August

08-03 最短无序连续子数组

🧩 排序+双指针 O(nlogn)

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int[] arr = new int[n];
        System.arraycopy(nums, 0, arr, 0, n);
        Arrays.sort(arr);
        int i = 0, j = n - 1;
        while (i <= j && nums[i] == arr[i]) ++ i;
        while (j >= i && nums[j] == arr[j]) -- j;
        return j + 1 - i;
    }
}

🧩 双指针+线性扫描 O(n)

class Solution {
    int MIN = -100005, MAX = 100005;
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int i = 0, j = n - 1;
        while (i < j && nums[i] <= nums[i + 1]) ++ i;
        while (j > i && nums[j] >= nums[j - 1]) -- j;
        if (i == j) return 0;

        int min = nums[i], max = nums[j];
        int l = i, r = j;
        for (int u = l; u <= r; ++ u) {
            if (nums[u] < min) {
                while (i >= 0 && nums[u] < nums[i]) -- i;
                min = i >= 0 ? nums[i] : MIN;
            }
            if (nums[u] > max) {
                while (j < n && nums[u] > nums[j]) ++ j;
                max = j < n ? nums[j] : MAX;
            }
        }
        return j - i - 1; // (j - 1) - (i + 1) + 1
    }
}

08-02 网络延迟时间⭐⭐

🧩 Dijkstra算法

class Solution {
    private final int INF = Integer.MAX_VALUE / 2;
    public int networkDelayTime(int[][] times, int n, int k) {
        // 预处理
        int[][] g = new int[n][n];
        for (int i = 0; i < n; ++ i) {
            Arrays.fill(g[i], INF);
        }
        for (int[] t : times) {
            int x = t[0] - 1, y = t[1] - 1;
            g[x][y] = t[2];
        }

        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        // 起点
        dist[k - 1] = 0;
        boolean[] used = new boolean[n];
        for (int i = 0; i < n; ++ i) {
            int x = -1;
            // 找出当前距离起始点的最短距离点
            for (int y = 0; y < n; ++ y) {
                if (!used[y] && (x == -1 || dist[y] < dist[x])) {
                    x = y;
                }
            }
            used[x] = true;
            // 使用找到的最短距离点更新其他点
            for (int y = 0; y < n; ++ y) {
                dist[y] = Math.min(dist[y], g[x][y] + dist[x]);
            }
        }
        // 遍历距离dist数组找到最大值
        int ans = Arrays.stream(dist).max().getAsInt();
        return ans == INF ? -1 : ans;
    }
}

08-01 矩阵中战斗力最弱的 K 行

🧩 二分 + 优先队列

class Solution {
    public int[] kWeakestRows(int[][] mat, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> {
            if (x[1] == y[1]) return x[0] - y[0];
            return x[1] - y[1];
        });
        // 二分获取每行战斗力并插入小根堆
        int n = mat.length, m = mat[0].length;
        for (int i = 0; i < n; ++ i) {
            int l = 0, r = m - 1;
            while (l < r) {
                int mid = (l + r + 1) / 2;
                if (mat[i][mid] == 0) r = mid - 1;
                else l = mid;
            }
            if (mat[i][l] == 0) l = -1;
            pq.offer(new int[]{i, l + 1});
        }
        // 小根堆中获取结果
        int[] ans = new int[k];
        for (int i = 0; i < k; ++ i) {
            ans[i] = pq.poll()[0];
        }
        return ans;
    }
}

July

07-28 二叉树中所有距离为 K 的结点

🧩 哈希表

class Solution {
    Map<Integer, TreeNode> parents = new HashMap<>();
    List<Integer> ans = new ArrayList<>();

    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        // 从root出发DFS，记录每个结点的父结点
        findParents(root);
        // 从target节点出发，寻找距离target深度为k的节点
        dfs(target, null, 0, k);
        return ans;
    }

    public void findParents(TreeNode node) {
        if (node.left != null) {
            parents.put(node.left.val, node);
            findParents(node.left);
        }
        if (node.right != null) {
            parents.put(node.right.val, node);
            findParents(node.right);
        }
    }

    public void dfs(TreeNode node, TreeNode from, int level, int k) {
        if (node == null) return;

        if (level == k) {
            ans.add(node.val);
            return;
        }

        if (node.left != from)
            dfs(node.left, node, level + 1, k);
        if (node.right != from)
            dfs(node.right, node, level + 1, k);
        if (parents.get(node.val) != from)
            dfs(parents.get(node.val), node, level + 1, k);
    }
}

