April

4月30日

只出现一次的数字II

⚡ 哈希表O(N) O(N)

class Solution {
    public int singleNumber(int[] nums) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {
            hashMap.put(nums[i], hashMap.getOrDefault(nums[i], 0) + 1);
        }
        for (Map.Entry<Integer, Integer> entry : hashMap.entrySet()) {
            if (entry.getValue() == 1) return entry.getKey();
        }
        return -1;
    }
}

⚡ 依次确定每一个二进制位 O(N) O(1)

class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            int count = 0;
            for (int num : nums) {
                count += (num >> i) & 1;
            }
            if (count % 3 != 0) {
                ans |= 1 << i;
            }
        }
        return ans;
    }
}

4月29日

青蛙过河⭐

⚡ 动态规划

class Solution {
    public boolean canCross(int[] stones) {
        int n = stones.length;
        //dp[i][j] 表示从上一个石头用j跳，是否可以跳到stones[i]石头上
        boolean[][] dp = new boolean[n][n];
        dp[0][0] = true;

        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                int k = stones[i] - stones[j];
                if (k <= j + 1) { //在stones[j]表示的石头上最多可向前跳j + 1步
                    dp[i][k] = dp[j][k - 1] || dp[j][k] || dp[j][k + 1]; //判断是否有石子在k - 1到k + 1跳范围内, 可跳到stones[j]上
                }
            }
        }
        for (int i = 1; i < n; ++i) {
            if (dp[n - 1][i]) return true;
        }
        return false;
    }
}

⚡ 动态规划（优化）

class Solution {
    public boolean canCross(int[] stones) {
        int n = stones.length;

        //初步去掉一些显然不可到达的情况
        for (int i = 1; i < n; ++i) {
            //两个石头所在实际位置之差不可大于后者的数组索引值
            if (stones[i] - stones[i - 1] > i) return false;
        }

        //动态规划求解是否可到达最后一个石头
        // dp[i][k] 表示从上一个石头用k跳，是否可以跳到stones[i]石头上
        boolean[][] dp = new boolean[n][n];
        dp[0][0] = true;
        for (int i = 1; i < n; ++i) {
            for (int j = i - 1; j >= 0; --j) {
                int k = stones[i] - stones[j];
                // 在stones[j]表示的石头上最多可向前跳j + 1步
                if (k > j + 1) break; //"剪枝"，出现不满足条件的情况即可跳出此次循环
                //判断是否有石子在k - 1到k + 1跳范围内, 可跳到stones[j]上
                dp[i][k] = dp[j][k - 1] || dp[j][k] || dp[j][k + 1]; 
                if (i == n - 1 && dp[i][k]) return true;
            }
        }
        return false;
    }
}

可获得的最大点数

⚡ 滑动窗口

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        //剩余的卡牌必然是连续的
        //求得长度为 length - k 的最小自序和即可
        //滑动窗口
        int i = 0, j = cardPoints.length - k;
        int tmpSum = 0;
        for (int c = i; c < j; ++c) tmpSum += cardPoints[c];
        int ans = tmpSum;
        while (j < cardPoints.length) {
            tmpSum = tmpSum - cardPoints[i++] + cardPoints[j++];
            ans = Math.min(ans, tmpSum);
        }
        return Arrays.stream(cardPoints).sum() - ans;
    }
}

4月28日

平方数之和

⚡ 双指针O(sqrt(c))

class Solution {
    public boolean judgeSquareSum(int c) {
        int a = 0, b = (int) Math.sqrt(c);
        while (a <= b) {
            int tmp = c - b * b;
            if (tmp > a * a) ++a;
            else if (tmp < a * a) --b;
            else return true;
        }
        return false;
    }
}

排序链表⭐

⚡ 归并排序O(nlogn)

class Solution {
    //递归
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        //找到中间结点
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //中间截断链表
        ListNode head2 = slow.next;
        slow.next = null;
        //递归
        ListNode left = sortList(head);
        ListNode right = sortList(head2);
        //归并两个有序段
        ListNode res = new ListNode(0);
        ListNode h = res;
        while (left != null && right != null) {
            if (left.val > right.val) {
                h.next = right;
                right = right.next;
            }
            else {
                h.next = left;
                left = left.next;
            }
            h = h.next;
        }
        h.next = (left == null ? right : left);
        return res.next;
    }
}

4月27日

二叉搜索树的范围和⭐

⚡ DFS先序遍历

class Solution {
    //递归
    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) return 0;
        if (root.val > high) {
            return rangeSumBST(root.left, low, high);
        }
        if (root.val < low) {
            return rangeSumBST(root.right, low, high);
        }
        return root.val + rangeSumBST(root.right, low, high) + rangeSumBST(root.left, low, high);
    }
}

