LeetCode weekly 270

合法重新排列数对

⚡ 欧拉路径(模板题)

func validArrangement(pairs [][]int) (ans [][]int) {
    adj := map[int][]int{}
    cnt := map[int]int{}
    for _, p := range pairs {
        adj[p[0]] = append(adj[p[0]], p[1])
        cnt[p[0]]++
        cnt[p[1]]--
    }
    start := pairs[0][0]
    for k, v := range cnt {
        if v == 1 {
            start = k
            break
        }
    }

    // Hierholzer 算法
    var dfs func(int)
    dfs = func(u int) {
        for len(adj[u]) != 0 {
            v := adj[u][0]
            adj[u] = adj[u][1:]
            dfs(v)
            ans = append(ans, []int{u, v})
        }
    }
    dfs(start)

    n := len(ans)
    for i := 0; i < n/2; i++ {
        ans[i], ans[n-i-1] = ans[n-i-1], ans[i]
    }
    return
}

class Solution {
    Map<Integer, List<Integer>> adj = new HashMap<>();
    Map<Integer, Integer> deg = new HashMap<>();
    List<int[]> ans = new ArrayList<>();

    public int[][] validArrangement(int[][] pairs) {

        for (int[] pair : pairs) {
            adj.computeIfAbsent(pair[0], v -> new ArrayList<>()).add(pair[1]);
            deg.put(pair[0], deg.getOrDefault(pair[0], 0) + 1);
            deg.put(pair[1], deg.getOrDefault(pair[1], 0) - 1);
        }
        int start = pairs[0][0];
        for (Map.Entry<Integer, Integer> en : deg.entrySet()) {
            if (en.getValue() == 1) {
                start = en.getKey();
                break;
            }
        }
        dfs(start);
        Collections.reverse(ans);
        return ans.toArray(new int[0][0]);
    }

    // Hierholzer 算法
    private void dfs(int u) {
        if (!adj.containsKey(u)) return;
        while (!adj.get(u).isEmpty()) {
            int v = adj.get(u).remove(0);
            dfs(v);
            ans.add(new int[]{u, v});
        }
    }
}

类似题型: 重新安排行程

LeetCode weekly 269

找出知晓秘密的所有专家

⚡ 并查集

class Solution {
    int[] p;
    public List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {
        this.p = new int[n];
        Arrays.sort(meetings, (x, y) -> x[2] - y[2]);

        for (int i = 0; i < n; ++ i) p[i] = i;
        p[firstPerson] = find(0);

        int time = -1;
        Set<Integer> persons = new HashSet<>();

        for (int[] m : meetings) {
            if (m[2] != time) {
                for (int person : persons) {
                    if (find(person) != p[0]) { // 断开不知道秘密的专家之间联系
                        p[person] = person;
                    }
                }
                persons = new HashSet<>();
                time = m[2];
            }

            persons.add(m[0]);
            persons.add(m[1]);

            if (find(m[0]) == find(0)) {
                p[find(m[1])] = find(0);
            } else if (find(m[1]) == find(0)) {
                p[find(m[0])] = find(0);
            } else {
                p[find(m[1])] = find(m[0]);
            }
        }

        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; ++ i) {
            if (find(i) == find(0)) {
                ans.add(i);
            }
        }
        return ans;
    }

    private int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
}

第66场双周赛

统计农场中肥沃金字塔的数目

⚡ dp

func countPyramids(grid [][]int) (ans int) {
    ans += work(grid) // 正金字塔
    m := len(grid)
    for i := 0; i < m/2; i++ {
        grid[i], grid[m-i-1] = grid[m-i-1], grid[i]
    }
    ans += work(grid) // 倒金字塔
    return
}

func work(g [][]int) (ans int) {
    m, n := len(g), len(g[0])
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    for i := range g[m-1] {
        dp[m-1][i] = g[m-1][i]
    }

    for i := m - 2; i >= 0; i-- {
        dp[i][0], dp[i][n-1] = g[i][0], g[i][n-1]
        for j := 1; j < n-1; j++ {
            if g[i][j] == 1 {
                dp[i][j] = min(dp[i+1][j-1], min(dp[i+1][j], dp[i+1][j+1])) + 1
            } else {
                dp[i][j] = 0
            }
            ans += max(0, dp[i][j]-1)
        }
    }
    return
}

LeetCode weekly 268

k 镜像数字的和

⚡ 打表

