本文最后更新于2022年3月20日,已超过 2 个月没更新!

LeetCode weekly 285

统计道路上的碰撞次数

// 解法 by灵茶山艾府
func countCollisions(s string) int {
    s = strings.TrimLeft(s, "L")          // 前缀向左的车不会发生碰撞
    s = strings.TrimRight(s, "R")         // 后缀向右的车不会发生碰撞
    return len(s) - strings.Count(s, "S") // 剩下非停止的车必然会碰撞
}

射箭比赛中的最大得分

位枚举

func maximumBobPoints(numArrows int, aliceArrows []int) (ans []int) {
    n := 1 << 12
    maxScore := 0
    for i := 0; i < n; i++ {
        cnt := 0
        score := 0
        arr := make([]int, 12)
        for j := 0; j < 12; j++ {
            if (i>>j)&1 == 1 {
                cnt += aliceArrows[j] + 1
                score += j
                arr[j] = aliceArrows[j] + 1
            }
        }
        if cnt > numArrows {
            continue
        }
        arr[0] += numArrows - cnt
        if maxScore < score {
            maxScore = score
            ans = arr
        }
    }
    return
}

LeetCode biweekly 74

用地毯覆盖后的最少白色砖块

dp

func minimumWhiteTiles(floor string, numCarpets int, carpetLen int) int {
    n := len(floor)
    f := make([][]int, numCarpets+1)
    for i := range f {
        f[i] = make([]int, n)
    }

    f[0][0] = int(floor[0] & 1)
    for i := 1; i < n; i++ {
        f[0][i] = f[0][i-1] + int(floor[i]&1)
    }
    for i := 1; i <= numCarpets; i++ {
        for j := carpetLen; j < n; j++ {
            f[i][j] = min(f[i][j-1]+int(floor[j]&1), f[i-1][j-carpetLen])
        }
    }
    return f[numCarpets][n-1]
}

LeetCode weekly 284

得到要求路径的最小带权子图

dijkstra

type edge struct{ to, wt int }

func dijkstra(g [][]edge, start int) []int {
    n := len(g)
    dis := make([]int, n)
    for i := range dis {
        dis[i] = 1e18
    }
    dis[start] = 0
    h := hp{{start, 0}}
    for len(h) > 0 {
        p := heap.Pop(&h).(pair)
        v := p.v
        if dis[v] < p.dis {
            continue
        }
        for _, e := range g[v] {
            w := e.to
            if dis[w] > dis[v]+e.wt {
                dis[w] = dis[v] + e.wt
                heap.Push(&h, pair{w, dis[w]})
            }
        }
    }
    return dis
}

func minimumWeight(n int, edges [][]int, src1 int, src2 int, dest int) int64 {
    g := make([][]edge, n)
    rg := make([][]edge, n)
    for _, e := range edges {
        v, w, wt := e[0], e[1], e[2]
        g[v] = append(g[v], edge{w, wt})
        rg[w] = append(rg[w], edge{v, wt})
    }

    d1 := dijkstra(g, src1)
    d2 := dijkstra(g, src2)
    d3 := dijkstra(rg, dest)

    ans := int(1e18)
    for x := 0; x < n; x++ {
        ans = min(ans, d1[x]+d2[x]+d3[x])
    }
    if ans < 1e18 {
        return int64(ans)
    }
    return -1
}

type pair struct{ v, dis int }
type hp []pair

func (h hp) Len() int              { return len(h) }
func (h hp) Less(i, j int) bool    { return h[i].dis < h[j].dis }
func (h hp) Swap(i, j int)         { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{})   { *h = append(*h, v.(pair)) }
func (h *hp) Pop() (v interface{}) { a := *h; *h, v = a[:len(a)-1], a[len(a)-1]; return }

LeetCode weekly 283

根据描述创建二叉树

func createBinaryTree(descriptions [][]int) (root *TreeNode) {
    m := map[int]*TreeNode{}
    in := map[int]int{}
    for _, d := range descriptions {
        x, y := d[0], d[1]
        if m[x] == nil {
            m[x] = &TreeNode{Val:x}
        }
        if m[y] == nil {
            m[y] = &TreeNode{Val:y}
        }
        if d[2] == 1 {
            m[x].Left = m[y]
        } else {
            m[x].Right = m[y]
        }
        in[y]++
    }

    for k, _ := range m {
        if in[k] == 0 {
            root = m[k]
            break
        }
    }
    return root
}

替换数组中的非互质数

func replaceNonCoprimes(nums []int) []int {
    st := []int{nums[0]}
    for _, v := range nums[1:] {
        st = append(st, v)
        for len(st) >= 2 {
            x, y := st[len(st)-1], st[len(st)-2]
            if gcd(x,y) > 1 {
                st = append(st[:len(st)-2], lcm(x,y))
            } else {
                break
            }
        }
    }
    return st
}

// 最大公约数
func gcd(x, y int) int{
    if y == 0 {
        return x
    }
    return gcd(y, x%y)
}

// 最小公倍数
func lcm(x, y int) int{
    return x*y/gcd(x,y)
}

LeetCode weekly 273

还原原数组

枚举+双指针

func recoverArray(nums []int) (ans []int) {
    sort.Ints(nums)
    n := len(nums)
    ans = make([]int, n)
    // 枚举所有k的可能情况
    for i := 1; i < n; i++ {
        k := nums[i] - nums[0]
        if k == 0 || k % 2 == 1 {
            continue
        }
        t := 0
        vis := make([]bool, n)
        l, r := 0, i
        for r < n {
            for l < n && vis[l] {
                l++
            }
            for r < n && nums[r] - nums[l] != k {
                r++
            }
            if r == n {
                break
            }
            vis[r] = true
            ans[t] = nums[l] + k / 2
            t++; l++; r++
        }
        if t == n / 2 {
            return ans
        }
    }
    return
}

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

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