发表更新算法 / LeetCode5 分钟读完 (大约705个字)

第 113 场力扣夜喵双周赛

使数组成为递增数组的最少右移次数

直接从最小值开始判断数组是否递增，或者可以找到第一个递减的位置，然后再判断数组是否递增（因为如果数组满足条件，则其最多只有一个递减段）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int minimumRightShifts(List<Integer> nums) {
        int n = nums.size(), idx = -1, min = 101;
        for (int i = 0; i < n; i++) {
            if (nums.get(i) < min) {
                min = nums.get(i);
                idx = i;
            }
        }
        for (int i = 0; i < n - 1; i++) {
            int x = (idx + i) % n, y = (x + 1) % n;
            if (nums.get(x) > nums.get(y)) return -1;
        }
        return (n - idx) % n;
    }
}

删除数对后的最小数组长度

贪心，比赛时我是用双指针做的，前半部分和后半部分进行匹配（当时边界想了很久，真笨！）。其他做法，参考题解：【小羊肖恩】数学 + 贪心：解决较长数组脑筋急转弯问题的关键。（因为 HashMap 很慢，所以用双指针会更快。）

方法一：贪心

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int minLengthAfterRemovals(List<Integer> nums) {
        int n = nums.size(), i = 0;
        for (int j = (n + 1) / 2; j < n; j++) {
            if (nums.get(i) < nums.get(j)) {
                i++;
            }
        }
        return n - i * 2;
    }
}

方法二：贪心 + 数学

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int minLengthAfterRemovals(List<Integer> nums) {
        int n = nums.size(), max = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int x : nums) {
            max = Math.max(max, map.merge(x, 1, Integer::sum));
        }
        return 2 * max <= n ? n % 2 : n - (n - max) * 2;
    }
}

统计距离为 k 的点对

枚举 \(x_{1}\oplus x_{2}\) 的值为 \(p\)，可以得到 \(y_{1}\oplus y_{2}\) 的值为 \(k-p\)。可以使用 HashMap 对前缀中的值计数来求解，需要注意循环的顺序，如果调换顺序会使代码变复杂，会花费更多的时间计算答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int countPairs(List<List<Integer>> coordinates, int k) {
        int ans = 0;
        Map<List<Integer>, Integer> map = new HashMap<>();
        for (var c : coordinates) {
            int x = c.get(0), y = c.get(1);
            for (int i = 0; i <= k; i++) {
                ans += map.getOrDefault(List.of(x ^ i, y ^ (k - i)), 0);
            }
            map.merge(c, 1, Integer::sum);
        }
        return ans;
    }
}

可以到达每一个节点的最少边反转次数

换根 DP，关键是要想到建立反向边，并为边添加相应的边权。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public int[] minEdgeReversals(int n, int[][] edges) {
        List<int[]>[] g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (var e : edges) {
            int u = e[0], v = e[1];
            g[u].add(new int[]{v, 0});
            g[v].add(new int[]{u, 1});
        }
        int[] ans = new int[n];
        ans[0] = dfs(0, -1, g);
        dfs2(0, -1, g, ans);
        return ans;
    }
    
    private int dfs(int x, int fa, List<int[]>[] g) {
        int res = 0;
        for (int t[] : g[x]) {
            int y = t[0], w = t[1];
            if (y == fa) continue;
            res += dfs(y, x, g) + w;
        }
        return res;
    }
    
    private void dfs2(int x, int fa, List<int[]>[] g, int[] ans) {
        for (int t[] : g[x]) {
            int y = t[0], w = t[1];
            if (y == fa) continue;
            ans[y] = ans[x] + (w == 0 ? 1 : -1);
            dfs2(y, x, g, ans);
        }
    }
}
发表更新算法 / LeetCode6 分钟读完 (大约857个字)

第 362 场力扣周赛

与车相交的点

差点又想区间合并做，看下数据范围，直接暴力，更好的做法是差分数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int numberOfPoints(List<List<Integer>> nums) {
        int[] d = new int[102];
        for (var num : nums) {
            d[num.get(0)]++;
            d[num.get(1) + 1]--;
        }
        int ans = 0;
        for (int i = 1; i <= 100; i++) {
            d[i] += d[i - 1];
            if (d[i] > 0) ans++;
        }
        return ans;
    }
}

判断能否在给定时间到达单元格

题目说恰好第 \(t\) 秒到达，我还以为之前都不能到达，结果可以。那么特殊情况就是起点和终点相同，并且 \(t=1\)。

1
2
3
4
5
6
7
class Solution {
    public boolean isReachableAtTime(int sx, int sy, int fx, int fy, int t) {
        if (sx == fx && sy == fy && t == 1) return false;
        int a = Math.abs(sx - fx), b = Math.abs(sy - fy);
        return Math.max(a, b) <= t;
    }
}