class Solution {
    long[][] table= {
        {1, 4, 9, 16, 25, 58, 157, 470, 1055, 1772, 9219, 18228, 33579, 65802, 105795, 159030, 212865, 286602, 872187, 2630758, 4565149, 6544940, 9674153, 14745858, 20005383, 25846868, 39347399, 759196316, 1669569335, 2609044274L},
        {1, 3, 7, 15, 136, 287, 499, 741, 1225, 1881, 2638, 31730, 80614, 155261, 230718, 306985, 399914, 493653, 1342501, 2863752, 5849644, 9871848, 14090972, 18342496, 22630320, 28367695, 36243482, 44192979, 71904751, 155059889},
        {1, 3, 6, 11, 66, 439, 832, 1498, 2285, 3224, 11221, 64456, 119711, 175366, 233041, 739646, 2540727, 4755849, 8582132, 12448815, 17500320, 22726545, 27986070, 33283995, 38898160, 44577925, 98400760, 721411086, 1676067545, 53393239260L},
        {1, 3, 6, 10, 16, 104, 356, 638, 1264, 1940, 3161, 18912, 37793, 10125794, 20526195, 48237967, 78560270, 126193944, 192171900, 1000828708, 1832161846, 2664029984L, 3500161622L, 4336343260L, 6849225412L, 9446112364L, 12339666346L, 19101218022L, 31215959143L, 43401017264L},
        {1, 3, 6, 10, 15, 22, 77, 188, 329, 520, 863, 1297, 2074, 2942, 4383, 12050, 19827, 41849, 81742, 156389, 325250, 1134058, 2043967, 3911648, 7009551, 11241875, 15507499, 19806423, 24322577, 28888231},
        {1, 3, 6, 10, 15, 21, 29, 150, 321, 563, 855, 17416, 83072, 2220384, 6822448, 13420404, 20379000, 29849749, 91104965, 321578997, 788407661, 1273902245, 1912731081, 2570225837L, 3428700695L, 29128200347L, 69258903451L, 115121130305L, 176576075721L, 241030621167L},
        {1, 3, 6, 10, 15, 21, 28, 37, 158, 450, 783, 1156, 1570, 2155, 5818, 14596, 27727, 41058, 67520, 94182, 124285, 154588, 362290, 991116, 1651182, 3148123, 5083514, 7054305, 11253219, 66619574},
        {1, 3, 6, 10, 15, 21, 28, 36, 227, 509, 882, 1346, 1901, 2547, 3203, 10089, 35841, 63313, 105637, 156242, 782868, 2323319, 4036490, 5757761, 7586042, 9463823, 11349704, 13750746, 16185088, 18627530}
    };

    public long kMirror(int k, int n) {
        return table[k - 2][n - 1];
    }
}

LeetCode weekly 267

反转偶数长度组的节点⭐

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

        while (tail != null) {
            k ++;
            int i;
            for (i = 1; i < k && tail.next != null; ++ i) {
                tail = tail.next;
            }
            if (i % 2 == 1) {
                pre = tail;
                head = tail = tail.next;
                continue;
            }
            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};
    }
}

相似题型：K个一组翻转链表

处理含限制条件的好友请求

⚡ 并查集

func friendRequests(n int, restrictions [][]int, requests [][]int) []bool {
    p := make([]int, n)
    for i := range p {
        p[i] = i
    }
    // 并查集
    var find func(int) int
    find = func(x int) int {
        if p[x] != x {
            p[x] = find(p[x])
        }
        return p[x]
    }
    // 预处理
    cant := make([]map[int]bool, n)
    for i := range cant {
        cant[i] = map[int]bool{}
    }
    for _, r := range restrictions {
        cant[r[0]][r[1]] = true
        cant[r[1]][r[0]] = true
    }
    // 求解
    ans := make([]bool, len(requests))
    for i, r := range requests {
        v, w := find(r[0]), find(r[1])
        ans[i] = true
        if v == w { // 已是朋友
            continue
        }
        if cant[v][w] { // 无法成为朋友
            ans[i] = false
            continue
        }
        if len(cant[v]) > len(cant[w]) { // 优化: 小的集合合并到大的集合
            v, w = w, v
        }
        // 合并集合
        for x := range cant[v] {
            x = find(x)
            cant[x][w] = true
            cant[w][x] = true
        }
        p[v] = p[w]
    }
    return ans
}

第65场双周赛

模拟行走机器人 II

⚡ 千万不要去模拟