07-27 二叉树中第二小的节点

class Solution {
    int ans;
    int rootVal;
    public int findSecondMinimumValue(TreeNode root) {
        ans = -1;
        rootVal = root.val;
        dfs(root);
        return ans;
    }

    private void dfs(TreeNode node) {
        if (node == null) return;
        if (ans != -1 && node.val >= ans) return;

        if  (node.val > rootVal)
            ans = node.val;

        dfs(node.left);
        dfs(node.right);
    }
}

07-25从相邻元素对还原数组⭐

🧩 哈希表

class Solution {
    public int[] restoreArray(int[][] adjacentPairs) {
        // 构造map
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] adjacentPair : adjacentPairs) {
            map.putIfAbsent(adjacentPair[0], new ArrayList<>());
            map.putIfAbsent(adjacentPair[1], new ArrayList<>());
            map.get(adjacentPair[0]).add(adjacentPair[1]);
            map.get(adjacentPair[1]).add(adjacentPair[0]);
        }
        // 得到数组端点
        int n = adjacentPairs.length + 1;
        int[] ret = new int[n];
        for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
            List<Integer> list = entry.getValue();
            if (list.size() == 1) {
                ret[0] = entry.getKey();
                ret[1] = list.get(0);
                break;
            }
        }
        // 构造数组
        for (int i = 2; i < n; ++ i) {
            List<Integer> list = map.get(ret[i - 1]);
            ret[i] = ret[i - 2] == list.get(0) ? list.get(1) : list.get(0);
        }
        return ret;
    }
}

07-24 替换隐藏数字得到的最晚时间

class Solution {
    public String maximumTime(String time) {
        char[] arr = time.toCharArray();

        if (arr[0] == '?')
            arr[0] = (arr[1] >= '4' && arr[1] <= '9') ? '1' : '2';
        if (arr[1] == '?')
            arr[1] = (arr[0] == '2') ? '3' : '9';

        if (arr[3] == '?') arr[3] = '5';
        if (arr[4] == '?') arr[4] = '9';
        return new String(arr);
    }
}

07-23 检查是否区域内所有整数都被覆盖⭐

🧩 差分数组

class Solution {
    public boolean isCovered(int[][] ranges, int left, int right) {
        //  求差分数组
        int[] diff = new int[52];
        for (int[] range : ranges) {
            diff[range[0]] ++ ;
            diff[range[1] + 1] --;
        }

        // 前缀和
        int cur = 0;
        for (int i = 1; i <= 50; ++ i) {
            cur += diff[i];
            if (i >= left && i <= right && cur <= 0)
                return false;
        }
        return true;
    }
}

07-22 复制带随机指针的链表⭐

🧩 回溯

class Solution {
    HashMap<Node, Node> visitedHash = new HashMap<Node, Node>();
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        //检查节点是否已经复制过
        if (this.visitedHash.containsKey(head)) {
            return this.visitedHash.get(head);
        }
        //复制节点
        Node node = new Node (head.val, null, null);
        //放入访问哈希表，比建立键值关系
        this.visitedHash.put(head, node);
        //递归复制其他节点，并将next和random指向新节点
        node.next = copyRandomList(head.next);
        node.random = copyRandomList(head.random);
        //返回复制节点
        return node;
    }
}

07-20 数组中最大数对和的最小值

class Solution {
    public int minPairSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int res = 0;
        for (int i = 0; i < n / 2; ++ i) {
            res = Math.max(nums[i] + nums[n - 1 - i], res);
        }
        return res;
    }
}

07-19 最高频元素的频数

class Solution {
    public int maxFrequency(int[] nums, int k) {
        int n = nums.length;
        Arrays.sort(nums);
        int l = 0, res = 1;
        int total = 0;
        for (int r = 1; r < n; ++ r ) {
            total += (long)(nums[r] - nums[r - 1]) * (r - l);
            while (total > k) {
                total -= nums[r] - nums[l];
                ++ l;
            }
            res = Math.max(res, r - l + 1);
        }
        return res;
    }
}

07-18 变位词组

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] cs = s.toCharArray();
            Arrays.sort(cs);
            String key = new String(cs);
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(s);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

07-15 减小和重新排列数组后的最大元素