将石头分散到网格图的最少移动次数

方法一：回溯

记录所有等于零和大于一的位置，然后 DFS 搜索每个零从哪个位置获取一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    int ans = Integer.MAX_VALUE;
    
    public int minimumMoves(int[][] grid) {
        List<int[]> a = new ArrayList<>(), b = new ArrayList<>();
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (grid[i][j] == 0) a.add(new int[]{i, j});
                else if (grid[i][j] > 1) b.add(new int[]{i, j});
            }
        }
        dfs(0, grid, a, b, 0);
        return ans;
    }
    
    private void dfs(int i, int[][] grid, List<int[]> a, List<int[]> b, int cnt) {
        if (i == a.size()) {
            ans = Math.min(ans, cnt);
            return;
        }
        int[] p = a.get(i);
        for (int j = 0; j < b.size(); j++) {
            int[] q = b.get(j);
            if (grid[q[0]][q[1]] > 1) {
                grid[q[0]][q[1]]--;
                dfs(i + 1, grid, a, b, cnt + Math.abs(p[0] - q[0]) + Math.abs(p[1] - q[1]));
                grid[q[0]][q[1]]++;
            }
        }
    }
}

方法二：状压 DP

不是很懂，具体解释可以看大佬的题解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    int ans = Integer.MAX_VALUE;
    
    public int minimumMoves(int[][] grid) {
        List<int[]> a = new ArrayList<>(), b = new ArrayList<>();
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (grid[i][j] == 0) a.add(new int[]{i, j});
                for (int k = 2; k <= grid[i][j]; k++) b.add(new int[]{i, j});
            }
        }

        int n = a.size();
        int[] f = new int[1 << n];
        for (int i = 1; i < 1 << n; i++) {
            f[i] = Integer.MAX_VALUE;
            int m = Integer.bitCount(i);
            for (int j = 0; j < n; j++) {
                if ((i >> j & 1) == 1) {
                    f[i] = Math.min(f[i], f[i ^ (1 << j)] + distance(a.get(m - 1), b.get(j)));
                }
            }
        }
        return f[(1 << n) - 1];
    }

    private int distance(int[] x, int[] y) {
        return Math.abs(x[0] - y[0]) + Math.abs(x[1] - y[1]);
    }
}

字符串转换

KMP + 矩阵快速幂，详细见灵神题解，学习 KMP 看代码随想录，还有各种其他解法可以看题解区（很不错！）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
    private static final int MOD = (int) 1e9 + 7;

    public int numberOfWays(String s, String t, long k) {
        int n = s.length();
        char[] text = (s + s.substring(0, n - 1)).toCharArray();
        char[] pattern = t.toCharArray();
        int c = kmp(text, pattern);

        // f[0][0] = s.equals(t) ? 1 : 0;
        // f[0][1] = s.equals(t) ? 0 : 1;
        // f[i][0] = f[i - 1][0] * (c - 1) + f[i - 1][1] * c;
        // f[i][1] = f[i - 1][0] * (n - c) + f[i - 1][1] * (n - c - 1);
        long[][] m = {{c - 1, c}, {n - c, n - c - 1}};
        m = pow(m, k);
        return s.equals(t) ? (int) m[0][0] : (int) m[0][1];
    }

    private int kmp(char[] text, char[] pattern) {
        int m = text.length, n = pattern.length;
        int[] next = new int[n];
        for (int i = 1, j = 0; i < n; i++) {
            while (j > 0 && pattern[i] != pattern[j]) {
                j = next[j - 1];
            }
            if (pattern[i] == pattern[j]) j++;
            next[i] = j;
        }

        int cnt = 0;
        for (int i = 0, j = 0; i < m; i++) {
            while (j > 0 && text[i] != pattern[j]) {
                j = next[j - 1];
            }
            if (text[i] == pattern[j]) j++;
            if (j == n) {
                cnt++;
                j = next[j - 1];
            }
        }
        return cnt;
    }

    private long[][] pow(long[][] a, long n) {
        long[][] res = {{1, 0}, {0, 1}};
        while (n != 0) {
            if ((n & 1) == 1) res = mul(res, a);
            a = mul(a, a);
            n >>= 1;
        }
        return res;
    }

    private long[][] mul(long[][] a, long[][] b) {
        long[][] c = new long[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                c[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j]) % MOD;
            }
        }
        return c;
    }
}
发表更新算法 / LeetCode6 分钟读完 (大约890个字)

第 361 场力扣周赛

统计对称整数的数目

模拟。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int countSymmetricIntegers(int low, int high) {
        int ans = 0;
        for (int i = low; i <= high; i++) {
            int x = i, n = 0;
            int[] aux = new int[10];
            for (; x != 0; x /= 10) {
                aux[n++] = x % 10;
            }
            if (n % 2 == 0) {
                int sum = 0;
                for (int j = 0; j < n / 2; j++) {
                    sum += aux[j] - aux[j + n / 2];
                }
                if (sum == 0) {
                    ans++;
                }
            }
        }
        return ans;
    }
}

