3524

mungo
abcla

ZeroAC
MWL丶

2小时前
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
int curs = 0, sum = 0, res = 0;
for (int i = 0; i < n; i ++ ) {
curs += gas[i] - cost[i];
sum += gas[i] - cost[i];
if (curs < 0) {
curs = 0;
res = i + 1;
}
}
if (sum >= 0) return res;
return -1;
}
}


14小时前
class Solution {
public int rob(int[] nums) {
int n = nums.length;
int[] f = new int[n + 1];
f[0] = 0; f[1] = nums[0];
for (int i = 2; i <= n; i ++ ) {
f[i] = Math.max(f[i - 1], f[i - 2] + nums[i - 1]);
}
return f[n];
}
}


class Solution {
public int minCut(String s) {
int n = s.length();
s = ' ' + s; //下标从1开始
boolean[][] g = new boolean[n + 1][n + 1];
int[] f = new int[n + 1];
Arrays.fill(f, Integer.MAX_VALUE);
for (int j = 1; j <= n; j ++ )  {
for (int i = 1; i <= n; i ++ ) {
if (i == j) g[i][j] = true;
else if (s.charAt(i) == s.charAt(j)) {
if (i + 1 > j - 1 || g[i + 1][j - 1])
g[i][j] = true;
}
}
}
f[0] = 0;
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= i; j ++ ) {
if (g[j][i]) {
f[i] = Math.min(f[i], f[j - 1] + 1);
}
}
}
return f[n] - 1;
}
}


class Solution {
boolean[][] f;
List<List<String>> ans = new ArrayList<>();
List<String> path = new ArrayList<>();
public List<List<String>> partition(String s) {
int n = s.length();
f = new boolean[n][n];  //预处理f数组，判断i～j这段是否是回文串
for (int j = 0; j < n; j ++ ){
for (int i = 0; i <= j; i ++ ) {
if (i == j) f[i][j] = true;
else if (s.charAt(i) == s.charAt(j)) {
if (i + 1 > j - 1 || f[i + 1][j - 1]) f[i][j] = true;
}
}
}
dfs(s, 0);
return ans;
}

void dfs(String s, int u) {
if (u == s.length()) {
return;
}
for (int i = u; i < s.length(); i ++ ) {
if (f[u][i]) {
dfs(s, i + 1);
path.remove(path.size() - 1);
}
}
}
}


class Solution {
public void solve(char[][] board) {
int n = board.length, m = board[0].length;
for (int i = 0; i < n; i ++ ) {
dfs(board, i, 0, n, m);
dfs(board, i, m - 1, n, m);
}
for (int i = 0; i < m; i ++ ) {
dfs(board, 0, i, n, m);
dfs(board, n - 1, i, n, m);
}
for (int i = 0; i < n; i ++ ) {
for (int j = 0; j < m; j ++ ) {
if (board[i][j] == '*') board[i][j] = 'O';
else board[i][j] = 'X';
}
}
}
void dfs(char[][] board, int x, int y, int n, int m) {
if (board[x][y] != 'O') return;
board[x][y] = '*';      //标记边界以及连接在边界上的O
int[] dx = new int[]{-1, 0, 1, 0};
int[] dy = new int[]{0, 1, 0, -1};
for (int i = 0; i < 4; i ++ ) {
int tx = x + dx[i], ty = y + dy[i];
if (tx > 0 && tx < n && ty > 0 && ty < m) {
dfs(board, tx, ty, n, m);
}
}
}
}


/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
int ans;
public int sumNumbers(TreeNode root) {
if (root != null) dfs(root, 0);
return ans;
}
void dfs(TreeNode u, int number) {
number = number * 10 + u.val;
//叶子节点，把答案加上
if (u.left == null && u.right == null) ans += number;
if (u.left != null) dfs(u.left, number);
if (u.right != null) dfs(u.right, number);
}
}


class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num: nums) {
}
int res = 0;
for (int x: nums) {
if (set.contains(x) && !set.contains(x - 1)) {
int y = x;
set.remove(x);
while (set.contains(y + 1)) {
y ++;
set.remove(y);
}
res = Math.max(res, y - x + 1);
}
}
return res;
}
}


class Solution {
Map<Integer, Integer> map = new HashMap<>();
public int longestConsecutive(int[] nums) {
int res = 0;
for (int i = 0; i < nums.length; i ++ ) {
map.put(nums[i], i);
}
for (int num: nums) {
//找到连续序列的开头
if (!map.containsKey(num - 1)) {
res = Math.max(res, find(num + 1) - num);
}
}
return res;
}

int find(int x) {
return map.containsKey(x) ? find(x + 1) : x;
}
}