5月31日

4的幂

class Solution {
    public boolean isPowerOfFour(int n) {
        // 0x2aaaaaaa也可以，因为n是有符号的32位整数
        return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
    }
}

5月30日🥗

2 的幂⭐

class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n == 0) return false;
        long b = (long) n;
        return (b & (b - 1)) == 0;
    }
}

二叉树中的最大路径和⭐

⚡ 递归

class Solution {
    int ans;
    public int maxPathSum(TreeNode root) {
        ans = Integer.MIN_VALUE;
        maxGain(root);
        return ans;
    }

    private int maxGain(TreeNode node) {
        if (node == null) return 0;
        // 获取左右节点的最大贡献值
        int leftVal = Math.max(maxGain(node.left), 0);
        int rightVal = Math.max(maxGain(node.right), 0);
        // 当前节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int currentVal = node.val + leftVal + rightVal;
        // 更新答案
        ans = Math.max(ans, currentVal);
        // 返回最大贡献值
        return node.val + Math.max(leftVal, rightVal);
    }
}

最小面积矩形

⚡ 枚举对角线

class Solution {
    static int N = 40001;
    public int minAreaRect(int[][] points) {
        Set<Integer> set = new HashSet<>();
        for (int[] p : points) set.add(p[0] * N + p[1]);
        int n = points.length;
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; ++ i) {
            for (int j = i + 1; j < n; ++ j) {
                if (points[i][0] != points[j][0] && points[i][1] != points[j][1]) {
                    if (set.contains(points[i][0] * N + points[j][1]) && set.contains(points[j][0] * N + points[i][1])) {
                        ans = Math.min(ans, Math.abs(points[i][0] - points[j][0]) * Math.abs(points[i][1] - points[j][1]));
                    }
                }
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

5月29日

元素和为目标值的子矩阵数量⭐

⚡ 前缀和 & 压缩

class Solution {
    public int numSubmatrixSumTarget(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int cnt = 0;

        for (int i = 0; i < m; ++ i) {
            int[] pre = new int[n];
            for (int j = i; j < m; ++ j) {
                for (int k = 0; k < n; ++ k) {
                    pre[k] += matrix[j][k]; // 压缩为一维
                }
                cnt += subarraySum(pre, target);
            }
        }
        return cnt;
    }

    // 和为K的子数组数量
    private int subarraySum (int[] nums, int k) {
        int n = nums.length;
        HashMap<Integer, Integer> map = new HashMap<>(){{
            put(0, 1);
        }};

        int pre = 0, cnt = 0;
        for (int i = 0; i < n; ++ i) {
            pre += nums[i];
            cnt += map.getOrDefault(pre - k, 0);
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }
        return cnt;
    }
}

5月28日

汉明距离总和⭐

⚡ 逐位统计

class Solution {
    public int totalHammingDistance(int[] nums) {
        int n = nums.length;
        int ans = 0;
        for (int i = 30; i >= 0; -- i) {
            int tmp = 0;
            for (int j = 0; j < n; ++ j) {
                tmp += (nums[j] >> i) & 1;
            }
            ans += tmp * (n - tmp);
        }
        return ans;
    }
}

5月27日

汉明距离

class Solution {
    public int hammingDistance(int x, int y) {
        int ans = 0, s = x ^ y;
        // Brian Kernighan 算法： 只需遍历 1
        while (s != 0) {
            s &= s - 1;
            ++ ans;
        }
        return ans;
    }
}

5月26日

反转每对括号间的子串

⚡ 栈O(n2)

class Solution {
    public String reverseParentheses(String s) {
        Deque<Character> stack = new LinkedList<>();
        Queue<Character> queue = new LinkedList<>();

        int n = s.length();
        for (int i = 0; i < n; ++ i) {
            if (s.charAt(i) == ')') {
                while (stack.peek() != '(') {
                    queue.offer(stack.pop());
                }
                stack.pop();
                while (!queue.isEmpty()) {
                    stack.push(queue.poll());
                }
            } else {
                stack.push(s.charAt(i));
            }
        }
        StringBuilder str = new StringBuilder();
        while (!stack.isEmpty()) {
            str.append(stack.pop());
        }
        return str.reverse().toString();
    }
}

⚡ 预处理 & 指针 O(n)

class Solution {
    public String reverseParentheses(String s) {
        Deque<Integer> stack = new LinkedList<>();
        int n = s.length();
        int[] pair = new int[n];
        for (int i = 0; i < n; ++ i) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else if (s.charAt(i) == ')'){
                pair[i] = stack.peek();
                pair[stack.pop()] = i;
            }
        }

        StringBuilder str = new StringBuilder();
        int step = 1, idx = 0;
        while (idx < n) {
            char ch = s.charAt(idx);
            if (ch == '(' || ch == ')') {
                idx = pair[idx];
                step = -step;
            } else {
                str.append(ch);
            }
            idx += step;
        }
        return str.toString();
    }
}

合并区间

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (x, y) -> x[0] - y[0]);
        List<int[]> list = new LinkedList<>();
        int l = intervals[0][0], r = intervals[0][1];
        for (int i = 1; i < intervals.length; ++ i) {
            if (r >= intervals[i][0]) {
                r = Math.max(r, intervals[i][1]);
            } else {
                list.add(new int[]{l, r});
                l = intervals[i][0];
                r = intervals[i][1];
            }
        }
        list.add(new int[]{l,r});

        int n = list.size();
        int[][] ans = new int[n][2];
        for (int i = 0; i < n; ++ i) {
            ans[i] = list.get(i);
        }
        return ans;
    }
}

数组中的第K个最大元素⭐

⚡ 随机数快排

class Solution {
    Random random = new Random();
    public int findKthLargest(int[] nums, int k) {
        quickSort(nums, 0, nums.length - 1);
        return nums[nums.length - k];
    }

    public void quickSort(int[] nums, int start, int end) {
        if (start >= end) return;
        int l = start, r = end;
        int randIdx = random.nextInt(r - l + 1) + l;
        swap(nums, l, randIdx);
        int piovt = nums[l];
        while (l < r) {
            while (l < r && nums[r] >= piovt) -- r;
            if (l < r) nums[l] = nums[r];
            while (l < r && nums[l] <= piovt) ++ l;
            if (l < r) nums[r] = nums[l]; 
        }
        nums[l] = piovt;
        quickSort(nums, start, l - 1);
        quickSort(nums, l + 1, end);
    }

    private void swap (int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

二叉树的右视图

⚡ 层序遍历

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        Queue<TreeNode> q = new LinkedList<>();    
        q.offer(root);
        while (!q.isEmpty()) {
            int levelSize = q.size();
            for (int i = 1; i <= levelSize; ++ i) {
                TreeNode node = q.poll();
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
                if (i == levelSize) list.add(node.val);
            }
        }
        return list;
    }
}

5月25日

使所有区间的异或结果为零

跳跃游戏II

⚡ 贪心

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int step = 0;
        int end = 0;
        int maxPosition = 0;
        for (int i = 0; i < n - 1; ++ i) {
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (i == end) {
                end = maxPosition;
                step ++;
            }
        }
        return step;
    }
}

类似题型：
LeetCode动态规划专题 - 跳跃游戏
LC-Weekly242 - 跳跃游戏VII

5月24日🥗

奇怪的打印机⭐

⚡ 区间dp