class Solution {
    //迭代 先序遍历
    public int rangeSumBST(TreeNode root, int low, int high) {
        int sum = 0;
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node == null) continue;
            if (node.val < low) {
                stack.push(node.right);
            }
            else if (node.val > high) {
                stack.push(node.left);
            }
            else {
                sum += node.val;
                stack.push(node.left);
                stack.push(node.right);
            }
        }
        return sum;
    }
}

⚡ BFS层序遍历

class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        int sum = 0;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode tmpNode = queue.poll();
            if (tmpNode == null) {
                continue;
            }
            if (tmpNode.val > high) {
                queue.offer(tmpNode.left);
            }
            else if (tmpNode.val < low) {
                queue.offer(tmpNode.right);
            }
            else {
                sum += tmpNode.val;
                queue.offer(tmpNode.left);
                queue.offer(tmpNode.right);
            }
        }
        return sum;
    }
}

对链表进行插入排序⭐

class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null) return head;

        ListNode dummyNode = new ListNode(0); //空头结点
        dummyNode.next = head;
        ListNode lastSort = head; //已经排好序部分的尾结点
        ListNode cur = head.next; //当前指向的结点
        while (cur != null) {
            if (lastSort.val <= cur.val) {
                lastSort = lastSort.next;
            }
            else {
                ListNode p = dummyNode;
                while (p.next.val <= cur.val) {
                    p = p.next;
                }
                lastSort.next = cur.next;
                cur.next = p.next;
                p.next = cur;
            }
            cur = lastSort.next;
        }
        return dummyNode.next;
    }
}

4月26日

在D天内送达包裹的能力⭐

⚡ 二分法

class Solution {
    public int shipWithinDays(int[] weights, int D) {
        //确定左右边界
        int left = Arrays.stream(weights).max().getAsInt();
        int right = Arrays.stream(weights).sum();

        while (left < right) {
            int mid = left + right >> 1;
            int day = 1, cur = 0;
            for (int weight : weights) {
                cur += weight;
                if (cur > mid) {
                    ++day;
                    cur = weight;
                }
            }
            //本题要最小的载重量
            //因此即使等于D，right也要继续左移，保证同等天数下的载重量最小
            //官方第一个案例中15、16均可满足要求，但最后答案只能是15
            if (day <= D) {
                right = mid;
            }else {
                left = mid + 1;
            }
        }
        return left;
    }
}

4月25日

递增顺序搜索树

⚡ DFS

class Solution {
    public TreeNode idxNode;

    public TreeNode increasingBST(TreeNode root) {
        TreeNode ans = new TreeNode(-1);
        idxNode = ans;
        inorder(root);
        return ans.right;
    }

    private void inorder (TreeNode node) {
        if (node == null) return;
        inorder(node.left);
        idxNode.right = new TreeNode(node.val);
        idxNode = idxNode.right;
        //在原树上操作
        //idxNode.right = node;
        //node.left = null;
        //idxNode = node;
        inorder(node.right);
    }
}

4月24日

组合总和Ⅳ

⚡ 动态规划

class Solution {
    public int combinationSum4(int[] nums, int target) {
        //dp[i]表示组合为i的方案数
        int[] dp = new int[target + 1];
        dp[0] = 1;

        for (int i = 1; i <= target; ++i) {
            for (int num : nums) {
                if (num <= i) {
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }
}

注意: 顺序不同的序列被视作不同的组合。(和零钱兑换II进行区分)

4月23日

最大整除子集

⚡ 动态规划

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);

        //动态规划找出最大子集的个数、最大子集中的最大整数
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int maxSize = 0;
        int maxVal = nums[0];

        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] % nums[j] == 0) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }

                if (maxSize < dp[i]) {
                    maxVal = nums[i];
                    maxSize = dp[i];
                }
            }
        }

        //倒推获得最大子集
        List<Integer> list = new ArrayList<Integer>();
        if (maxSize == 0) {
            list.add(nums[0]);
            return list;
        }

        for (int i = n - 1; i >= 0 && maxSize > 0; --i) {
            if (dp[i] == maxSize && maxVal % nums[i] == 0) {
                list.add(nums[i]);
                maxVal = nums[i];
                --maxSize;
            }
        }
        return list;
    }
}

4月22日

矩形区域不超过K的最大数值和

⚡ 暴力 + 动态规划

class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        int m = matrix.length, n = matrix[0].length;
        int ans = Integer.MIN_VALUE;

        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                int[][] dp = new int[m + 1][n + 1];
                dp[i][j] = matrix[i - 1][j - 1];
                for (int ii = i; ii <= m; ++ii) {
                    for (int jj = j; jj <= n; ++jj) {
                        dp[ii][jj] = dp[ii - 1][jj] + dp[ii][jj - 1] - dp[ii - 1][jj - 1] + matrix[ii - 1][jj - 1];
                        if (dp[ii][jj] > ans && dp[ii][jj] <= k) ans = dp[ii][jj];
                    }
                }
            }
        }
        return ans;
    }
}

⚡ 数组滚动⭐