class Solution {
    public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
        Arrays.sort(arr);
        int last = 0;
        for (int a : arr) {
            last = Math.min(last + 1, a);
        }
        return last;
    }
}

07-14 绝对差值和⭐

🧩 二分 + 排序

class Solution {
    private final int mod = (int)1e9 + 7;
    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[] rec = new int[n];
        System.arraycopy(nums1, 0, rec, 0, n);
        Arrays.sort(rec);
        int sum = 0, maxn = 0;
        for (int i = 0; i < n; ++ i) {
            int diff = Math.abs(nums1[i] - nums2[i]);
            sum = (sum + diff) % mod;
            int j = binarySearch(rec, nums2[i]);
            if (j < n) maxn = Math.max(maxn, diff - (rec[j] - nums2[i]));
            if (j > 0) maxn = Math.max(maxn, diff - (nums2[i] - rec[j - 1]));
        }
        return (sum - maxn + mod) % mod;
    }

    // 二分找出 >= 目标元素的第一个位置
    private int binarySearch(int[] nums, int tar) {
        int n = nums.length;
        if (nums[n - 1] < tar) return n;

        int l = 0, r = n - 1;
        while (l < r) {
            int mid = (r - l) / 2 + l;
            if (nums[mid] < tar) l = mid + 1;
            else r = mid;
        }
        return l;
    }
}

07-12 H 指数 II

🧩 二分

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (citations[mid] >= n - mid) r = mid - 1;
            else l = mid + 1;
        }
        return n - l;
    }
}

07-11 H 指数

🧩 排序O(logn)

class Solution {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int h = 0, i = citations.length - 1;
        while (i >= 0 && citations[i] > h) {
            ++ h;
            -- i;
        }
        return h;
    }
}

🧩 计数排序O(n)

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int[] arr = new int[n + 1];
        for (int c : citations) {
            if (c >= n) arr[n] ++;
            else arr[c] ++;
        }

        int total = 0;
        for (int i = n; i >= 0; -- i) {
            total += arr[i];
            if (total >= i) return i;
        }
        return 0;
    }
}

07-10 基于时间的键值存储

🧩 哈希 + 二分

class TimeMap {
    class Node {
        String val;
        int time;
        public Node (String val, int time) {
            this.val = val;
            this.time = time;
        }
    }

    /** Initialize your data structure here. */
    Map<String, List<Node>> map;
    public TimeMap() {
        map = new HashMap<String, List<Node>>();
    }

    public void set(String key, String value, int timestamp) {
        List<Node> list = map.getOrDefault(key, new ArrayList<>());
        list.add(new Node(value, timestamp));
        map.put(key, list);
    }

    public String get(String key, int timestamp) {
        List<Node> list = map.getOrDefault(key, new ArrayList<>());
        if (list.isEmpty()) return "";
        // 二分查找 查找 <= timestamp的最大的数
        int n = list.size();
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = (l + r + 1) / 2;
            if (list.get(mid).time <= timestamp) l = mid;
            else r = mid - 1;
        }
        return list.get(l).time > timestamp ? "" : list.get(l).val;
    }
}

07-09 主要元素

🧩 Boyer-Moore 投票算法

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = -1;
        int cnt = 0;
        for (int num : nums) {
            if (cnt == 0) candidate = num;
            if (candidate == num) ++ cnt;
            else -- cnt;
        }
        cnt = 0;
        for (int num : nums) {
            if (num == candidate) ++ cnt;
        }
        return cnt * 2 > nums.length ? candidate : -1;
    }
}

07-08 和相同的二元子数组

🧩 双指针

class Solution {
    public int numSubarraysWithSum(int[] nums, int goal) {
        int n = nums.length;
        int right = 0, left1 = 0, left2 = 0;
        int sum1 = 0, sum2 = 0;
        int ans = 0;
        while (right < n) {
            sum1 += nums[right];
            while (sum1 > goal && left1 <= right) {
                sum1 -= nums[left1 ++];
            }
            sum2 += nums[right];
            while (sum2 >= goal && left2 <= right) {
                sum2 -= nums[left2 ++];
            }
            ans += left2 - left1;
            ++ right;
        }
        return ans;
    }
}

07-07 大餐计数

🧩 哈希表