class Solution {
    public int strangePrinter(String s) {
        int n = s.length();
        // f[i][j]表示[i, j]的需要打印的最小次数
        int[][] f = new int[n][n];
        for (int i = n - 1; i >= 0; -- i) {
            f[i][i] = 1; // 边界条件
            for (int j = i + 1; j < n; ++ j) {
                if (s.charAt(i) == s.charAt(j)) {
                    f[i][j] = f[i][j - 1];
                } else {
                    int min = Integer.MAX_VALUE;
                    for (int k = i; k < j; ++ k) {
                        min = Math.min(min, f[i][k] + f[k + 1][j]);
                    }
                    f[i][j] = min;
                }
            }
        }
        return f[0][n - 1];
    }
}

func strangePrinter(s string) int {
    n := len(s);
    f := make([][]int, n)
    for i := range f {
        f[i] = make([]int, n)
    }
    for i := n - 1; i >= 0; i -- {
        f[i][i] = 1
        for j := i + 1; j < n; j ++ {
            if s[i] == s[j] {
                f[i][j] = f[i][j - 1];
            } else {
                f[i][j] = math.MaxInt64
                for k := i; k < j; k ++ {
                    f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j])
                }
            }
        }
    }
    return f[0][n - 1];
}

func min (a, b int) int {
    if a > b {
        return b
    }
    return a
}

两数相除⭐

⚡ 二分 & 快速乘

class Solution {
    public int divide(int dividend, int divisor) {
        boolean sign = true;
        long x = dividend, y = divisor;
        if ((x > 0 && y < 0) || (x < 0 && y > 0))
            sign = false;
        if (x < 0) x = -x;
        if (y < 0) y = -y;
        long l = 0, r = x;
        while (l < r) {
            long mid = (l + r + 1) >> 1;
            if (mul(mid, y) > x) r = mid - 1;
            else l = mid;
        }
        l *= sign == true ? 1 : -1;
        // 越界处理
        if (l > Integer.MAX_VALUE || l < Integer.MIN_VALUE) l = Integer.MAX_VALUE;
        return (int)l;
    }

    // 快速乘模板
    private long mul (long a, long k) {
        long ans = 0;
        while (k > 0) {
            if ((k & 1) == 1) ans += a;
            k >>= 1;
            a += a;
        }
        return ans;
    }
}

在排序数组中查找元素的第一个和最后一个位置⭐

⚡ 二分 & 细节

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int n = nums.length;
        int left = binarySort(nums, target, true);
        int right = binarySort(nums, target, false) - 1;
        if (left <= right && right < n && nums[left] == target && nums[right] == target)
            return new int[]{left, right};
        return new int[]{-1, -1};
    }

    private int binarySort (int[] nums, int tar, boolean flag) {
        int l = 0, r = nums.length - 1;
        int ans = nums.length; // 关键
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (nums[mid] > tar || (flag && nums[mid] == tar)) {
                r = mid - 1;
                ans = mid;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }
}

搜索插入位置

⚡ 二分 - 模板题

class Solution {
    public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        int l = 0, r = n - 1;
        int ans = n;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (nums[mid] >= target) {
                r = mid - 1;
                ans = mid;
            }
            else l = mid + 1;
        }
        return ans;
    }
}

外观数列

⚡ 递归

class Solution {
    public String countAndSay(int n) {
        if (n == 1) return "1"; 
        String s = countAndSay(n - 1);
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < s.length();) {
            int count = 1;
            while (i + 1 < s.length() && s.charAt(i) == s.charAt(i + 1)) {
                ++ count;
                ++ i;
            }
            str.append(count).append(s.charAt(i));
            ++ i;
        }
        return str.toString();
    }
}

LRU缓存机制⭐

⚡ LinkedHashMap

class LRUCache extends LinkedHashMap<Integer, Integer> {
    int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true); // true表示按照访问顺序
        this.capacity = capacity;
    }

    public void put (int key, int val) {
        super.put(key, val);
    }

    public int get (int key) {
        return getOrDefault(key, -1);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > capacity;
    }
}

⚡ 双链表 & HashMap⭐⭐

class LRUCache {
    int size;
    int capacity;
    DLinkedNode head;
    DLinkedNode tail;
    HashMap<Integer, DLinkedNode> cache;

    public LRUCache(int capacity) {
        size = 0;
        this.capacity = capacity;
        cache = new HashMap<>();
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) return -1;
        else {
            moveToHead(node);
            return node.val;
        }
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            DLinkedNode insertNode = new DLinkedNode(key, value);
            InsertHead(insertNode);
            cache.put(key, insertNode);
            ++ size;
            if (size > capacity) {
                DLinkedNode delNode = removeTail();
                cache.remove(delNode.key);
                -- size;
            }
        } else {
            node.val = value;
            moveToHead(node);
        }
    }

    // 移除节点node
    public void removeNode (DLinkedNode node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    // 插入到双链表头部
    public void InsertHead (DLinkedNode node) {
        node.pre = head;
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
    }

    // 移动node到链表头部
    public void moveToHead (DLinkedNode node) {
        removeNode(node);
        InsertHead(node);
    }

    // 移除到链表尾部节点
    public DLinkedNode removeTail () {
        DLinkedNode node = tail.pre;
        removeNode(node);
        return node;
    }

    // 双链表节点定义
    class DLinkedNode {
        int key;
        int val;
        DLinkedNode pre;
        DLinkedNode next;
        public DLinkedNode () {};
        public DLinkedNode (int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
}

全排列

⚡ 回溯

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        dfs(nums, 0, list, ans);
        return ans;
    }

    private void dfs (int[] nums, int idx, List<Integer> list, List<List<Integer>> ans) {
        if (idx == nums.length) {
            ans.add(new ArrayList<>(list));
            return;
        }
        for (int i = idx; i < nums.length; ++ i) { 
            list.add(nums[i]);
            swap(nums, idx, i);
            dfs(nums, idx + 1, list, ans);
            list.remove(list.size() - 1);
            swap(nums, idx, i);
        }
    }

    private void swap (int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

⚡ 回溯优化

class Solution {
    boolean[] visited;
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        visited = new boolean[nums.length];
        dfs(nums, list, ans);
        return ans;
    }

    private void dfs (int[] nums, List<Integer> list, List<List<Integer>> ans) {
        if (list.size() == nums.length) {
            ans.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; ++ i) {
            if (visited[i]) continue;
            list.add(nums[i]);
            visited[i] = true;
            dfs(nums, list, ans);
            list.remove(list.size() - 1);
            visited[i] = false;
        }
    }
}

全排列II⭐

⚡ 回溯

class Solution {
    boolean[] visited;
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        visited = new boolean[nums.length];
        dfs(nums, list, ans);
        return ans;
    }

    private void dfs (int[] nums, List<Integer> list, List<List<Integer>> ans) {
        if (list.size() == nums.length) {
            ans.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; ++ i) {
            if (visited[i] || (i != 0 && nums[i] == nums[i - 1] && !visited[i - 1])) // 关键
                continue;
            list.add(nums[i]);
            visited[i] = true;
            dfs(nums, list, ans);
            list.remove(list.size() - 1);
            visited[i] = false;
        }
    }
}

5月23日

与数组中元素的最大异或值

⚡ Trie树

class Solution {
    public int[] maximizeXor(int[] nums, int[][] queries) {
        int len = queries.length;
        int n = nums.length;
        int[][] queriesCopy = new int[len][3];
        for (int i = 0; i < len ; ++ i) {
            queriesCopy[i][0] = queries[i][0];
            queriesCopy[i][1] = queries[i][1];
            queriesCopy[i][2] = i;
        }
        Arrays.sort(queriesCopy, (x, y) -> x[1] - y[1]);
        Arrays.sort(nums);

        int[] ans =  new int[len];
        Trie trie = new Trie();
        int idx = 0;
        for (int[] query : queriesCopy) {
            while (idx < n && nums[idx] <= query[1]) {
                trie.insert(nums[idx ++]);
            }
            if (idx == 0) { // 字典树为空
                ans[query[2]] = -1;
            } else {
                ans[query[2]] = trie.getXorMax(query[0]);
            }
        }
        return ans;
    }
}