class Robot {
    int w, h, dis;
    boolean state;
    int mod;

    public Robot(int width, int height) {
        w = width;
        h = height;
        dis = 0;
        state = true;
        mod = 2 * (w + h - 2);
    }

    public void move(int num) {
        dis = (dis + num) % mod;
        state = false;
    }

    public int[] getPos() {
        if (state)
            return new int[]{0, 0};
        if (dis < w)
            return new int[]{dis, 0};
        if (dis < w + h - 1)
            return new int[]{w - 1, dis - w + 1};
        if (dis < 2*w + h - 2)
            return new int[]{2*w + h - 3 - dis, h - 1};
        return new int[]{0, mod - dis};
    }

    public String getDir() {
        if (state) return "East";
        if (dis == 0) return "South";
        if (dis < w) return "East";
        if (dis < w + h - 1) return "North";
        if (dis < 2*w + h - 2) return "West";
        return "South";
    }
}

LeetCode weekly 266

最大化一张图中的路径价值

⚡ 回溯

class Solution {
    int[] values;
    Map<Integer, List<int[]>> adjvex;
    boolean[] vis;
    int maxPrice = 0;
    int maxTime;

    public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {
        this.maxTime = maxTime;
        this.values = values;
        this.vis = new boolean[values.length];
        adjvex = new HashMap<>();
        for (int[] e : edges) {
            adjvex.computeIfAbsent(e[0], k -> new ArrayList<int[]>()).add(new int[]{e[1], e[2]});
            adjvex.computeIfAbsent(e[1], k -> new ArrayList<int[]>()).add(new int[]{e[0], e[2]});
        }
        vis[0] = true; 
        backTrack(0, 0, values[0]);
        return maxPrice;
    }

    private void backTrack(int x, int time, int price) {
        if (time > maxTime) return;
        if (x == 0) {
            maxPrice = Math.max(price, maxPrice);
        }
        for (int[] e : adjvex.getOrDefault(x, new ArrayList<>())) {
            if (!vis[e[0]]) {
                vis[e[0]] = true;
                backTrack(e[0], time + e[1], price + values[e[0]]);
                vis[e[0]] = false;
            } else {
                backTrack(e[0], time + e[1], price);
            }
        }
    }
}

第64场双周赛

两个最好的不重叠活动

⚡ 预处理+二分

class Solution {
    public int maxTwoEvents(int[][] events) {
        int n = events.length;
        Arrays.sort(events, (x, y) -> x[1] - y[1]);
        int[] f = new int[n];
        f[0] = events[0][2];
        for (int i = 1; i < n; ++ i) {
            f[i] = Math.max(f[i - 1], events[i][2]);
        }

        int res = 0;
        for (int[] e : events) {
            int i = 0, j = n - 1;
            while (i < j) {
                int mid = (i + j + 1) / 2;
                if (events[mid][1] < e[0]) i = mid;
                else j = mid - 1;
            }
            int s = e[2];
            if (events[i][1] < e[0]) s += f[i];
            res = Math.max(res, s);
        }
        return res;
    }
}

蜡烛之间的盘子⭐

⚡ 前缀和

class Solution {
    public int[] platesBetweenCandles(String s, int[][] queries) {
        int n = s.length();
        int[] pre = new int[n + 1];
        int[] l = new int[n + 1];
        int[] r = new int[n + 2];
        for (int i = 1; i <= n; ++ i) {
            pre[i] = pre[i - 1];
            if (s.charAt(i - 1) == '*') {
                pre[i] ++;
                l[i] = l[i - 1];
            } else {
                l[i] = i;
            }
        }
        for (int i = n; i >= 1; -- i) {
            if (s.charAt(i - 1) == '*') r[i] = r[i + 1];
            else r[i] = i;
        }
        // 枚举所有请求
        int[] ans = new int[queries.length];
        int idx = 0;
        for (int[] q : queries) {
            int a = l[q[1] + 1], b = r[q[0] + 1];
            ans[idx ++] = a > b ? pre[a] - pre[b - 1] : 0;
        }
        return ans;
    }
}

LeetCode Weekly 264

统计最高分的节点数目⭐