class Solution {
    public int countPairs(int[] deliciousness) {
        int mod = (int)(1e9 + 7);
        int maxDel = 0;
        for (int del : deliciousness)
            maxDel = Math.max(maxDel, del);
        int maxSum = maxDel * 2;

        Map<Integer, Integer> map = new HashMap<>();
        int n = deliciousness.length;
        int pairs = 0;
        for (int i = 0; i < n; i ++) {
            int val = deliciousness[i];
            for (int sum = 1; sum <= maxSum; sum <<= 1) {
                pairs = (pairs + map.getOrDefault(sum - val, 0)) % mod;
            }
            map.put(val, map.getOrDefault(val, 0) + 1);
        }
        return pairs;
    }
}

07-06 点菜展示表

🧩 哈希表

class Solution {
    public List<List<String>> displayTable(List<List<String>> orders) {
        Map<Integer, Map<String, Integer>> tableMap = new HashMap<>();
        Set<String> foodSet = new HashSet<>();

        for (List<String> order : orders) {
            int num = Integer.parseInt(order.get(1));
            String food = order.get(2);
            foodSet.add(food);

            Map<String, Integer> map = tableMap.getOrDefault(num, new HashMap<String, Integer>());
            map.put(food, map.getOrDefault(food, 0) + 1);
            tableMap.put(num, map);
        }
        LinkedList<List<String>> ans = new LinkedList<>();
        LinkedList<String> foodList = new LinkedList<>();
        for (String food : foodSet) {
            foodList.add(food);
        }
        Collections.sort(foodList); // 食品标题排序

        for (Map.Entry<Integer, Map<String, Integer>> entry : tableMap.entrySet()) {
            List<String> table = new LinkedList<>();
            table.add(String.valueOf(entry.getKey()));
            Map<String, Integer> map = entry.getValue();
            for (String food : foodList) {
                table.add(String.valueOf(map.getOrDefault(food, 0)));
            }
            ans.add(table);
        }
        // 按照餐桌桌号排序
        Collections.sort(ans, (x, y) -> Integer.parseInt(x.get(0)) - Integer.parseInt(y.get(0)));

        foodList.addFirst("Table");
        ans.addFirst(foodList);
        return ans;
    }
}

07-06 字符串相乘

class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0"))
            return "0";

        int n = num1.length(), m = num2.length();
        int[] nums = new int[n + m];
        for (int i = n - 1; i >= 0; -- i) {
            int x = num1.charAt(i) - '0';
            for (int j = m - 1; j >= 0; -- j) {
                int y = num2.charAt(j) - '0';
                nums[i + j + 1] += x * y;
            }
        }
        for (int i = m + n - 1; i >= 1; -- i) {
            nums[i - 1] += nums[i] / 10; // 向上的进位
            nums[i] %= 10;
        }

        int idx = nums[0] == 0 ? 1 : 0;
        StringBuilder sb = new StringBuilder();
        for (int i = idx; i < m + n; ++ i) {
            sb.append(nums[i]);
        }
        return sb.toString();
    }
}

07-06 字符串相加

class Solution {
    public String addStrings(String num1, String num2) {
        int t = 0;
        StringBuilder sb = new StringBuilder();
        int n1 = num1.length(), n2 = num2.length();
        for (int i = n1 - 1, j = n2 - 1; i >= 0 || j >= 0; -- i, --j) {
            if (i >= 0) t += num1.charAt(i) - '0';
            if (j >= 0) t += num2.charAt(j) - '0';
            sb.append(t % 10);
            t /= 10;
        }
        if (t == 1) sb.append(t);
        return sb.reverse().toString();
    }
}

07-05 原子的数量⭐

🧩 栈 + 哈希表

class Solution {
    int i, n;
    String formula;

    public String countOfAtoms(String formula) {
        this.i = 0;
        this.n = formula.length();
        this.formula = formula;

        Deque<Map<String, Integer>> stack = new ArrayDeque<>();
        stack.push(new HashMap<String, Integer>());
        while (i < n) {
            char ch = formula.charAt(i);
            if (ch == '(') {
                ++ i;
                stack.push(new HashMap<String, Integer>());
            } else if (ch == ')') {
                ++ i;
                int num = parseNum(); // 获取括号右侧的数字
                Map<String, Integer> popMap = stack.pop();
                Map<String, Integer> topMap = stack.peek();
                for (Map.Entry<String, Integer> entry : popMap.entrySet()) {
                    String atom = entry.getKey();
                    int val = entry.getValue();
                    topMap.put(atom, topMap.getOrDefault(atom, 0) + num * val);
                }
            } else {
                String atom = parseAtom();
                int num = parseNum();
                Map<String, Integer> topMap = stack.peek();
                topMap.put(atom, topMap.getOrDefault(atom, 0) + num);
            }
        }
        // 排序输出
        StringBuilder sb = new StringBuilder();
        TreeMap<String, Integer> treeMap = new TreeMap<String, Integer>(stack.pop());
        for (Map.Entry<String, Integer> entry : treeMap.entrySet()) {
            sb.append(entry.getKey());
            int val = entry.getValue();
            if (val > 1) sb.append(val);
        }
        return sb.toString();
    }