class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        int m = matrix.length, n = matrix[0].length;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < m; ++i) { //枚举上边界
            int[] sum = new int[n];
            for (int j = i; j < m; ++j) { //枚举下边界
                for (int c = 0; c < n; ++c) {
                    sum[c] += matrix[j][c]; //更新每列元素的和
                }
                //化为一维问题求解
                max = Math.max(max, findMax(sum, k));
            }
        }
        return max;
    }

    //求一维数组中不超过k的最大数值和
    public static int findMax (int[] arr, int k) {
        int n = arr.length;
        int max = Integer.MIN_VALUE;
        int sum = 0;
        //先求数组的最大自序和 
        for (int i = 0; i < n; ++i) {
            sum = Math.max(sum + arr[i], arr[i]);
            max = Math.max(max, sum);
        }
        //如果最大自序和不超过k则返回其值
        if (max <= k) return max;

        max = Integer.MIN_VALUE;
        //若最大自序和大于k，则开始暴力求解
        for (int i = 0; i < n; ++i) {
            sum = 0;
            for (int j = i; j < n; ++j) {
                sum += arr[j];
                if (sum > max && sum <= k) {
                    max = sum;
                }
            }
        }
        return max;
    }
}

4月21日

解码方法

⚡ 动态规划

class Solution {
    public int numDecodings(String s) {
        int len = s.length();
        //dp[i]表示0到i-1字符的解码方法数量
        int[] dp = new int[len + 1];
        dp[0] = 1;
        //注意边界条件的判断
        for (int i = 1; i <= len; ++i) {
            if (s.charAt(i - 1) != '0') {
                dp[i] += dp[i - 1];
            }
            if (i > 1) {
                int num = (s.charAt(i - 2) - '0') * 10 + s.charAt(i - 1) - '0';
                if (s.charAt(i - 2) != '0' && num <= 26) {
                    dp[i] += dp[i - 2];
                }
            }
        }
        return dp[len];
    }
}

4月19日

移除元素

class Solution {
    public int removeElement(int[] nums, int val) {
        int n = nums.length;
        int slow = 0, fast = 0;
        while (fast < n) {
            if (nums[fast] != val) {
                nums[slow++] = nums[fast++];
            }
            else ++fast;
        }
        return slow;
    }
}

4月18日

删除有序数组中的重复项

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        int slow = 0, fast = 1;
        while (fast < n) {
            if (nums[slow] != nums[fast]) {
                nums[++slow] = nums[fast++];
            }
            else ++fast;
        }
        return slow + 1;
    }
}

注：与4月6日同类型

4月17日

存在重复元素III

⚡ 滑动窗口 & 有序集合

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int n = nums.length;
        TreeSet<Long> set = new TreeSet<Long>();
        //维护一个nums中i - k 到 i 的有序元素集合，找到有元素介于nums[i] - t , nums[i] + t之间返回true
        for (int i = 0; i < n; ++i) {
            //set.ceiling(e)在方法调用返回比至少元素大于或等于e或null，如果不存在这样的元素。
            Long ceiling = set.ceiling((long)nums[i] - (long)t);
            if (ceiling != null && ceiling <= ((long)nums[i] + (long)t)) {
                return true;
            }
            set.add((long)nums[i]);
            if (i >= k) {
                set.remove((long)nums[i - k]);
            }
        }
        return false;
    }
}

4月16日

扰乱字符串🌟

⚡ 动态规划 & 递归

class Solution {
    //记忆化搜索储存状态数组
    //-1表示false
    //1表示true
    //0表示未计算
    int[][][] memo;
    String s1, s2;

    public boolean isScramble(String s1, String s2) {
        int len = s1.length();
        this.memo = new int[len][len][len + 1];
        this.s1 = s1;
        this.s2 = s2;
        return dfs(0, 0, len);
    }

    //判断输入两个字符串是否和谐
    public boolean dfs (int i1, int i2, int length) {
        if (memo[i1][i2][length] != 0) {
            return memo[i1][i2][length] == 1;
        }
        //判断两个字串是否相等
        if (s1.substring(i1, i1 + length).equals(s2.substring(i2, i2 + length))) {
            memo[i1][i2][length] = 1;
            return true;
        }

        //判断是否存在子串c在两段字符中出现次数不同
        if (!checkIfSimilar(i1, i2, length)) {
            memo[i1][i2][length] = -1;
            return false;
        }

        //枚举不同的分割位置
        for (int i = 1; i < length; ++i) {
            //分割子串不交换位置
            if (dfs(i1, i2, i) && dfs(i1 + i, i2 + i, length - i)) {
                memo[i1][i2][length] = 1;
                return true;
            }
            //分割子串交换位置
            if (dfs(i1, i2 + length - i, i) && dfs(i1 + i, i2, length - i)) {
                memo[i1][i2][length] = 1;
                return true;
            }
        }

        memo[i1][i2][length] = -1;
        return false;
    }