class Solution {
    public int countHighestScoreNodes(int[] parents) {
        // 预处理
        Map<Integer, List<Integer>> tree = new HashMap<>();
        for (int i = 0; i < parents.length; ++ i) {
            tree.putIfAbsent(parents[i], new ArrayList<>());
            tree.get(parents[i]).add(i);
        }
        // 递归求出每个子树结点数
        int[] count = new int[parents.length];
        dfs(0, tree, count);
        // 求最高分的节点数目
        int ans = 0;
        long maxScore = 0;
        for (int i = 0; i < parents.length; ++ i) {
            long score = 1;
            int parNum = count[0];
            for (int node : tree.getOrDefault(i, new ArrayList<>())) {
                score *= count[node];
                parNum -= count[node];
            }
            score *= parNum == 1 ? 1 : parNum - 1;

            if (score > maxScore) {
                maxScore = score;
                ans = 0;
            }
            if (score == maxScore) ++ ans;
        }
        return ans;
    }

    private int dfs (int node, Map<Integer, List<Integer>> tree, int[] count) {
        List<Integer> subList = tree.getOrDefault(node, new ArrayList<>());
        int cnt = 1;
        for (int sub : subList) {
            cnt += dfs(sub, tree, count);
        }
        count[node] = cnt;
        return cnt;
    }
}

并行课程 III

⚡ 拓扑排序

class Solution {
    public int minimumTime(int n, int[][] relations, int[] time) {
        // 初始化图
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] r : relations) {
            map.putIfAbsent(r[0], new ArrayList<>());
            map.get(r[0]).add(r[1]);
        }
        // 统计入度
        int[] indeg = new int[n + 1];
        for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
            for (int e : entry.getValue()) {
                indeg[e] ++;
            }
        }

        Queue<Integer> q = new LinkedList<>();
        int[] f = new int[n + 1]; // f[i]表示完成第i个课程的时间
        for (int i = 1; i <= n; ++ i) {
            if (indeg[i] == 0) {
                q.offer(i);
                f[i] = time[i - 1];
            }
        }

        while (!q.isEmpty()) {
            int u = q.poll();
            for (int e : map.getOrDefault(u, new ArrayList<>())) {
                f[e] = Math.max(f[e], f[u] + time[e - 1]);
                if (-- indeg[e] == 0) q.offer(e);
            }
        }
        return Arrays.stream(f).max().getAsInt();
    }
}

LeetCode Weekly 263

统计按位或能得到最大值的子集数目

⚡ DFS + 剪枝

class Solution {
    int ans  = 0;
    public int countMaxOrSubsets(int[] nums) {
        int sum = 0; // 按位或是不减的操作，全部 | 起来即为最大值
        for (int num : nums) {
            sum |= num;
        }
        dfs(nums, sum, 0, 0);
        return ans;
    }

    private void dfs(int[] nums, int sum, int idx, int cur) {
        if (cur == sum) { // 达到最大值即可剪枝
            ans += 1 << (nums.length - idx);
            return;
        }
        if (idx == nums.length) return;
        dfs(nums, sum, idx + 1, cur | nums[idx]);
        dfs(nums, sum, idx + 1, cur);
    }
}

到达目的地的第二短时间⭐

⚡ BFS次短路

class Solution {
    public int secondMinimum(int n, int[][] edges, int time, int change) {
        // 预处理: 邻接表建图
        Map<Integer, List<Integer>> adjvex = new HashMap<>();
        for (int[] edge : edges) {
            adjvex.putIfAbsent(edge[0], new ArrayList());
            adjvex.putIfAbsent(edge[1], new ArrayList());
            adjvex.get(edge[0]).add(edge[1]);
            adjvex.get(edge[1]).add(edge[0]);
        }
        Queue<int[]> q = new LinkedList<>();
        // 记录最短和次短到达的时间
        int[][] minTimes = new int[n + 1][2];
        for (int[] minTime : minTimes) {
            Arrays.fill(minTime, Integer.MAX_VALUE);
        }
        q.offer(new int[]{1, 0}); // 存放编号和到达该编号的时间
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int tmp = cur[1] % (2 * change);
            int extra = tmp >= 0 && tmp < change ? 0 : 2 * change - tmp;
            int nextTime = cur[1] + extra + time; // 该点到达下一个连接点的时间
            // 更新连接点的时间
            for (int next : adjvex.getOrDefault(cur[0], new ArrayList<>())) {
                if (nextTime < minTimes[next][0]) {
                    minTimes[next][1] = minTimes[next][0];
                    minTimes[next][0] = nextTime;
                } else if (nextTime > minTimes[next][0] && nextTime < minTimes[next][1]) {
                    minTimes[next][1] = nextTime;
                } else {
                    continue;
                }
                // 入队: 更新的点及其新的到达时间
                q.offer(new int[]{next, nextTime});
            }
        }
        return minTimes[n][1];
    }
}

