头像

请用心听




离线:2小时前


最近来访(7)
用户头像
布克波波
用户头像
一万小时定律
用户头像
mungo
用户头像
abcla
用户头像
无人生还
用户头像
ZeroAC
用户头像
MWL丶

活动打卡代码 LeetCode 134. 加油站

请用心听
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;
    }
}


活动打卡代码 LeetCode 198. 打家劫舍

请用心听
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;
    }
}


活动打卡代码 LeetCode 131. 分割回文串

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()) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = u; i < s.length(); i ++ ) {
            if (f[u][i]) {
                path.add(s.substring(u, i + 1));
                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) {
            set.add(num);
        }
        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;
    }
}