    //检查两子串中相同字符出现次数是否相同
    public boolean checkIfSimilar (int i1, int i2, int length) {
        HashMap<Character, Integer> freq = new HashMap<Character, Integer>();
        //对应键值加1
        for (int i = i1; i < i1 + length; ++i) {
            //getOrDefault() 方法获取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值。
            //key - 键
            //defaultValue - 当指定的key并不存在映射关系中，则返回的该默认值
            char c = s1.charAt(i);
            freq.put (c, freq.getOrDefault(c, 0) + 1);
        }
        //对应键值减1
        for (int i = i2; i < i2 + length; ++i) {
            char c = s2.charAt(i);
            freq.put(c, freq.getOrDefault(c, 0) - 1);
        }
        //遍历整个HashMap
        for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
            //不为零则两字串中对应字符出现次数不同
            if (entry.getValue() != 0) return false; 
        }
        return true;
    }
}

4月15日

打家劫舍 II

⚡ 动态规划

class Solution {
    public int rob(int[] nums) {

        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        if (n == 2) return Math.max(nums[0], nums[1]);

        int[] dp1 = new int[n];
        int[] dp2 = new int[n];
        //1到n
        dp1[1] = nums[1];
        dp1[2] = Math.max(nums[1], nums[2]);
        for (int i = 3; i < n; ++i) {
            dp1[i] = Math.max(dp1[i - 2] + nums[i], dp1[i - 1]);
        }

        //0到n-1
        dp2[0] = nums[0];
        dp2[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n - 1; ++i) {
            dp2[i] = Math.max(dp2[i - 2] + nums[i], dp2[i - 1]);
        }

        return Math.max(dp1[n - 1], dp2[n - 2]);
    }
}

打家劫舍

⚡ 动态规划

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

4月14日

实现 Trie (前缀树)

class Trie {
    private Trie[] children;
    private boolean isEnd;

    /** Initialize your data structure here. */
    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); ++i) {
            int idx = word.charAt(i) - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new Trie();
            }
            node = node.children[idx];
        }
        node.isEnd = true;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;

    }

    //查找指定字符串是否在字典树中存在，并返回最后一个字母所在节点
     public Trie searchPrefix(String prefix) {
        Trie node = this;
        for (int i = 0; i < prefix.length(); ++i) {
            int idx = prefix.charAt(i) - 'a';
            if (node.children[idx] == null) {
                return null;
            }
            node = node.children[idx];
        }
        return node;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

岛屿数量⭐

⚡ DFS深度优先遍历

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; ++i) {
            for (int j = 0; j < grid[0].length; ++j) {
                //当是陆地时，进入递归，递归结束时岛屿数量加1
                if (grid[i][j] == '1') {
                    gridDfs (grid, i, j);
                    ++count;
                }
            }
        }
        return count;
    }

    public void gridDfs (char[][] grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') {
            return;
        }
        //标记已访问，当原图不能改时可以用visited数组代替
        grid[i][j] = '0';
        //递归周边其他节点
        gridDfs (grid, i + 1, j);
        gridDfs (grid, i, j + 1);
        gridDfs (grid, i - 1, j);
        gridDfs (grid, i, j - 1);
    }
}

⚡ DFS广度优先遍历

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; ++i) {
            for (int j = 0; j < grid[0].length; ++j) {
                //当是陆地时，进入递归，递归结束时岛屿数量加1
                if (grid[i][j] == '1') {
                    grid[i][j] = '0';
                    gridBfs (grid, i, j);
                    ++count;
                }
            }
        }
        return count;
    }
    //广度优先遍历
    public void gridBfs (char[][] grid, int i, int j) {
        int n = grid.length;
        int m = grid[0].length;
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(i * m + j);
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            i = cur / m; j = cur % m;
            //入队前先判断防止重复入队浪费资源
            if ((i - 1) >= 0 && grid[i - 1][j] == '1') {
                grid[i - 1][j] = '0';
                queue.offer((i - 1) * m + j);
            }
            if ((i + 1) < n && grid[i + 1][j] == '1') {
                grid[i + 1][j] = '0';
                queue.offer((i + 1) * m + j);
            }
            if ((j - 1) >= 0 && grid[i][j - 1] == '1') {
                grid[i][j - 1] = '0';
                queue.offer(i * m + j - 1);
            }
            if ((j + 1) < m && grid[i][j + 1] == '1') {
                grid[i][j + 1] = '0';
                queue.offer(i * m + j + 1);
            }
        }
    }
}

BFS遍历方法的另一种写法：

public void gridBfs (char[][] grid, int i, int j) {
    Queue<int[]> queue = new LinkedList<int[]>();
    queue.add(new int[] {i, j});
    while (!queue.isEmpty()) {
        int[] cur = queue.remove();
        i = cur[0]; j = cur[1];
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') {
            continue;
        }
        grid[i][j] = '0';
        //未判断会出现重复入队
        queue.add(new int[] {i + 1, j});
        queue.add(new int[] {i, j + 1});
        queue.add(new int[] {i - 1, j});
        queue.add(new int[] {i, j - 1});
    }
}