class Trie {
    TrieNode root;
    public Trie () {
        root = new TrieNode();
    }

    // 插入
    public void insert (int x) {
        TrieNode cur = root;
        for (int i = 30; i >= 0; -- i) {
            int tmp = (x >> i) & 1; 
            if (cur.sub[tmp] == null) {
                cur.sub[tmp] = new TrieNode();
            }
            cur = cur.sub[tmp];
        }
    }

    // 求x最大异或值
    public int getXorMax (int x) {
        TrieNode cur = root;
        int ans = 0;
        for (int i = 30; i >= 0; -- i) {
            int tmp = (x >> i) & 1;
            if (cur.sub[tmp ^ 1] != null) {
                ans = ans * 2 + 1;
                cur = cur.sub[tmp ^ 1];
            } else {
                ans = ans * 2;
                cur = cur.sub[tmp];
            }
        }
        return ans;
    }

    class TrieNode {
        TrieNode[] sub = new TrieNode[2];
    }
}

⚡ 加入限制的Trie树

class Solution {
    public int[] maximizeXor(int[] nums, int[][] queries) {
        int len = queries.length;
        int n = nums.length;
        Trie trie = new Trie();
        for (int num : nums) {
            trie.insert(num);
        }
        int[] ans = new int[len];
        for (int i = 0; i < len; ++ i) {
            ans[i] =  trie.getXorMaxWithLimit(queries[i][0], queries[i][1]);
        }
        return ans;
    }
}

class Trie {
    TrieNode root;
    public Trie () {
        root = new TrieNode();
    }

    // 插入
    public void insert (int x) {
        TrieNode cur = root;
        cur.min = Math.min(cur.min, x);
        for (int i = 30; i >= 0; -- i) {
            int tmp = (x >> i) & 1; 
            if (cur.sub[tmp] == null) {
                cur.sub[tmp] = new TrieNode();
            }
            cur = cur.sub[tmp];
            cur.min = Math.min(cur.min, x);
        }
    }

    // 求x最大异或值 加入限制
    public int getXorMaxWithLimit (int x, int m) {
        TrieNode cur = root;
        if (m < cur.min) return -1;
        int ans = 0;
        for (int i = 30; i >= 0; -- i) {
            int tmp = (x >> i) & 1;
            if (cur.sub[tmp ^ 1] != null && cur.sub[tmp ^ 1].min <= m) {
                ans = ans * 2 + 1;
                cur = cur.sub[tmp ^ 1];
            } else {
                ans = ans * 2;
                cur = cur.sub[tmp];
            }
        }
        return ans;
    }

    class TrieNode {
        TrieNode[] sub = new TrieNode[2];
        int min;
        public TrieNode() {
            min = Integer.MAX_VALUE;
        }
    }
}

类似题型: 数组中两个数的最大异或值

5月22日🥗

黑板异或游戏

⚡ 数学

class Solution {
    public boolean xorGame(int[] nums) {
        if (nums.length % 2 == 0) return true;
        int xor = 0;
        for (int num : nums) xor ^= num;
        return xor == 0;
    }
}

• 当且仅当以下两个条件至少满足一个时，Alice 必胜：
  • 数组 nums 的全部元素的异或结果等于 0；
  • 数组 nums 的长度是偶数。

电话号码的字母组合

⚡ 回溯

class Solution {
    String[] numbers = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<>();
        if (digits.length() == 0) return ans;
        StringBuilder str  = new StringBuilder();
        dfs(digits, 0, str, ans);
        return ans;
    }

    private void dfs (String digits, int idx, StringBuilder str, List<String> list) {
        if (idx >= digits.length()) {
            list.add(str.toString());
            return;
        }
        String s = numbers[digits.charAt(idx) - '2'];
        for (int i = 0; i < s.length(); ++ i) {
            str.append(s.charAt(i));
            dfs (digits, idx + 1, str, list);
            str.deleteCharAt(str.length() - 1);
        }
    }
}

括号生成

⚡ 回溯

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        backtrack(new StringBuilder(), ans, 0, 0, n);
        return ans;
    }

    private void backtrack (StringBuilder str, List<String> list, int open, int close, int n) {
        if (str.length() == n * 2) {
            list.add(str.toString());
            return;
        }
        if (open < n) {
            str.append("(");
            backtrack (str, list, open + 1, close, n);
            str.deleteCharAt(str.length() - 1);
        }
        if (close < open) {
            str.append(")");
            backtrack (str, list, open, close + 1, n);
            str.deleteCharAt(str.length() - 1);
        }
    }
}

Pow(x, n)⭐⭐

⚡ 快速幂 - 模板题

class Solution {
    public double myPow(double x, int n) {
        double ans = 1.0;
        long b = (long) n;
        if (n < 0) {
            x = 1 / x;
            b = -b;
        }
        while (b != 0) {
            if ((b & 1) == 1) ans *= x;
            x *= x;
            b >>= 1;
        }
        return ans;
    }
}

合并K个升序链表⭐

⚡ 分治归并

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        return merge(lists, 0, lists.length - 1);
    }

    private ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummyNode = new ListNode();
        ListNode tail = dummyNode;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }
        tail.next = list1 == null ? list2 : list1;
        return dummyNode.next;
    }

    private ListNode merge (ListNode[] lists, int l, int r) {
        if (l == r) return lists[r];
        int mid = (l + r) / 2;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }
}

⚡ 优先队列

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>((x, y) -> x.val - y.val);
        for (ListNode list : lists) {
            if (list != null) pq.offer(list);
        }
        ListNode dummyNode = new ListNode();
        ListNode tail = dummyNode;
        while (!pq.isEmpty()) {
            tail.next = pq.poll();
            tail = tail.next;
            if (tail.next != null) {
                pq.offer(tail.next);
            }
        }
        return dummyNode.next;
    }
}

两两交换链表中的节点

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyNode = new ListNode();
        dummyNode.next = head;
        ListNode pre = dummyNode, p = head;

        while (p != null && p.next != null) {
            ListNode tmp = p.next;
            p.next = tmp.next;
            tmp.next = p;
            pre.next = tmp;
            pre = p;
            p = p.next;
        }
        return dummyNode.next;
    }
}

K个一组翻转链表⭐

⚡ 链表操作

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummyNode = new ListNode();
        dummyNode.next = head;
        ListNode pre = dummyNode, tail = head;

        while (tail != null) {
            for (int i = 1; i < k; ++ i) {
                tail = tail.next;
                if (tail == null) return dummyNode.next;
            }
            ListNode tmpNode = tail.next;
            // 反转链表
            ListNode[] nodes = reverse(head, tail);
            // 接入原链表中
            pre.next = nodes[0];
            nodes[1].next = tmpNode;
            pre = nodes[1];
            head = tail = tmpNode;
        }
        return dummyNode.next;
    }

    // 反转链表
    public ListNode[] reverse (ListNode head, ListNode tail) {
        ListNode prev = tail.next, p = head;
        while (p != tail) {
            ListNode tmp = p.next;
            p.next = prev;
            tail.next = p;
            prev = p;
            p = tmp;
        }
        return new ListNode[]{tail, head};
    }
}

5月21日🥗

不相交的线⭐

⚡ 动规-经典问题

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; ++ i) {
            for (int j = 1; j <= n; ++ j) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}

经典问题：最长公共子序列

Z字形变换

⚡ 规律