生成特殊数字的最少操作

比较简洁的暴力写法，当然从个位开始找 \(25,75,50,00,0\) 更快。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minimumOperations(String num) {
        int n = num.length(), ans = n;
        for (int i = 0; i < n; i++) {
            if (num.charAt(i) == '0') {
                ans = Math.min(ans, n - 1);
            }
            for (int j = i + 1; j < n; j++) {
                int x = (num.charAt(i) - '0') * 10 + num.charAt(j) - '0';
                if (x % 25 == 0) {
                    ans = Math.min(ans, n - i - 2);
                }
            }
        }
        return ans;
    }
}

统计趣味子数组的数目

最开始的思路是，找到所有满足 \(nums[i]\bmod modulo=k\) 的下标放入新的列表，然后在新列表中枚举左端点 \(i\)，此时满足条件的右端点就是 \(i+k-1+j\times modulo\)。暴力解决的时间复杂度 \(O(n^{2})\)，所以可以倒序枚举左端点，顺便记录间隔为 \(modulo\) 的后缀和。但是，这样解决还需要特判 \(k=0\) 的情况，总之很麻烦。

更好的做法是利用同余的性质。将所有 \(nums[i]\bmod modulo=k\) 的数字看作 \(1\)，其他数字看作 \(0\)，这样我们要求的就是满足 \((sum[r+1]-sum[l])\bmod modulo=k\) 的所有子数组的数目。我们可以枚举右端点，找到满足 \((sum[r+1]-k)\equiv sum[l]\pmod{modulo}\) 的左端点的个数，使用前缀和 + 哈希表即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public long countInterestingSubarrays(List<Integer> nums, int modulo, int k) {
        long ans = 0L;
        int n = nums.size(), sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int x : nums) {
            if (x % modulo == k) {
                sum = (sum + 1) % modulo;
            }
            ans += map.getOrDefault((sum - k + modulo) % modulo, 0);
            map.merge(sum, 1, Integer::sum);
        }
        return ans;
    }
}

边权重均等查询

树上倍增求最近公共祖先，同时维护边权的计数。详细见灵神题解。（发现汪佬的写法更简单，在 DFS 的同时进行倍增，以及通过拷贝数组来维护边权的计数信息。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Solution {
    private static final int M = 14;

    public int[] minOperationsQueries(int n, int[][] edges, int[][] queries) {
        List<int[]>[] g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2] - 1;
            g[u].add(new int[]{v, w});
            g[v].add(new int[]{u, w});
        }
        int[] depth = new int[n];
        int[][] cnt = new int[n][26];
        int[][] parent = new int[M][n];
        dfs(0, -1, g, depth, parent, cnt);
        // 查询
        int k = queries.length;
        int[] ans = new int[k];
        while (k-- != 0) {
            int x = queries[k][0], y = queries[k][1];
            int z = lca(x, y, depth, parent), max = 0;
            for (int i = 0; i < 26; i++) {
                max = Math.max(max, cnt[x][i] + cnt[y][i] - 2 * cnt[z][i]);
            }
            ans[k] = depth[x] + depth[y] - 2 * depth[z] - max;
        }
        return ans;
    }

    // DFS 的同时进行倍增，以及维护边权的计数
    private void dfs(int x, int fa, List<int[]>[] g, int[] depth, int[][] parent, int[][] cnt) {
        for (int i = 1; 1 << i <= depth[x]; i++) {
            parent[i][x] = parent[i - 1][parent[i - 1][x]];
        }
        for (int[] t : g[x]) {
            int y = t[0], w = t[1];
            if (y != fa) {
                parent[0][y] = x;
                System.arraycopy(cnt[x], 0, cnt[y], 0, 26);
                cnt[y][w]++;
                depth[y] = depth[x] + 1;
                dfs(y, x, g, depth, parent, cnt);
            }
        }
    }

    // 求最近公共祖先
    private int lca(int x, int y, int[] depth, int[][] parent) {
        if (depth[x] > depth[y]) {
            int t = x;
            x = y;
            y = t;
        }
        // 先向上跳到相同深度
        int step = depth[y] - depth[x];
        for (int i = 0; i < 32; i++) {
            if ((step >> i & 1) != 0) {
                y = parent[i][y];
            }
        }
        // 尽量向上跳
        if (x != y) {
            for (int i = M - 1; i >= 0; i--) {
                int px = parent[i][x], py = parent[i][y];
                if (px != py) {
                    x = px;
                    y = py;
                }
            }
            x = parent[0][x];
        }
        return x;
    }
}
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×