队列（Queue）相关方法区别：

1. offer，add 区别：
   • 一些队列有大小限制，因此如果想在一个满的队列中加入一个新项，多出的项就会被拒绝。这时新的 offer 方法就可以起作用了。它不是对调用 add() 方法抛出一个 unchecked 异常，而只是得到由 offer() 返回的 false。
2. poll，remove 区别：
   • remove() 和 poll() 方法都是从队列中删除第一个元素。remove() 的行为与 Collection 接口的版本相似， 但是新的 poll() 方法在用空集合调用时不是抛出异常，只是返回 null。因此新的方法更适合容易出现异常条件的情况。
3. peek，element区别：
   • element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似，在队列为空时， element() 抛出一个异常，而 peek() 返回 null。

4月13日

二叉搜索树节点最小距离

⚡ 对二叉搜索树进行中序遍历，将遍历的值保存到list中，再判断元素之间最小差值

/**
 * 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 {
    public int minDiffInBST(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        inorder (root, list);
        int min = Integer.MAX_VALUE;
        for (int i = 1; i < list.size(); ++i) {
            min = Math.min(list.get(i) - list.get(i - 1), min);
        } 
        return min;
    }
    //中序遍历
    private void inorder (TreeNode node, List<Integer> res) {
        if (node == null) return;
        inorder (node.left, res);
        res.add(node.val);
        inorder (node.right, res);
    }
}

⚡ 上述方法优化

class Solution {
    int ans = Integer.MAX_VALUE;
    int pre = -1;
    public int minDiffInBST(TreeNode root) {
        return inorder(root);
    }
    //中序遍历
    private int inorder (TreeNode node) {
        if (node == null) return ans;
        inorder(node.left);
        if (pre == -1) pre = node.val;
        else {
            ans = Math.min(ans, node.val - pre);
            pre = node.val;
        }
        inorder (node.right);
        return ans;
    }
}

4月12日

最大数⭐

class Solution {
    public String largestNumber(int[] nums) {
        int n = nums.length;

        //Arrays类提供的函数中，没有方法对int[]数组进行排序。
        //sort函数可以有第二个参数: Comparator参数，但此参数仅支持引用类型。
        //int并非引用类型，无法对int[]数组进行排序，因此需要把数组复制进Integer[]数组中。
        Integer[] numsArr = new Integer[n];
        for (int i = 0; i < n; ++i) {
            numsArr[i] = nums[i];
        }

        //使用lambda表达式重写Comparator比较器
        //返回值小于0时，排序x在y的前面；返回值大于0时，排序x在y的后面；
        Arrays.sort(numsArr, (x, y) -> {
            long sx = 10, sy = 10;
            while (sx <= x) sx *= 10;
            while (sy <= y) sy *= 10;
            return (int) (sx * y + x - sy * x - y);
        });

        //上述步骤结束后numsArr里元素已经按照要求排序完成
        //首先判断是否元素都为0
        if (numsArr[0] == 0) return "0";
        //以下进行数组结果字符串输出
        StringBuilder ret = new StringBuilder();
        for (int num : numsArr) ret.append(num);
        return ret.toString();
    }
}

4月11日

丑数II⭐

⚡ 动态规划

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        int p2 = 1, p3 = 1, p5 = 1;
        for (int i = 2; i <= n; ++i) {
            int num2 = dp[p2] * 2;
            int num3 = dp[p3] * 3;
            int num5 = dp[p5] * 5;
            dp[i] = Math.min(Math.min(num2, num3), num5);
            if (dp[i] == num2) ++p2;
            if (dp[i] == num3) ++p3;
            if (dp[i] == num5) ++p5;
        }
        return dp[n];
    }
}

4月10日

丑数

⚡ 丑数就是只包含质因数2、3、5 的正整数

class Solution {
    public boolean isUgly(int n) {
        if (n <= 0) return false;

        while (n % 2 == 0) n /= 2;
        while (n % 3 == 0) n /= 3;
        while (n % 5 == 0) n /= 5;

        if (n == 1) return true;
        else return false;
    }
}

4月9日

寻找旋转排序数组中的最小值II⭐

⚡ 二分法

class Solution {
    public int findMin(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low < high) {
            int mid = (low + high) / 2;
            if (nums[mid] < nums[high]) {
                high = mid;
            }
            else if (nums[mid] > nums[high]) {
                low = mid + 1;
            }
            else --high;
        }
        return nums[low];
    }
}

4月8日

寻找旋转排序数组中的最小值

⚡ 利用规律线性查找

class Solution {
    public int findMin(int[] nums) {
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] < nums[i - 1]) return nums[i];
        }
        return nums[0];
    }
}

⚡ 二分法

class Solution {
    public int findMin(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low < high) {
            int mid = (low + high) / 2;
            if (nums[mid] < nums[high]) {
                high = mid;
            }
            //不可能会有等于的情况
            else if (nums[mid] > nums[high]) {
                low = mid + 1;
            }
        }
        return nums[low];
    }
}

4月7日

搜索旋转排序数II⭐

⚡ 利用规律线性查找

class Solution {
    public boolean search(int[] nums, int target) {
        int n = nums.length;
        if (nums[0] == target || nums[n - 1] == target) return true;

        for (int i = 0; i < n - 1; ++i) {
            if (target > nums[i] && target < nums[i + 1]) {
                return false;
            }
            else if (target == nums[i]) {
                return true;
            }
        }
        return false;
    }
}

⚡ 二分法

class Solution {
    public boolean search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) return false;
        if (n == 1) return nums[0] == target;
        int low = 0, high = n - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (nums[mid] == target) return true;
            if (nums[mid] == nums[low] && nums[mid] == nums[high]) {
                ++low;
                --high;
            }
            else if (nums[low] <= nums[mid]) {
                //这里由于上面已经判断过了target == nums[mid]因此可以不需要做等于判断。
                if (target >= nums[low] && target < nums[mid]) {
                    high = mid - 1;
                }
                else {
                    low = mid + 1;
                }
            }
            else {
                if (target > nums[mid] && target <= nums[high]) {
                    low = mid + 1;
                }
                else {
                    high = mid - 1;
                }
            }
        }
        return false;
    }
}

搜索旋转排序数组

⚡ 二分法

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) return -1;
        if (n == 1) return nums[0] == target ? 0 : -1;
        int low = 0, high = n - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (nums[mid] == target) return mid;
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) high = mid - 1; 
                else low = mid + 1;
            } 
            else {
                if (nums[mid] < target && target <= nums[n - 1]) low = mid + 1; 
                else high = mid - 1;
            }
        }
        return -1;
    }
}

验证回文串

class Solution {
    public boolean isPalindrome(String s) {
        int n = s.length();
        int low = 0, high = n - 1;
        while (low < high) {
            while (low < high && !Character.isLetterOrDigit(s.charAt(low))) ++low;
            while (low < high && !Character.isLetterOrDigit(s.charAt(high))) --high;
            if(low < high) {
                if (Character.toLowerCase(s.charAt(low)) != Character.toLowerCase(s.charAt(high))) {
                    return false;
                }
                ++low;
                --high;
            }
        }
        return true;
    }
}

• Character.toLowerCase()方法用于将大写字符转换为小写。
• Character.isLetterOrDigit()方法确定指定字符(Unicode代码点)是一个字母或数字。

4月6日

删除有序数组中的重复项II

class Solution {
    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        if (len <= 2) return len;
        int slow = 2, fast = 2;
        while (fast < len) {
            if(nums[slow - 2] != nums[fast]) {
                nums[slow] =  nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
}

4月5日

合并两个有序数组

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1, j = n - 1;
        int k = m + n - 1;
        while (j >= 0) {
            if (i >= 0 && nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            }
            else {
                nums1[k--] = nums2[j--];
            }
        }
    }
}

二分查找

class Solution {
    public int search(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        int mid = 0;
        while (low <= high) {
            mid = (low + high) / 2;
            if (nums[mid] > target) {
                high = mid - 1;
            }
            else if (nums[mid] < target) {
                low = mid + 1;
            }
            else return mid;
        }
        return -1;
    }
}

截断句子

class Solution {
    public String truncateSentence(String s, int k) {
        StringBuilder ans = new StringBuilder();
        for (String i : s.split("\\s+")) {
            if (k-- > 0)
            ans = ans.append(i).append(' ');

        }
        ans.setLength(ans.length() - 1);
        return ans.toString();
    }
}

• split("\s+") 按空格,制表符，等进行拆分，也就是说它是按空白部分进行拆分，不管这个空白使用什么操作留下的（如空格键 tab键）；
• split(" +") 按空格进行拆分，也就是说只有按空格键流出来的空白才会是拆分的一句。

4月4日

森林中的兔子

class Solution {
    public int numRabbits(int[] answers) {
        Map<Integer, Integer> count = new HashMap<Integer, Integer>();
        for (int y : answers) {
            //getOrDefault()方法获取指定key对应对value，如果找不到key，则返回设置的默认值。
            count.put(y, count.getOrDefault(y, 0) + 1);
        }
        int ans = 0;
        for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
            int y = entry.getKey(), x = entry.getValue();
            // (x + y) / (y + 1)用来向上取整求共有多少组兔子
            ans += (x + y) / (y + 1) * (y + 1);
        }
        return ans;
    }
}

万一兔子说谎了呢？

排序数组

⚡ 快速排序

class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length-1);
        return nums;
    }
    public static void quickSort(int[] arr, int start, int end) {
        int mid = partition(arr, start, end); //数组分区
        quickSort(arr, start, mid - 1); //左边快排
        quickSort(arr, mid + 1, end); //右边快排
    }
    public static int partition(int[] arr, int start, int end) {
        int pivot = arr[0];
        while (start < end) {
            while (start < end && arr[end] >= pivot) --end;
            arr[start] = arr[end];
            while (start < end && arr[start] <= pivot) ++start;
            arr[end] = arr[start];
        }
        arr[start] = pivot;
        return start;
    }
}

4月3日

最长公共子序列

见动态规划专题训练

4月2日

直方图的水量⭐

⚡ 动态规划 Time: O(n) Space: O(n)

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if(n == 0) return 0;
        int leftMax[] = new int[n];
        int rightMax[] = new int[n];
        //动态规划两个表示某一元素左右两边最大值的数组
        leftMax[0] = height[0];
        rightMax[n - 1] = height[n - 1];
        for (int i = 1; i < n; ++i) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }
        for (int j = n-2; j >= 0; --j) {
            rightMax[j] = Math.max(rightMax[j + 1], height[j]);
        }
        //利用求出的两个数组求水量
        int ans = 0;
        for (int i = 0; i < n; ++i) {
                ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
}

⚡ 双指针法 Time: O(n) Space: O(1)

class Solution {
    public int trap(int[] height) {
        int ans = 0;
        int low = 0, high = height.length - 1;
        int lowMax = 0, highMax = 0;
        while (low < high) {
            lowMax = Math.max(lowMax, height[low]);
            highMax = Math.max(highMax, height[high]);

            if(height[low] < height[high]) {
                ans += lowMax - height[low];
                ++low;
            }
            else {
                ans += highMax - height[high];
                --high;
            }
        }
        return ans;
    }
}

4月1日

笨阶乘

⚡ 栈模拟

class Solution {
    public int clumsy(int N) {
        Deque<Integer> stack = new LinkedList<Integer>();
        stack.push(N--);
        int index = 0;
        while(N > 0) {
            if(index % 4 == 0) stack.push(stack.pop() * N);
            else if(index % 4 == 1) stack.push(stack.pop() / N);
            else if(index % 4 == 2) stack.push(N);
            else stack.push(-N);
            --N; ++index;
        }

        int sum = 0;
        while(!stack.isEmpty()) {
            sum += stack.pop();
        }
        return sum;
    }
}

删除有序数组中的重复项

⚡ 双指针法

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums == null) return 0;
        int i = 0, j = 1;
        while(j < nums.length) {
            if(nums[i] == nums[j]) ++j;
            else nums[++i] = nums[j++];
        }
        return i + 1;
    }
}

旋转数组

class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length-1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }

    private void reverse(int[] nums, int low, int high) {
        while(low < high) {
            int temp = nums[low];
            nums[low] = nums[high];
            nums[high] = temp;
            ++low; --high;
        }
    }
}

March

3月31日

子集⭐

⚡ 回溯算法(递归)

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(0, nums, res, new ArrayList<Integer>());
        return res;

    }

    private void backtrack(int i, int[] nums, List<List<Integer>> res, ArrayList<Integer> temp){
        res.add(new ArrayList<>(temp));
        for(int j = i; j < nums.length; ++j) {
            temp.add(nums[j]);
            backtrack(j + 1, nums, res, temp);
            temp.remove(temp.size() - 1);
        }
    }
}

子集II⭐

⚡ 回溯算法

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums); //对有重复元素的数组先进行排序
        backtrack(0, nums, res, new ArrayList<Integer>());
        return res;

    }

    private void backtrack(int i, int[] nums, List<List<Integer>> res, ArrayList<Integer> temp){
        res.add(new ArrayList<>(temp));
        for(int j = i; j < nums.length; ++j) {
            if(j != i && nums[j] == nums[j-1]) continue; //当出现重复元素进行剪枝
            temp.add(nums[j]);
            backtrack(j + 1, nums, res, temp);
            temp.remove(temp.size() - 1);
        }
    }
}

搜索二维矩阵II

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length - 1, n = 0;
        while(m >= 0 && n < matrix[0].length) {
            if(matrix[m][n] > target) --m;
            else if(matrix[m][n] < target) ++n;
            else return true;
        }
        return false;
    }
}

3月30日

搜索二维矩阵

⚡ 单次二分查找

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int low = 0, high = m * n - 1;

        while(low <= high) {
            int mid = (low + high) / 2;
            int x = matrix[mid / n][mid % n];

            if(x < target) low = mid + 1;
            else if (x > target) high = mid - 1;
            else return true;
        }
        return false;
    }
}

二叉树的深度⭐

⚡ DFS后序遍历

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

⚡ BFS层序遍历

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;

        int res = 0;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);

        while(!queue.isEmpty()){
            int currentLevelSize = queue.size();
            for(int i = 0; i < currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
            res++;
        }
        return res;
    }
}

平衡二叉树⭐

⚡ DFS自底向上

class Solution {
    public boolean isBalanced(TreeNode root) {
        return dfs(root) != -1;
    }

    private int dfs(TreeNode root) {
        if(root == null) return 0;

        int left = dfs(root.left);
        if(left == -1) return -1;

        int right = dfs(root.right);
        if(right == -1) return -1;

        return Math.abs(left - right) <= 1 ? Math.max(left, right) + 1 : -1;
    }
}

⚡ 自顶向下

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    private int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

3月29日

颠倒二进制位

⚡ 逐位颠倒

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int ret = 0;
        for(int i = 0; i < 32; ++i) {
            ret |= (n & 1) << (31 - i);
            n >>>= 1;
        }
        return ret;
    }
}

⚡ 位运算分治

public class Solution {
    // you need treat n as an unsigned value
    private static final int M1 = 0x55555555;
    private static final int M2 = 0x33333333;
    private static final int M4 = 0x0f0f0f0f;
    private static final int M8 = 0x00ff00ff;

    public int reverseBits(int n) {
        n = (n >>> 1 & M1) | ((n & M1) << 1);
        n = (n >>> 2 & M2) | ((n & M2) << 2);
        n = (n >>> 4 & M4) | ((n & M4) << 4);
        n = (n >>> 8 & M8) | ((n & M8) << 8);

        return n >>> 16 | (n << 16);
    }
}

注：>>>表示不带符号向右移动二进制数，位运算优先级高于逻辑运算可去掉部分括号。

反转链表

⚡ 迭代法

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null, curr = head;
        while(curr != null) {
            ListNode temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }
        return prev;
    }
}

⚡ 递归法

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode newhead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newhead;
    }
}

3月28日

二叉搜索树迭代器

class BSTIterator {
    private int index;
    private List<Integer> arr;

    public BSTIterator(TreeNode root) {
        index = 0;
        arr = new ArrayList<Integer>();
        inorderTraversal(root, arr);
    }

    public int next() {
        return arr.get(index++);
    }

    public boolean hasNext() {
        return index < arr.size();
    }

    private void inorderTraversal(TreeNode root, List<Integer> arr) {
        if (root == null) return;
        inorderTraversal(root.left, arr);
        arr.add(root.val);
        inorderTraversal(root.right, arr);
    }
}

3月27日

旋转链表

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(k==0 || head==null || head.next==null) {
            return head;
        }
        int n = 1;
        ListNode q = head;
        while(q.next != null){
            q = q.next;
            n++;
        }
        int add = n - k%n;
        if(add == n) return head;
        q.next = head;

        while(add-- > 0) q = q.next;
        ListNode ret = q.next;
        q.next = null;
        return ret;
    }
}

二叉树的层序遍历⭐

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if(root == null) return ret;

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);

        while(!queue.isEmpty()){
            List<Integer> level = new ArrayList<Integer>();
            int currentLevelSize = queue.size();
            for(int i = 0; i < currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
            ret.add(level);
        }
        return ret;
    }
}

二叉树的中序遍历⭐

⚡ 递归

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        inorder(root, list);
        return list;
    }

    private void inorder (TreeNode node, List<Integer> list) {
        if (node == null) return;
        inorder (node.left, list);
        list.add(node.val);
        inorder (node.right, list);
    }
}

⚡ 迭代⭐

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }
}

二叉树的后序遍历⭐

⚡ 迭代⭐

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode prev = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (root.right == null || root.right == prev) {
                list.add(root.val);
                prev = root;
                root = null;
            } else {
                stack.push(root);
                root = root.right;
            }
        }
        return list;
    }
}

二叉树的前序遍历

⚡ 迭代⭐

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node != null) {
                list.add(node.val);
                stack.push(node.right);
                stack.push(node.left);
            }
        }
        return list;
    }
}

3月26日

删除排序链表中的重复元素

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null) return head;

        ListNode q = head;
        while(q.next != null) {
            if(q.val == q.next.val) {
                q.next = q.next.next;
            }
            else q = q.next;
        }
        return head;
    }
}

3月25日

删除排序链表中的重复元素II⭐

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode p = dummy;
        while (p.next != null && p.next.next != null) {
            if (p.next.val == p.next.next.val) {
                int x = p.next.val;
                while (p.next != null && p.next.val == x) {
                    p.next = p.next.next;
                }
            }
            else {
                p = p.next;
            }
        }
        return dummy.next;
    }
}

3月24日

132模式⭐

⚡ 单调栈

class Solution {
    public boolean find132pattern(int[] nums) {
        int n = nums.length;
        Stack<Integer> candidateK = new Stack<>();
        candidateK.push(nums[n - 1]);
        int maxK = Integer.MIN_VALUE;
        for (int i = n - 2; i >= 0; --i) {
            if (nums[i] < maxK) return true;
            while (!candidateK.isEmpty() && nums[i] > candidateK.peek()) {
                maxK = candidateK.pop();
            }
            if (nums[i] > maxK) {
                candidateK.push(nums[i]);
            }
        }
        return false;
    }
}