class Solution {
    public String convert(String s, int numRows) {
        int start = 0, jump = 0;
        int space = 0;
        int n = s.length();
        if (numRows == 1) jump = 1;
        else jump = (numRows - 1) * 2;
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < numRows; ++ i) {
            for (int j = i; j < n; j += jump) {
                str.append(s.charAt(j));
                if (space != jump && space != 0 && (j + jump - space) < n) str.append(s.charAt(j + jump - space));
            }
            space += 2;
        }
        return str.toString();
    }
}

字符串转换整数(atoi)⭐

⚡ 自动机

class Solution {
    public int myAtoi(String s) {
        Automaton auto = new Automaton();
        for (int i = 0; i < s.length(); ++ i) {
            auto.get(s.charAt(i));
        }
        return (int)(auto.sign * auto.ans);
    }
}

class Automaton {
    public int sign;
    public long ans;
    private String state;
    private HashMap<String, String[]> table;

    public Automaton () {
        ans = 0;
        sign = 1;
        state = "start";
        table = new HashMap<>(){{
            put("start", new String[]{"start", "signed", "in_number", "end"});
            put("signed", new String[]{"end", "end", "in_number", "end"});
            put("in_number", new String[]{"end", "end", "in_number", "end"});
            put("end", new String[]{"end", "end", "end", "end"});
        }};
    }

    public void get (char c) {
        state = table.get(state)[get_col(c)]; // 转移状态
        if ("in_number".equals(state)) {
            ans = ans * 10 + c - '0';
            ans = sign == 1 ? Math.min(ans, (long)Integer.MAX_VALUE) : Math.min(ans, -(long)Integer.MIN_VALUE);
        } else if ("signed".equals(state)) {
            sign = c == '+' ? 1 : -1;
        }
    }

    private int get_col (char c) {
        if (c == ' ')  return 0;
        else if (c == '+' || c == '-') return 1;
        else if (Character.isDigit(c)) return 2;
        else return 3;
    }
}

盛最多水的容器

⚡ 双指针

class Solution {
    public int maxArea(int[] height) {
        int l = 0, r = height.length - 1;
        int ans = 0;
        while (l < r) {
            int area = (r - l) * Math.min(height[l], height[r]);
            ans = Math.max(ans, area);
            if (height[l] <= height[r]) ++ l;
            else -- r;
        }
        return ans;
    }
}

最接近的三数之和⭐

⚡ 双指针

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        int ans = 10010;
        for (int i = 0; i < n; ++ i) {
            if (i != 0 && nums[i] == nums[i - 1])
                continue;
            int j = i + 1, k = n - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == target) return sum;
                if (Math.abs(sum - target) < Math.abs(ans - target)) {
                    ans = sum;
                }
                if (sum < target) {
                    int j0 = j + 1;
                    while (j0 < k && nums[j0] == nums[j]) ++ j0;
                    j = j0;
                } else if (sum > target) {
                    int k0 = k - 1;
                    while (k0 > j && nums[k0] == nums[k]) -- k0;
                    k = k0;
                }
            }
        }
        return ans;
    }
}

类似题型：详见5月11日

5月20日

前K个高频单词

⚡ 哈希表 & 排序

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        int n = words.length;
        HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i < n; ++ i) {
            map.put(words[i], map.getOrDefault(words[i], 0) + 1);
        }
        List<String> list = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            list.add(entry.getKey());
        }
        Collections.sort(list, (x, y) -> {
            int numy = map.get(y), numx = map.get(x);
            if (numx == numy) return x.compareTo(y);
            else return numy - numx;

        });
        return list.subList(0, k);
    }
}

⚡ 优先队列

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        int n = words.length;
        HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i < n; ++ i) {
            map.put(words[i], map.getOrDefault(words[i], 0) + 1);
        }

        PriorityQueue<String> pq = new PriorityQueue<>((x, y) -> {
            int numy = map.get(y), numx = map.get(x);
            if (numx == numy) return y.compareTo(x);
            else return numx - numy; 
        });
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            pq.offer(entry.getKey());
            if (pq.size() > k) {
                pq.poll();
            }
        }
        List<String> list = new ArrayList<>();
        while (!pq.isEmpty()) {
            list.add(pq.poll());
        }
        Collections.reverse(list);
        return list;
    }
}

5月19日

找出第K大的异或坐标值

⚡ 二维前缀和 & 排序

class Solution {
    public int kthLargestValue(int[][] matrix, int k) {
        int m = matrix.length, n = matrix[0].length;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < m; ++ i) {
            for (int j = 0; j < n; ++ j) {
                if (j != 0)
                    matrix[i][j] ^= matrix[i][j - 1];
                if (i != 0)
                    matrix[i][j] ^= matrix[i - 1][j];
                if (i != 0 && j != 0)
                    matrix[i][j] ^= matrix[i - 1][j - 1];
                list.add(matrix[i][j]);
            }
        }
        Collections.sort(list, (x, y) -> y - x);
        return list.get(k - 1);
    }
}

5月18日🥗

形成两个异或相等数组的三元组数目

⚡ 双循环

class Solution {
    public int countTriplets(int[] arr) {
        int n  = arr.length;
        int[] pre = new int[n + 1];
        pre[0] = 0;
        for (int i = 1; i <= n; ++ i) {
            pre[i] = pre[i - 1] ^ arr[i - 1];
        }
        int ans = 0;
        for (int i = 0; i < n; ++ i) {
            for (int k = i + 1; k < n; ++ k) {
                    if (pre[i] == pre[k + 1]) ans += k - i;
            }
        }
        return ans;
    }
}

⚡ 哈希表单循环

class Solution {
    public int countTriplets(int[] arr) {
        int n  = arr.length;
        int[] pre = new int[n + 1];
        pre[0] = 0;
        for (int i = 1; i <= n; ++ i) {
            pre[i] = pre[i - 1] ^ arr[i - 1];
        }
        HashMap<Integer, Integer> cnt = new HashMap<>();
        HashMap<Integer, Integer> total = new HashMap<>();
        int ans = 0;
        for (int i = 0; i < n ; ++ i) {
            if (cnt.containsKey(pre[i + 1])) {
                ans += total.get(pre[i + 1]) * i - cnt.get(pre[i + 1]);
            }
            cnt.put(pre[i], cnt.getOrDefault(pre[i], 0) + i);
            total.put(pre[i], total.getOrDefault(pre[i], 0) + 1);
        }
        return ans;
    }
}

最大矩形⭐

⚡ 单调栈

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length; 
        if (m == 0) return 0;
        int n = matrix[0].length;
        int[][] sum = new int[m][n];
        int[] u = new int[m];
        for (int i = 0; i < n; ++ i) {
            sum[0][i] = matrix[0][i] - '0';
        }
        u[0] = calc(sum[0]);
        for (int i = 1; i < m; ++ i) {
            for (int j = 0; j < n; ++ j) {
                if (matrix[i][j] - '0' == 1) sum[i][j] = sum[i - 1][j] + 1;
                else sum[i][j] = 0;
            }
            u[i] = Math.max(u[i - 1], calc(sum[i]));
        }
        return u[m - 1];

    }

    // 求直方图最大矩形
    private int calc (int[] nums) {
        int n = nums.length;
        Deque<Integer> stack = new LinkedList<>();
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(left, -1);
        Arrays.fill(right, n);
        for (int i = 0; i < n; ++ i) {
            while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
                right[stack.pop()] = i;
            }
            stack.push(i);
        }

        stack.clear();
        for (int i = n - 1; i >= 0; -- i) {
            while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
                left[stack.pop()] = i;
            }
            stack.push(i);
        }

        int ans = 0;
        for (int i = 0; i < n; ++ i) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * nums[i]);
        }
        System.out.println(ans);
        return ans;
    }
}