第63场双周赛

网络空闲的时刻⭐

⚡ BFS最短路

class Solution {
    public int networkBecomesIdle(int[][] edges, int[] patience) {
        int n = patience.length;
        int ans = 0;

        // 预处理: 邻接表建图
        Map<Integer, List<Integer>> adjvex = new HashMap<>();
        for (int[] edge : edges) {
            adjvex.putIfAbsent(edge[0], new ArrayList());
            adjvex.putIfAbsent(edge[1], new ArrayList());
            adjvex.get(edge[0]).add(edge[1]);
            adjvex.get(edge[1]).add(edge[0]);
        }

        // BFS求最短路径
        int[] distance = new int[n]; // 到起始点0的最小距离
        Arrays.fill(distance, Integer.MAX_VALUE);
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
        distance[0] = 0;
        while (!q.isEmpty()) {
            int x = q.poll();
            if (x != 0) {
                int time = distance[x];
                int cost = 2 * time + (2 * time - 1) / patience[x] * patience[x]; // 关键
                ans = Math.max(ans, cost);
            }
            for (int y : adjvex.getOrDefault(x, new ArrayList<>())) {
                // 更新最短距离
                if (distance[x] + 1 < distance[y]) {
                    distance[y] = distance[x] + 1;
                    q.offer(y);
                }
            }
        }
        return ans + 1; // 返回空闲状态的最早秒数因此需要+1
    }
}

两个有序数组的第K小乘积⭐

⚡ 二分

