本文最后更新于2021年10月16日,已超过 1 个月没更新!

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;
    }
}

Try and fail, but don't fail to try.