扩展题型: AcWing每日一题夏季 - 3516.最大面积

计算右侧小于当前元素的个数⭐

⚡ 归并

class Solution {
    int[] ans;
    int[] index;
    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        index = new int[n];
        ans = new int[n];
        for (int i = 0; i < n; ++ i) index[i] = i;
        mergeSort(nums, 0, n - 1);

        List<Integer> list = new ArrayList<>(n);
        for (int a : ans) list.add(a);
        return list;
    }

    private void mergeSort(int[] nums, int l, int r) {
        if (l >= r) return;
        int n = nums.length;
        int mid = (l + r) >> 1;

        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);

        int[] tmp = new int[r - l + 1];
        int[] tmpIdx = new int[r - l + 1];
        int idx = 0;
        int i = l, j = mid + 1;
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) {
                tmp[idx] = nums[i];
                tmpIdx[idx] = index[i]; // 关键
                ans[index[i]] += j - (mid + 1); // 关键
                ++ i;

            } else {
                tmp[idx] = nums[j];
                tmpIdx[idx] = index[j];
                ++ j;
            }
            ++ idx;
        }
        for (int k = i; k <= mid; ++ k) {
            tmp[idx] = nums[k];
            tmpIdx[idx] = index[k];
            ans[index[k]] += j - (mid + 1);
            ++ idx;
        }
        for (int k = j; k <= r; ++ k) {
            tmp[idx] = nums[k];
            tmpIdx[idx] = index[k];
            ++ idx;
        }
        // 修改原数组和位置数组
        for (int k = l; k <= r; ++ k) {
            nums[k] = tmp[k - l];
            index[k] = tmpIdx[k - l];
        }
    }
}

类似题型：数组中的逆序对

5月17日

二叉树的堂兄弟节点

class Solution {
    int x;
    int xLevel;
    TreeNode xFather;

    int y;
    int yLevel;
    TreeNode yFather;

    public boolean isCousins(TreeNode root, int x, int y) {
        this.x = x;
        this.y = y;
        xLevel = -1;
        yLevel = -1;
        xFather = null;
        yFather = null;

        dfs (root, 0, null);
        if (xLevel == yLevel && xFather != yFather) return true;
        else return false;
    }
    private void dfs (TreeNode node, int level, TreeNode father) {
        if ((xFather != null && yFather != null) || node == null) return;
        if (node.val == x) {
            xFather = father;
            xLevel = level;
        } else if (node.val == y) {
            yFather = father;
            yLevel = level;
        }
        dfs(node.left, level + 1, node);
        dfs(node.right, level + 1, node);
    }
}

5月16日🥗

数组中两个数的最大异或值⭐

⚡ Tire

class Solution {
    public int findMaximumXOR(int[] nums) {
        Trie trie = new Trie();
        int ans = 0;
        for (int num : nums) {
            trie.insert(num);
            ans = Math.max(ans, trie.get(num));
        }
        return ans;
    }
}

/**
 * Description: Tire树结点定义
 */
class TrieNode {
    TrieNode[] sub = new TrieNode[2];
}

/**
 * Description: 字典树
 */
class Trie{
    TrieNode root;
    public Trie(){
        root = new TrieNode();
    }

    // 插入
    public void insert(int x){
        TrieNode cur = root;
        for(int i = 30; i >= 0; i--){
            int d = (x >> i) & 1;
            if(cur.sub[d] == null){
                cur.sub[d] = new TrieNode();
            }
            cur = cur.sub[d];
        }
    }

    //获得 x 的最大异或值
    public int get(int x){
        int sum = 0;
        TrieNode cur = root;
        for(int i = 30; i >= 0; i--){
            int d = (x >> i) & 1;
            if(cur.sub[d ^ 1] != null){
                sum = sum * 2 + 1;
                cur = cur.sub[d ^ 1];
            }else if(cur.sub[d] != null){
                sum = sum * 2;
                cur = cur.sub[d];
            }
        }
        return sum;
    }
}

5月15日

罗马数字转整数

class Solution {
    public int romanToInt(String s) {
        HashMap<Character, Integer> map = new HashMap<>(){{
            put('I', 1);
            put('V', 5);
            put('X', 10);
            put('L', 50);
            put('C', 100);
            put('D', 500);
            put('M', 1000);
        }};
        int ans = 0;
        int n = s.length();
        for(int i = 0; i < n; ++ i) {
            int value = map.get(s.charAt(i));
            if (i < n - 1 && value < map.get(s.charAt(i + 1))) {
                ans -= value;
            } else {
                ans += value;
            }
        }
        return ans;
    }
}

5月14日

整数转罗马数字

⚡ 硬编码数字

class Solution {
    public String intToRoman(int num) {
        String[] thousands = {"","M","MM","MMM"};
        String[] hundreds = {"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"};
        String[] tens = {"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"};
        String[] ones = {"","I","II","III","IV","V","VI","VII","VIII","IX"};

        StringBuilder str = new StringBuilder();
        str.append(thousands[num / 1000]);
        str.append(hundreds[(num % 1000) / 100]);
        str.append(tens[num % 100 / 10]);
        str.append(ones[num % 10]);
        return str.toString();
    }
}

5月13日🥗

停在原地的方案数

⚡ 动态规划

class Solution {
    public int numWays(int steps, int arrLen) {
        int mod = (int)(1e9 + 7);
        // dp[i][j]表示i步跳到j处的方案数
        int size  = Math.min(steps, arrLen);
        long[][] dp = new long[steps + 1][size + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= steps; ++ i) {
            dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % mod;
            for (int j = 1; j < size; ++ j) {
                dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod;
            }
        }
        return (int)dp[steps][0];
    }
}

⚡ 剪枝 & 数组优化

class Solution {
    public int numWays(int steps, int arrLen) {
        int mod = (int)(1e9 + 7);
        // dp[i][j]表示i步跳到j处的方案数
        int size  = Math.min(steps, arrLen);
        int[][] dp = new int[steps + 1][size + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= steps; ++ i) {
            int edge = Math.min(i + 1, size); // 剪枝
            dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % mod;
            for (int j = 1; j < edge; ++ j) {
                dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % mod;
                dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % mod;
            }
        }
        return dp[steps][0];
    }
}

5月12日

子数组异或查询

⚡ 前缀和

class Solution {
    public int[] xorQueries(int[] arr, int[][] queries) {
        int n = queries.length;
        int[] ans = new int[n];
        int[] pre = new int[arr.length + 1];
        for (int i = 1; i <= arr.length; ++ i) {
            pre[i] = pre[i - 1] ^ arr[i - 1];
        }
        for (int i = 0; i < n; ++ i) {
            ans[i] = pre[queries[i][1] + 1] ^ pre[queries[i][0]];
        }
        return ans;
    }
}

5月11日🥗

解码异或后的排列

class Solution {
    public int[] decode(int[] encoded) {
        int n = encoded.length;
        int total = 0, odd = 0;
        for (int i = 1; i <= n + 1; ++ i) total ^= i; // 求原数组异或和
        for (int i = 1; i < n; i += 2) odd ^= encoded[i]; // 求原数组除了perm[0]元素之外的异或和

        int[] perm = new int[n + 1];
        perm[0] = total ^ odd;
        for (int i = 1; i <= n; ++ i) {
            perm[i] = encoded[i - 1] ^ perm[i - 1];
        }
        return perm;
    }
}

注：类似题型5月6日每日一题

- - - 回溯小专题 - - -

寻找目标值序列

⚡ 回溯

import java.util.ArrayList;
import java.util.List;