class Solution {
    public long kthSmallestProduct(int[] nums1, int[] nums2, long k) {
        // 预处理
        List<Integer> p1 = Arrays.stream(nums1).filter(v -> v >= 0).boxed().collect(Collectors.toList()); // positive
        List<Integer> n1 = Arrays.stream(nums1).filter(v -> v < 0).map(v -> v = -v).sorted().boxed().collect(Collectors.toList()); // negative
        List<Integer> p2 = Arrays.stream(nums2).filter(v -> v >= 0).boxed().collect(Collectors.toList());
        List<Integer> n2 = Arrays.stream(nums2).filter(v -> v < 0).map(v -> v = -v).sorted().boxed().collect(Collectors.toList());

        // 确定寻找范围（正or负）
        int sign = 1;
        long nCnt = (long) p1.size() * n2.size() + (long) p2.size() * n1.size(); // 所有乘积为负数的数量
        List<Integer> l1, r1, l2, r2;
        if (k > nCnt) { // 结果为正数
            k -= nCnt;
            l1 = p1; r1 = p2;
            l2 = n1; r2 = n2;
        } else { // 结果为负数
            sign = -1;
            k = nCnt - k + 1; // 负数中最大的是正数里最小的
            l1 = p1; r1 = n2;
            l2 = n1; r2 = p2;
        }

        // 二分
        long left = 0L, right = (long) 1e11;
        while (left < right) {
            long mid = (left + right) / 2;
            if (count(l1, r1, mid) + count(l2, r2, mid) < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left * sign;
    }

    // 乘积小于等target的组合数量
    private long count(List<Integer> arrL, List<Integer> arrR, long target) {
        long res = 0;
        for (int i = 0, j = arrL.size() - 1; i < arrR.size(); ++ i) {
            while (j >= 0 && (long) arrL.get(j) * arrR.get(i) > target) {
                -- j;
            }
            res += j + 1;
        }
        return res;
    }
}

LeetCode Weekly 261

石子游戏 IX⭐

⚡ 博弈论

func stoneGameIX(stones []int) bool {
    c := [3]int{}
    for _, v := range stones {
        c[v % 3] ++
    }
    // 枚举两种回合序列
    // 112121212...
    // 221212121...
    return check(c) || check([3]int{c[0], c[2], c[1]})
}

func check(c [3]int) bool {
    // 枚举第一回合移除1
    if c[1] == 0 {
        return false // 第一回合移除0则直接输
    }
    c[1] --
    turn := 1 + min(c[1], c[2]) * 2 + c[0] // 最大的回合数
    if c[1] > c[2] { // 序列是否以1结尾
        c[1] --
        turn ++
    }
    return turn % 2 == 1 && c[1] != c[2]
}

第 62 场双周赛

分割数组的最多方案数

⚡ 前缀和+哈希表

class Solution {
    public int waysToPartition(int[] nums, int k) {
        int n = nums.length;
        Map<Long, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; ++ i) {
            List<Integer> orDefault = map.getOrDefault((long)(k - nums[i]), new ArrayList<>());
            orDefault.add(i);
            map.put((long)(k - nums[i]), orDefault);
        }
        long[] pre =  new long[n + 1];
        long[] end = new long[n + 1];
        for (int i = 1; i <= n; ++ i) {
            pre[i] = pre[i - 1] + nums[i - 1];
            end[n - i] = end[n + 1 - i] + nums[n - i];
        }
        int[] ans = new int[n + 1];
        for (int i = 1; i < n; ++ i) {
            if (pre[i] == end[i]) {
                ++ ans[n];
            }
            List<Integer> idxs = map.getOrDefault(end[i] - pre[i], null);
            if (idxs != null)
                for (int idx : idxs)
                    if (idx < i)
                        ++ ans[idx];
            idxs = map.getOrDefault(pre[i] - end[i], null);
            if (idxs != null)
                for (int idx : idxs)
                    if (idx >= i)
                        ++ ans[idx];
        }
        return Arrays.stream(ans).max().getAsInt();
    }
}

LeetCode Weekly 260

判断单词是否能放入填字游戏内

⚡ 遍历枚举

class Solution {
    public boolean placeWordInCrossword(char[][] board, String word) {
        int n = board.length, m = board[0].length;
        int k = word.length();
        // 遍历行
        for (char[] b : board) {
            for (int j = 0; j < m; ++ j) {
                if (b[j] == '#') {
                    continue;
                }
                int j0 = j;
                boolean ok1 = true, ok2 = true;
                for (; j < m && b[j] != '#'; ++ j) {
                    // 正序
                    if (j - j0 >= k || (b[j] != ' ' && word.charAt(j - j0) != b[j])) {
                        ok1 = false;
                    }
                    // 逆序
                    if (j - j0 >= k || (b[j] != ' ' && word.charAt(k - 1 - j + j0) != b[j])) {
                        ok2 = false;
                    }
                }
                if ((ok1 || ok2) && j - j0 == k) {
                    return true;
                }
            }
        }

        // 遍历列
        for (int i = 0; i < m; ++ i) {
            for (int j = 0; j < n; ++ j) {
                if (board[j][i] == '#') {
                    continue;
                }
                int j0 = j;
                boolean ok1 = true, ok2 = true;
                for (; j < n && board[j][i] != '#'; ++ j) {
                    // 正序
                    if (j - j0 >= k || (board[j][i] != ' ' && word.charAt(j - j0) != board[j][i])) {
                        ok1 = false;
                    }
                    // 逆序
                    if (j - j0 >= k || (board[j][i] != ' ' && word.charAt(k - 1 - j + j0) != board[j][i])) {
                        ok2 = false;
                    }
                }
                if ((ok1 || ok2) && j - j0 == k) {
                    return true;
                }
            }
        }
        return false;
    }
}

解出数学表达式的学生分数⭐

⚡ 区间DP

class Solution {
    public int scoreOfStudents(String s, int[] answers) {
        // 统计学生所有答案
        int[] count = new int[1024];
        for (int a : answers) {
            count[a] ++;
        }

        // 求出正确答案
        int n = s.length();
        int corrent = 0;
        for (int i = 0; i < n;) {
            int mul = s.charAt(i) - '0';
            for (i += 2; i < n && s.charAt(i - 1) == '*'; i += 2) {
                mul *= s.charAt(i) - '0';
            }
            corrent += mul;
        }

        // 区间 DP
        // dp[l][r] 表示 s[l..r] 内的表达式在不同计算顺序下的不超过 1000 的所有可能值
        Set<Integer>[][] f = new HashSet[n][n];
        for (int i = 0; i < n; i += 2) {
            f[i][i] = new HashSet();
            f[i][i].add(s.charAt(i) - '0');
        }
        // 枚举步伐，不断增大，即 step = j-i
        for(int step = 2; step < n; step += 2){
            // 枚举开始位置 i
            for(int i = 0; i + step < n; i += 2){
                f[i][i + step] = new HashSet(); // 初始化集合
                // 枚举左半部分长度 t
                for(int t = 0; t < step; t += 2){
                    // x是左半部分所有可能值
                    // y是右半部分所有可能值
                    for(int x : f[i][i + t]){
                        for(int y : f[i + t + 2][i + step]){
                            // 根据中间连接符是+/*，来计算连接后的值
                            if(s.charAt(i + t + 1) == '+'){
                                // 因为学生猜测结果均在 [0,1000]，因此超限的值可以直接忽略。
                                if(x + y <= 1000)
                                    f[i][i + step].add(x + y);
                            } else {
                                if(x * y <= 1000)
                                    f[i][i + step].add(x * y);
                            }
                        }
                    }
                }
            }
        }

        int ans = count[corrent] * 5;
        for (int p : f[0][n - 1]) {
            if (p != corrent) {
                ans += count[p] * 2;
            }
        }
        return ans;
    }
}

LeetCode Weekly 259

检测正方形

class DetectSquares {