    // 解析下一个原子
    private String parseAtom() {
        StringBuilder sb = new StringBuilder();
        sb.append(formula.charAt(i ++ )); // 加入首字母
        while (i < n && Character.isLowerCase(formula.charAt(i))) { // 加入后续小写字母
            sb.append(formula.charAt(i ++ ));
        }
        return sb.toString();
    }

    // 解析原子数量
    private int parseNum() {
        if (i == n || !Character.isDigit(formula.charAt(i))) {
            return 1;
        }
        int num = 0;
        while (i < n && Character.isDigit(formula.charAt(i))) {
            num = num * 10 + formula.charAt(i ++ ) - '0';
        }
        return num;
    }
}

07-04 错误的集合⭐

🧩 位运算（异或运算性质）

class Solution {
    // 时间复杂度O(n) 空间复杂度O(1)
    public int[] findErrorNums(int[] nums) {
        // 位运算
        int n = nums.length;
        int xor = 0;
        for (int num : nums) xor ^= num;
        for (int i = 1; i <= n; ++ i) xor ^= i;

        // 此时xor 为 x ^ y 的值
        int lowbit = xor & (-xor); // x 和 y的最低不同位

        // 求 x 和 y
        int x = 0, y = 0;
        for (int num : nums) {
            if ((num & lowbit) == 0) x ^= num;
            else y ^= num; 
        }
        for (int i = 1; i <= n; ++ i) {
            if ((i & lowbit) == 0) x ^= i;
            else y ^= i;
        }

        // 确定x, y各自是哪个数
        for (int num : nums) {
            if (x == num) return new int[]{x, y};
        }
        return new int[]{y, x};
    }
}

07-03 根据字符出现频率排序

🧩 哈希表 + 优先队列

class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> {
            if (x[1] == y[1]) return x[0] - y[0];
            return y[1] - x[1];
        });
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            pq.add(new int[]{entry.getKey(), entry.getValue()});
        }

        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            int[] a = pq.poll();
            for (int i = 0; i < a[1]; ++ i)
                sb.append((char)(a[0]));
        }
        return sb.toString();

    }
}

🧩 数组模拟

class Solution {
    public String frequencySort(String s) {
        int n = 128;
        int[][] nums = new int[n][2];
        for (int i = 0; i < n; ++ i)
            nums[i][0] = i;
        for (char c : s.toCharArray())
            nums[c][1] ++;

        Arrays.sort(nums, (x, y) -> {
            if (x[1] == y[1]) return x[0] - y[0];
            return y[1] - x[1];
        });
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; ++ i) {
            for (int j = 0; j < nums[i][1]; ++ j) {
                sb.append((char)nums[i][0]);
            }
        }
        return sb.toString();
    }
}

07-02 雪糕的最大数量

同LeetCode周赛weekly 237-2

07-01 传递信息

🧩 BFS

class Solution {
    public int numWays(int n, int[][] relation, int k) {
        int m = relation.length;
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
        while (!q.isEmpty() && k > 0) {
            int size = q.size();
            for (int i = 0; i < size; ++ i) {
                int num = q.poll();
                for (int[] rel : relation) {
                    if (rel[0] == num) q.offer(rel[1]);
                }
            }
            k --;
        }
        int ans = 0;
        while (!q.isEmpty()) {
            if (q.poll() == n - 1) ++ ans;
        }
        return ans;
    }
}

🧩 动态规划

class Solution {
    public int numWays(int n, int[][] relation, int k) {
        int[][] f = new int[k + 1][n];
        f[0][0] = 1;
        for (int i = 0; i < k; ++ i) {
            for (int[] rel : relation) {
                f[i + 1][rel[1]] += f[i][rel[0]];
            }
        }
        return f[k][n - 1];
    }
}