/**
 * @author Javid Xi
 * @Classname FindTargetList
 * @Description 已知一个无序数组 array，元素均为正整数。给定一个目标值 target，输出数组中是否存在若干元素的组合，相加为目标值。
 * @Date 2021/5/11
 */
public class FindTargetList {

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        int[] arr = {1,2,7,3,6,5,4};
        find(arr, 12, 0, 0, list);

    }

    /**
     * Description: 回溯
     */
    public static void find(int[] arr, int tar, int idx, int total, List<Integer> list){
        if(idx == arr.length) return;

        list.add(idx);
        if(total + arr[idx] == tar)
            System.out.println(list);
        else
            find(arr, tar, idx + 1, total + arr[idx], list);

        list.remove(list.size() - 1);
        find(arr, tar, idx + 1, total, list);
    }
}

组合总和

⚡ 回溯

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<>();
        backTrack(candidates, target, list, ans, 0);
        return ans;
    }

    private void backTrack (int[] candidates, int target, List<Integer> list, List<List<Integer>> ans, int idx) {
        ///if (target <= 0) return;
        for (int i = idx; i < candidates.length; ++ i) {
            list.add(candidates[i]);
            if (candidates[i] == target) {
                // 这里不可直接传 list 因为其传递为引用传递 list 中数据的改变会影响到 ans 中的数据
                // 因此需要传入 list 的复制
                ans.add(new ArrayList<Integer>(list));
            } else if (candidates[i] < target) {
                backTrack(candidates, target - candidates[i], list, ans, i);
            }
            list.remove(list.size() - 1);
        }
    }
}

组合总和II

⚡ 回溯 & 剪枝

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        backTrack(candidates, target, 0, list, ans);
        return ans;
    }

    private void backTrack (int[] candidates, int target, int idx, List<Integer> list, List<List<Integer>> ans) {
        for (int i = idx; i < candidates.length; ++ i) {
            if (i != idx && candidates[i] == candidates[i - 1]) continue;
            list.add(candidates[i]);
            if (candidates[i] == target) {
                    ans.add(new ArrayList<>(list));
            } else if (candidates[i] < target) {
                backTrack(candidates, target - candidates[i], i + 1, list, ans);
            } else {
                // 剪枝
                list.remove(list.size() - 1);
                break;
            }
            list.remove(list.size() - 1);
        }
    }
}

组合总和III

⚡ 回溯

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        backTrack(k, n, 1, list, ans);
        return ans;
    }

    private void backTrack (int k, int n, int idx, List<Integer> list, List<List<Integer>> ans) {
        for (int i = idx; i < 10; ++ i) {
            list.add(i);
            k--;
            if (i == n && k == 0) {
                ans.add(new ArrayList<>(list));
            } else if (i < n){
                backTrack(k, n - i, i + 1, list, ans);
            }
            list.remove(list.size() - 1);
            k++;
        }
    }
}

组合总和Ⅳ

⚡ 动态规划

class Solution {
    public int combinationSum4(int[] nums, int target) {
        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];
    }
}

注：回溯会超时

三数之和

⚡ 双指针O(n2)

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> ans = new ArrayList<>();
        // 枚举 a
        for (int first = 0; first < n; ++ first) {
            if (first != 0 && nums[first] == nums[first - 1]) continue;
            int third = n - 1;
            int target = -nums[first];
            // 枚举 b
            for (int second = first + 1; second < n; ++ second) {
                if (second != first + 1 && nums[second] == nums[second - 1])
                    continue;
                while (second < third && nums[second] + nums[third] > target) {
                    -- third;
                }
                if (second == third) break;
                if (nums[second] + nums[third] == target) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    ans.add(list);
                }
            }
        }
        return ans;
    }
}

注：回溯O(n3)会超时

较小的三数之和

⚡ 双指针O(n2)

class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        int ans = 0;
        // 枚举 a
        for (int first = 0; first < n; ++ first) {
            int third = n - 1;
            int tar = target - nums[first];
            // 枚举 b
            for (int second = first + 1; second < n; ++ second) {
                while (second < third && nums[second] + nums[third] >= tar) {
                    -- third;
                }
                if (second == third) break;
                ans += third - second;
            }
        }
        return ans;
    }
}

四数之和

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> ans = new ArrayList<>();
        // 枚举 a
        for (int first = 0; first < n; ++ first) {
            if (first != 0 && nums[first] == nums[first - 1])
                continue;
            // 枚举 b
            for (int second = first + 1; second < n; ++ second) {
                if (second != first + 1 && nums[second] == nums[second - 1])
                    continue;
                int fouth = n - 1;
                int tar = target - nums[first] - nums[second];
                // 枚举 c
                for (int third = second + 1; third < n; ++ third) {
                    if (third != second + 1 && nums[third] == nums[third - 1])
                        continue;
                    while (third < fouth && nums[third] + nums[fouth] > tar) {
                        -- fouth;
                    }
                    if (fouth == third) break;
                    if (nums[fouth] + nums[third] == tar) {
                        ans.add(Arrays.asList(nums[first], nums[second], nums[third], nums[fouth]));
                    }
                }
            }
        }
        return ans;
    }
}

注：

• Arrays.asList() 该方法是将数组转化成List集合的方法。
  1. 该方法适用于对象型数据的数组（String、Integer...）；
  2. 该方法不建议使用于基本数据类型的数组（byte,short,int,long,float,double,boolean）；
  3. 该方法将数组与List列表链接起来：当更新其一个时，另一个自动更新；
  4. 不支持add()、remove()、clear()等方法；
  5. 用此方法得到的List的长度是不可改变的。
• 总结：
  • 如果List只是用来遍历，就用Arrays.asList()；
  • 如果List还要添加或删除元素，就new一个java.util.ArrayList，然后一个一个地添加元素。

5月10日

叶子相似的树

⚡ 递归

class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        dfs(root1, list1);
        dfs(root2, list2);
        return list1.equals(list2);
    }
    private void dfs (TreeNode node, List<Integer> list) {
        if (node == null) return;
        if (node.left == null && node.right == null) {
            list.add(node.val);
        }
        dfs(node.left, list);
        dfs(node.right, list);
    }
}

⚡ 迭代

class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        return iterate(root1).equals(iterate(root2));
    }

    private List<Integer> iterate (TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> s = new LinkedList<>();
        s.push(root);
        while (!s.isEmpty()) {
            TreeNode node = s.pop();
            if (node.left == null && node.right == null) list.add(node.val);
            if (node.left != null) s.push(node.left);
            if (node.right != null) s.push(node.right);
        }
        return list;
    }
}

5月9日🥗

制作m束花所需的最少天数⭐

⚡ 二分

class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        if (k * m > bloomDay.length) return -1;
        int len = bloomDay.length;
        int low = 1, high = 1;
        for (int i = 0; i < len; i ++) {
            high = Math.max(high, bloomDay[i]);
        }
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (canMake(bloomDay, mid, m, k)) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return high;
    }

    private boolean canMake (int[] bloomDay, int day, int m, int k) {
        int bouquets = 0; // 记录在天数day的限制内能制作的花束
        int len = bloomDay.length;
        int flowers = 0; // 记录花束的数量
        for (int i = 0; i < len; i ++) {
            if (bloomDay[i] <= day) {
                flowers ++;
                if (flowers == k) {
                    bouquets ++;
                    flowers = 0;
                }
            } else flowers = 0;
        }
        return bouquets >= m;
    }
}

下一个更大元素I

⚡ 单调栈

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < nums2.length; ++ i) {
            while (!stack.isEmpty() && nums2[i] > stack.peek())
                hashMap.put(stack.pop(), nums2[i]);
            stack.push(nums2[i]);
        }
        int[] ans = new int[nums1.length];
        for (int i = 0; i < nums1.length; ++ i) {
            ans[i] = hashMap.getOrDefault(nums1[i], -1);
        }
        return ans;
    }
}