    // 点和对应数量的哈希表
    Map<String, Integer> map;

    public DetectSquares() {
        map = new HashMap<>();

    }

    public void add(int[] point) {
        String key = point[0] + "-" + point[1];
        map.put(key, map.getOrDefault(key, 0) + 1);
    }

    public int count(int[] point) {
        int ans = 0;
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            String[] strs = entry.getKey().split("-");
            int x = Integer.parseInt(strs[0]);
            int y = Integer.parseInt(strs[1]);
            // 统计以point和(x,y)为对角线的正方形数量
            if (x != point[0] && y != point[1] && 
            Math.abs(x - point[0]) == Math.abs(y - point[1])) {
                int xParCnt  = map.getOrDefault(x + "-" + point[1], 0);
                int yParCnt  = map.getOrDefault(point[0] + "-" + y, 0);
                ans += entry.getValue() * xParCnt * yParCnt;
            }
        }
        return ans;
    }
}

重复 K 次的最长子序列

⚡ BFS枚举 + 双指针

class Solution {
    public String longestSubsequenceRepeatedK(String s, int k) {
        String res = "";
        // 队列q保存满足条件子串
        Queue<String> q = new LinkedList<>();
        q.add("");
        // BFS 最后一个满足条件的便为答案
        while (!q.isEmpty()) {
            String sub = q.poll();
            for (int i = 0; i < 26; ++ i) {
                String next = sub + (char)('a' + i);
                if (isSubsequence(s, next, k)) { // 满足条件
                    res = next;
                    q.add(next);
                }
            }
        }
        return res;
    }

    // 判断sub * k 是否是 s 的子串
    private boolean isSubsequence(String s, String sub, int k) {
        int j = 0, repeat = 0;
        int n = s.length();
        for (int i = 0; i < n; ++ i) {
            if (s.charAt(i) == sub.charAt(j)) {
                ++ j;
                if (j == sub.length()) {
                    ++ repeat;
                    j = 0;
                    if (repeat == k) return true;
                }
            }
        }
        return false;
    }
}

第61场双周赛

出租车的最大盈利(经典dp题)

⚡ dp

class Solution {
    public long maxTaxiEarnings(int n, int[][] rides) {
        Arrays.sort(rides, (x, y) -> {
            return x[1] - y[1];
        });

        // f[i] 表示到i地点的最大盈利
        long[] f = new long[n + 1];
        int idx = 0;
        for (int i = 1; i <= n; ++ i) {
            f[i] = f[i - 1];
            while (idx < rides.length && i == rides[idx][1]) {
                f[i] = Math.max(f[i], f[rides[idx][0]] + rides[idx][1] - rides[idx][0] + rides[idx][2]);
                ++ idx;
            }
        }
        return f[n];
    }
}

使数组连续的最少操作数

⚡ 去重 + 排序 + 滑动窗口

class Solution {
    public int minOperations(int[] a) {
        // 排序
        Arrays.sort(a);
        // 去重
        int n = unique(a);
        // 滑动窗口
        int cur = 0, r = 1;
        for (int l = 0; l < n; ++ l) {
            while (r < n && a[r] - a[l] <= a.length - 1) {
                ++ r;
            }
            cur = Math.max(cur, r - l);
        }
        return a.length - cur;
    }

    /**
     * 在原数组上去重
     * @param nums 原数组
     * @return 去重后的长度
     */
    private int unique(int[] nums) {
        int n = nums.length;
        int i = 0, j = 1;
        while (j < n) {
            if (nums[j - 1] != nums[j]) {
                nums[++ i] = nums[j];
            }
            ++ j;
        }
        return i + 1;
    }
}

类似题型 - 规划兼职工作