下一个更大元素II⭐

⚡ 单调栈

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] ans = new int[nums.length];
        Arrays.fill(ans, -1);
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < 2 * n; ++i) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i % n]) {
                ans[stack.pop()] = nums[i % n];
            }
            stack.push(i % n);
        }
        return ans;
    }
}

5月8日

完成所有工作的最短时间⭐

⚡ DFS & 剪枝

class Solution {
    int jobs[];
    int n, k, ans;
    public int minimumTimeRequired(int[] jobs, int k) {
        this.jobs = jobs;
        this.k = k;
        this.n = jobs.length;
        this.ans = Integer.MAX_VALUE;
        int[] distributions = new int[n];
        dfs(0, 0, distributions, 0);
        return ans;
    }

    /**
     * u: 当前处理的job
     * used: 当前分配给了多少个工人了
     * distributions: 工人的分配情况 distributions[0] = x 代表 0 号工人工作量为 x
     * maxTime: 当前的「最大工作时间」
     */
    private void dfs (int u, int used, int[] distributions, int maxTime) {
        if (maxTime >= ans) return;
        if (u == n) {
            ans = maxTime;
            return;
        }
        // 优先分配给未分配的工人
        // 先找到一个较小ans，便于 maxTime >= ans return剪枝
        if (used < k) {
            distributions[used] = jobs[u];
            dfs(u + 1, used + 1, distributions, Math.max(distributions[used], maxTime));
            distributions[used] = 0;
        }

        for (int i = 0; i < used; ++i) {
            distributions[i] += jobs[u];
            dfs(u + 1, used, distributions, Math.max(distributions[i], maxTime));
            distributions[i] -= jobs[u];
        }
    }
}

5月7日🥗

数组异或操作

⚡ 利用异或性质

class Solution {
    public int xorOperation(int n, int start) {
        int b0 = n & start & 1; // 确定最低位
        int s = start >> 1;
        // 3^4^5^6^7^8^9 = (1^2)^(1^2^3^4^5^6^7^8^9)
        int ans = sumXor(s - 1) ^ sumXor(s + n - 1);
        return ans << 1 | b0;
    }
    // 4i ⊕ (4i+1) ⊕ (4i+2) ⊕ (4i+3) = 0
    private static int sumXor (int x) {
        switch (x % 4) {
            case 0 : return x;
            case 1 : return 1;
            case 2 : return x + 1;
        }
        return 0; 
    }
}

无重复字符的最长子串⭐

⚡ 滑动窗口

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int len = s.length();
        int rk = 0, ans = 0;
        for (int i = 0; i < len; ++i) {
            if (i != 0) set.remove(s.charAt(i - 1));
            while (rk < len && !set.contains(s.charAt(rk))) {
                set.add(s.charAt(rk));
                ++ rk;
            }
            ans = Math.max(ans, rk - i);
        }
        return ans;
    }
}

寻找两个正序数组的中位数⭐⭐

⚡ 二分法

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length, len2 = nums2.length;
        int total = len1 + len2;
        if (total % 2 == 1) {
            return getKthNum(nums1, nums2, total / 2 + 1);
        } else {
            return (getKthNum(nums1, nums2, total / 2 + 1) + getKthNum(nums1, nums2, total / 2)) / 2.0;
        }
    }

    // 二分查找 两数组按顺序 k 位置的数
    private int getKthNum (int[] nums1, int[] nums2, int k) {
        int len1 = nums1.length, len2 = nums2.length;
        int idx1 = 0, idx2 = 0;
        int kElem = 0;
        while (true) {
            // 处理边界情况
            if (idx1 == len1) return nums2[idx2 + k - 1];
            if (idx2 == len2) return nums1[idx1 + k - 1];
            if (k == 1) return Math.min(nums1[idx1], nums2[idx2]);

            int half = k >> 1;
            int newIdx1 = Math.min(idx1 + half, len1) - 1;
            int newIdx2 = Math.min(idx2 + half, len2) - 1;
            int pivot1 = nums1[newIdx1], pivot2 = nums2[newIdx2];
            if (pivot1 <= pivot2) {
                k -= newIdx1 - idx1 + 1;
                idx1 = newIdx1 + 1;
            } else {
                k -= newIdx2 - idx2 + 1;
                idx2 = newIdx2 + 1;
            }
        }
    }
}

5月6日

解码异或后的数组

class Solution {
    public int[] decode(int[] encoded, int first) {
        int n = encoded.length;
        int[] arr = new int[n + 1];
        arr[0] = first;
        for (int i = 0; i < n; ++i) {
            // 异或满足交换律
            arr[i + 1] = arr[i] ^ encoded[i];
        }
        return arr;
    }
}

5月5日

删除并获得点数

⚡ 动态规划

class Solution {
    public int deleteAndEarn(int[] nums) {
        int maxNum = Arrays.stream(nums).max().getAsInt();
        int[] sums = new int[maxNum + 1];
        for (int num : nums) {
            sums[num] += num;
        }

        // 动态规划
        for (int i = 2; i <= maxNum; ++i) {
            sums[i] = Math.max(sums[i - 1], sums[i - 2] + sums[i]);
        }
        return sums[maxNum];
    }
}

⚡ 排序 & 动态规划

class Solution {
    // 将 nums 排序后，将其划分成若干连续子数组，子数组内任意相邻元素之差不超过 1。
    // 对每个子数组按照方法一的动态规划过程计算出结果，累加所有结果即为答案。
    public int deleteAndEarn(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        List<Integer> list = new ArrayList<>();
        list.add(nums[0]);
        int size = 1, ans = 0;
        for (int i = 1; i < n; ++i) {
            if (nums[i] == nums[i - 1]) {
                list.set(size - 1, list.get(size - 1) + nums[i]);
            } else if (nums[i] == nums[i - 1] + 1) {
                list.add(nums[i]);
                ++size;
            } else {
                ans += rob(list);
                list.clear();
                list.add(nums[i]);
                size = 1;
            }
        }
        ans += rob(list);
        return ans;
    }

    private int rob (List<Integer> list) {
        int size = list.size();
        if (size == 1) return list.get(0);
        int first = list.get(0), second = Math.max(first, list.get(1));
        for (int i = 2; i < size; ++i) {
            int tmp = second;
            second = Math.max(first + list.get(i), second);
            first = tmp;
        }
        return second;
    }
}

打家劫舍

5月4日🥗

粉刷房子III

⚡ 三维动态规划

class Solution {
    // 为防止溢出，Integer最大值除2表示无穷大
    static final int INFTY = Integer.MAX_VALUE / 2;

    public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
        //为了叙述方便, 令所有的变量都从 0 开始编号, 即: 
        // 房子的编号为 [0, m-1]
        // 颜色的编号为 [0, n-1] 如果房子没有涂上颜色，那么记为 -1
        // 街区的编号为 [0,target−1]