LeetCode Weekly 258

可互换矩形的组数

⚡ GCD + 组合数

class Solution {
    public long interchangeableRectangles(int[][] rectangles) {
        HashMap<String, Long> map = new HashMap<>();
        for (int[] rect : rectangles) {
            int gcd = gcd(rect[0], rect[1]);
            String key = null;
            key = rect[0] / gcd + "/" +rect[1] / gcd;
            map.put(key, map.getOrDefault(key, 0L) + 1);
        }

        long ans = 0;
        for (Map.Entry<String, Long> entry : map.entrySet()) {
            Long val = entry.getValue();
            ans += val * (val - 1) / 2; // 组合数Cn2
        }
        return ans;
    }

    private int gcd (int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

LeetCode Weekly 255

最小化目标值与所选元素的差⭐

⚡ 背包型动态规划

func minimizeTheDifference(mat [][]int, target int) int {
    n := len(mat)
    dp := make([] int, n * 70 + 1)
    for i := range dp {
        dp[i] = -1e9
    }
    dp[0] = 0
    for i, row := range mat {
        for j := (i + 1) * 70; j > 0; j -- {
            for _, v := range row {
                if v <= j {
                    dp[j] = max(dp[j], dp[j - v] + 1)
                }
            }
        }
    }
    ans := int(1e9)
    for i, v := range dp {
        if v == n {
            if d := abs(i - target); d < ans {
                ans = d
            }
        }
    }
    return ans
}

第 59 场双周赛

最大方阵和✔️

⚡ 贪心

class Solution {
    public long maxMatrixSum(int[][] matrix) {
        int n = matrix.length, m = matrix[0].length;
        int minAbsNum = Integer.MAX_VALUE;
        int count = 0;
        long ans = 0;
        for (int i = 0; i < n; ++ i) {
            for (int j = 0; j < n; ++ j) {
                int num = Math.abs(matrix[i][j]);
                ans += num;
                minAbsNum = Math.min(minAbsNum, num);
                if (matrix[i][j] <= 0) {
                    count ++;
                }
            }
        }
        return count % 2 == 0 ? ans : ans - 2 * minAbsNum;
    }
}

到达目的地的方案数⭐

⚡ 最短路 + 有向无环图上的动态规划

---

LeetCode Weekly 248

最长公共子路径

⚡ 滚动哈希 & 二分

class Solution {
    int[][] paths;

    int N = 100010;
    long[] h = new long[N];
    long[] p = new long[N];  // p[i]存储base的i次方
    int base = 133331;

    // 合并的总哈希表
    // key序列哈希值 value出现的行数
    Map<Long, Integer> cnt = new HashMap<>(); 
    // key序列哈希值 value是最后出现的行号
     // 用于判断每行内部有没有重复的哈希表
    Map<Long, Integer> S = new HashMap<>();

    private long get(int l, int r) {
        return h[r] - h[l - 1] * p[r - l + 1];
    }

    // 判断是否有长度为mid的公共子路径
    private boolean check (int mid) {
        cnt.clear();
        S.clear();
        p[0] = 1;
        int k = 0;
        for (int[] path : paths) {
            // 计算path哈希值数组
            int n = path.length;
            for (int i = 1; i <= n; ++ i) {
                p[i] = p[i - 1] * base;
                h[i] = h[i - 1] * base + path[i - 1];
            }
            for (int i = mid; i <= n; ++ i) {
                long t = get(i - mid + 1, i);
                // 如果总哈希表cnt中没有出现过，或者S中对应的行号不是当前行
                // 则说明是第一次出现，增加cnt中对应的统计次数和更新最后的行号
                if (!cnt.containsKey(t) || S.get(t) != k) { 
                    cnt.put(t, cnt.getOrDefault(t, 0) + 1);
                    S.put(t, k);
                }
            }
            ++ k;
        }
        // 遍历哈希表统计长度为mid的序列出现的最大行数
        int res = 0;
        for (Map.Entry<Long, Integer> entry : cnt.entrySet()) {
            res = Math.max(res, entry.getValue());
        }
        return res == paths.length;
    }

    public int longestCommonSubpath(int n, int[][] paths) {
        this.paths = paths;
        int l = 0, r = N;
        for (int[] path : paths) {
            r = Math.min(r, path.length);
        }

        // 二分查找最大的公共子路径
        while (l < r) {
            int mid = (l + r + 1) /2;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
        return r;
    }
}

对应模板题：字符串哈希