        // 让房间颜色数从零开始计 -1为未涂色
        for (int i = 0; i < m; ++i) {
            houses[i]--;
        }
        // dp(i,j,k) 表示将 [0, i] 的房子都涂上颜色，最末尾的第 i 个房子的颜色为 j，并且它属于第 k 个街区时，需要的最少花费。
        int[][][] dp = new int[m][n][target];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                Arrays.fill(dp[i][j], INFTY);
            }
        }

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (houses[i] != -1 && houses[i] != j) { // 房间i已被上色且不属于此街区
                    continue;
                }

                for (int k = 0; k < target; ++k) { // 枚举所有街区
                    for (int j0 = 0; j0 < n; ++j0) { // 枚举所有颜色
                        if (j == j0) { // 颜色相同，属于同一个街区
                            if (i == 0) {
                                if (k == 0) {
                                    dp[i][j][k] = 0;
                                }
                            } else {
                                dp[i][j][k] = Math.min(dp[i][j][k], dp[i - 1][j][k]);
                            }
                        }
                        else if (i > 0 && k > 0) {  //颜色不同，不属于同一个街区
                            dp[i][j][k] = Math.min(dp[i][j][k], dp[i - 1][j0][k - 1]);
                        }
                    }
                    // 若dp传递成功，且此房间未被上色
                    if (dp[i][j][k] != INFTY && houses[i] == -1) {
                        dp[i][j][k] += cost[i][j];
                    }
                } 
            }
        }

        int ans = INFTY;
        for (int j = 0; j < n; ++j) {
            ans = Math.min(ans, dp[m - 1][j][target - 1]);
        }
        return ans == INFTY ? -1 : ans;
    }
}

粉刷房子⭐⭐

⚡ DFS(超时)

class Solution {
    private int[][] costs;
    public int minCost(int[][] costs) {
        if (costs.length == 0) return 0;
        this.costs = costs;
        return Math.min (paintCost(0, 0), Math.min(paintCost(0, 1), paintCost(0, 2)));
    }

    private int paintCost (int n, int color) {
        int total = costs[n][color];
        if (n < costs.length - 1) {
            if (color == 0) {
                total += Math.min(paintCost(n + 1, 1), paintCost(n + 1, 2));
            } else if (color == 1) {
                total += Math.min(paintCost(n + 1, 0), paintCost(n + 1, 2));
            } else {
                total += Math.min(paintCost(n + 1, 0), paintCost(n + 1, 1));
            }
        }
        return total;
    }
}

⚡ 记忆化搜索DFS

class Solution {
    private int[][] costs;
    HashMap<String, Integer> hashMap; // 使用HashMap储存已经计算过的total值
    public int minCost(int[][] costs) {
        if (costs.length == 0) return 0;
        this.costs = costs;
        hashMap = new HashMap<>();
        return Math.min (paintCost(0, 0), Math.min(paintCost(0, 1), paintCost(0, 2)));
    }

    private int paintCost (int n, int color) {
        String key = getKey(n, color);
        if (hashMap.containsKey(key)) {
            return hashMap.get(key);
        }
        int total = costs[n][color];
        if (n < costs.length - 1) {
            if (color == 0) {
                total += Math.min(paintCost(n + 1, 1), paintCost(n + 1, 2));
            } else if (color == 1) {
                total += Math.min(paintCost(n + 1, 0), paintCost(n + 1, 2));
            } else {
                total += Math.min(paintCost(n + 1, 0), paintCost(n + 1, 1));
            }
        }
        hashMap.put(key, total);
        return total;
    }

    private String getKey(int n, int color) {
        return String.valueOf(n) + " " + String.valueOf(color);
    }
}

⚡ 动态规划

class Solution {
    // 在原数组上修改
    public int minCost(int[][] costs) {
        int n = costs.length;
        for (int i = 1; i < n; ++i) {
            costs[i][0] += Math.min(costs[i - 1][1], costs[i - 1][2]);
            costs[i][1] += Math.min(costs[i - 1][0], costs[i - 1][2]);
            costs[i][2] += Math.min(costs[i - 1][0], costs[i - 1][1]);
        }
        return Math.min(costs[n - 1][0], Math.min(costs[n - 1][1], costs[n - 1][2]));
    }
}

⚡ 动态规划(空间优化)

class Solution {
    public int minCost(int[][] costs) {
        int n = costs.length;
        int[] preCosts = costs[0];
        for (int i = 1; i < n; ++i) {
            int[] currentCosts = costs[i];
            currentCosts[0] += Math.min(preCosts[1], preCosts[2]);
            currentCosts[1] += Math.min(preCosts[0], preCosts[2]);
            currentCosts[2] += Math.min(preCosts[0], preCosts[1]);
            preCosts = currentCosts;
        }
        return Math.min(preCosts[0], Math.min(preCosts[1], preCosts[2]));
    }
}

二叉搜索树中的插入操作

⚡ 递归

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        recur(root, val);
        return root;
    }
    public void recur(TreeNode root, int val) {
        if (root == null) return;
        if (val > root.val) {
            if (root.right == null) {
                root.right = new TreeNode(val);
                return;
            } else {
                recur(root.right, val);
            }
        }
        else if (val < root.val) {
            if (root.left == null) {
                root.left = new TreeNode(val);
                return;
            } else recur(root.left, val);
        }
    }
}

⚡ 迭代

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        TreeNode pos = root;
        while (pos != null) {
            if (val < pos.val) {
                if (pos.left == null) {
                    pos.left = new TreeNode(val);
                    break;
                } else {
                    pos = pos.left;
                }
            } else {
                if (pos.right == null) {
                    pos.right = new TreeNode(val);
                    break;
                } else {
                    pos = pos.right;
                }
            }
        }
        return root;
    }
}

5月3日

整数反转

class Solution {
    public int reverse(int x) {
        int ans = 0;
        while (x != 0) {
            if (ans > Integer.MAX_VALUE / 10 || ans < Integer.MIN_VALUE / 10) return 0;
            ans = ans * 10 + x % 10; 
            x /= 10;
        }
        return ans;
    }
}

5月2日

砖墙

⚡ 哈希表

class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        int size = wall.size();
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (List<Integer> level : wall) {
            int sum = 0;
            for (int j = 0; j < level.size() - 1; ++j) {
                sum += level.get(j);
                hashMap.put(sum, hashMap.getOrDefault(sum, 0) + 1);
            }
        }

        int max = 0;
        for (Map.Entry<Integer, Integer> entry : hashMap.entrySet()) {
            max = Math.max(max, entry.getValue());
        }
        return size - max;
    }
}

下一个排列⭐

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            --i;
        }
        if (i >= 0) {
            int j = n - 1;
            while (j > i && nums[j] <= nums[i]) {
                --j;
            }
            int tmp = nums[j];
            nums[j] = nums[i];
            nums[i] = tmp;
        }   
        for (int left = i + 1, right = n - 1; left < right; ++left,--right) {
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
        }
    }
}

5月1日

员工的重要性

⚡ 递归

class Solution {
    public int getImportance(List<Employee> employees, int id) {
        int ans = 0;
        for (int i = 0; i < employees.size(); ++i) {
            if (employees.get(i).id == id) {
                ans += employees.get(i).importance;
                for (int num : employees.get(i).subordinates) {
                    ans += getImportance(employees, num);
                }
                break;
            }
        }
        return ans;
    }
}

⚡ 用HashMap加快查找

class Solution {
    HashMap<Integer, Employee> hashMap = new HashMap<>();
    public int getImportance(List<Employee> employees, int id) {
        for (Employee employee : employees) {
            hashMap.put (employee.id, employee);
        }
        return dfs(id);
    }

    public int dfs (int id) {
        Employee employee = hashMap.get(id);
        int total = employee.importance;
        List<Integer> subordinates = employee.subordinates;
        for (int subId : subordinates) {
            total += dfs (subId);
        }
        return total;
    }
}

最长回文子串

⚡ 中心扩散 枚举

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        int n = s.length();
        int start = 0, end = 0;
        for (int i = 0; i < n; ++i) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (end - start < len) {
                start = i - (len - 1) / 2; //仔细体会
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private static int expandAroundCenter (String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            --left;
            ++right;
        }
        return right - left - 1; //仔细体会
    }
}