周赛361（模拟、枚举、记忆化搜索、统计子数组数目（前缀和+哈希）、LCA应用题）

周赛361

2843. 统计对称整数的数目

简单

给你两个正整数 low 和 high 。

对于一个由 2 * n 位数字组成的整数 x ，如果其前 n 位数字之和与后 n 位数字之和相等，则认为这个数字是一个对称整数。

返回在 [low, high] 范围内的 对称整数的数目 。

示例 1：

输入：low = 1, high = 100
输出：9
解释：在 1 到 100 范围内共有 9 个对称整数：11、22、33、44、55、66、77、88 和 99 。
1
2
3

示例 2：

输入：low = 1200, high = 1230
输出：4
解释：在 1200 到 1230 范围内共有 4 个对称整数：1203、1212、1221 和 1230 。
1
2
3

提示：

• 1 <= low <= high <= 104

模拟

class Solution {
    public int countSymmetricIntegers(int low, int high) {
        int ans = 0;
        for(int num = low; num <= high; num++){
            String str = String.valueOf(num);
            if(str.length() % 2 != 0) continue;
            if(f(str, 0, str.length()/2) == f(str, str.length()/2, str.length()))
                ans += 1;
        }
        return ans;
    }

    public int f(String str, int start, int end){
        int sum = 0;
        for(int i = start; i < end; i++)
            sum += str.charAt(i) - '0';
        return sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2844. 生成特殊数字的最少操作

中等

给你一个下标从 0 开始的字符串 num ，表示一个非负整数。

在一次操作中，您可以选择 num 的任意一位数字并将其删除。请注意，如果你删除 num 中的所有数字，则 num 变为 0。

返回最少需要多少次操作可以使 num 变成特殊数字。

如果整数 x 能被 25 整除，则该整数 x 被认为是特殊数字。

示例 1：

输入：num = "2245047"
输出：2
解释：删除数字 num[5] 和 num[6] ，得到数字 "22450" ，可以被 25 整除。
可以证明要使数字变成特殊数字，最少需要删除 2 位数字。
1
2
3
4

示例 2：

输入：num = "2908305"
输出：3
解释：删除 num[3]、num[4] 和 num[6] ，得到数字 "2900" ，可以被 25 整除。
可以证明要使数字变成特殊数字，最少需要删除 3 位数字。
1
2
3
4

示例 3：

输入：num = "10"
输出：1
解释：删除 num[0] ，得到数字 "0" ，可以被 25 整除。
可以证明要使数字变成特殊数字，最少需要删除 1 位数字。
1
2
3
4

提示

• 1 <= num.length <= 100
• num 仅由数字 '0' 到 '9' 组成
• num 不含任何前导零

记忆化搜索

class Solution {
    String num;
    int[][] cache;
    public int minimumOperations(String num) {
        this.num = num;
        int n = num.length();
        cache = new int[n][25];
        for(int i = 0; i < n; i++)
            Arrays.fill(cache[i], -1);
        return dfs(0, 0);
    }
    // 定义dfs(i, last) 表示 枚举到第i位，0-i位上被25整除后的余数为last，要操作的次数
    // 枚举第i位删还是不删
    public int dfs(int i, int last){
        if(i == num.length())
            return last == 0 ? 0 : num.length();
        if(cache[i][last] >= 0) return cache[i][last];
        int res = num.length();
        res = Math.min(res, dfs(i+1, (last*10 + (num.charAt(i) - '0')) % 25));
        res = Math.min(res, dfs(i+1, last) + 1);
        return cache[i][last] = res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

枚举

枚举删除后以 00/25/50/75 结尾

https://leetcode.cn/problems/minimum-operations-to-make-a-special-number/solutions/2424068/mei-ju-shan-chu-hou-yi-00255075-jie-wei-zhjlu/

class Solution {
    public int minimumOperations(String num) {
        int n = num.length();
        // 如果数字中有0，删除除0外其他数字可以被25整除； 
       // 如果没有，全部删掉使之为0
       int ans = num.contains("0")? n-1 : n;
       ans = Math.min(ans, Math.min(f("00", num), f("25", num)));
       ans = Math.min(ans, Math.min(f("50", num), f("75", num)));
       return ans;
    }

    public int f(String target, String num){
        int i = num.lastIndexOf(target.substring(1));
        // i < 0 代表没有这个数字 (lastIndexOf未找到返回-1)
        if (i < 0) return num.length();
        i = num.substring(0, i).lastIndexOf(target.substring(0, 1));
        if(i < 0) return num.length();
        // 需要删除的数字是 i以后所有除了target的数字
        return num.length() - i - 2;
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2845. 统计趣味子数组的数目

中等

给你一个下标从 0 开始的整数数组 nums ，以及整数 modulo 和整数 k 。

请你找出并统计数组中 趣味子数组 的数目。

如果 子数组 nums[l..r] 满足下述条件，则称其为 趣味子数组 ：

• 在范围 [l, r] 内，设 cnt 为满足 nums[i] % modulo == k 的索引 i 的数量。并且 cnt % modulo == k 。

以整数形式表示并返回趣味子数组的数目。

**注意：**子数组是数组中的一个连续非空的元素序列。

示例 1：

输入：nums = [3,2,4], modulo = 2, k = 1
输出：3
解释：在这个示例中，趣味子数组分别是： 
子数组 nums[0..0] ，也就是 [3] 。 
- 在范围 [0, 0] 内，只存在 1 个下标 i = 0 满足 nums[i] % modulo == k 。
- 因此 cnt = 1 ，且 cnt % modulo == k 。
子数组 nums[0..1] ，也就是 [3,2] 。
- 在范围 [0, 1] 内，只存在 1 个下标 i = 0 满足 nums[i] % modulo == k 。
- 因此 cnt = 1 ，且 cnt % modulo == k 。
子数组 nums[0..2] ，也就是 [3,2,4] 。
- 在范围 [0, 2] 内，只存在 1 个下标 i = 0 满足 nums[i] % modulo == k 。
- 因此 cnt = 1 ，且 cnt % modulo == k 。
可以证明不存在其他趣味子数组。因此，答案为 3 。
1
2
3
4
5
6
7
8
9
10
11
12
13

示例 2：

输入：nums = [3,1,9,6], modulo = 3, k = 0
输出：2
解释：在这个示例中，趣味子数组分别是： 
子数组 nums[0..3] ，也就是 [3,1,9,6] 。
- 在范围 [0, 3] 内，只存在 3 个下标 i = 0, 2, 3 满足 nums[i] % modulo == k 。
- 因此 cnt = 3 ，且 cnt % modulo == k 。
子数组 nums[1..1] ，也就是 [1] 。
- 在范围 [1, 1] 内，不存在下标满足 nums[i] % modulo == k 。
- 因此 cnt = 0 ，且 cnt % modulo == k 。
可以证明不存在其他趣味子数组，因此答案为 2 。
1
2
3
4
5
6
7
8
9
10

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• 1 <= modulo <= 109
• 0 <= k < modulo

前缀和 + 哈希表（区间计数经常是前缀和）

class Solution {
    /**
    1. 转换 设 cnt 为满足 nums[i] % m == k 的索引 i 的数量
        如果 nums[i] % m == k，则 nums[i] = 1，否则 nums[i] = 0
        ==> cnt = 子数组的元素和   ==> 前缀和

    2. 取模 cnt % modulo == k  ==> (pre[r] - pre[l]) % m = k
                               ==> (pre[r] % m - pre[l] % m + m) % m = k
    3. 式子变形 (pre[r] % m - pre[l] % m + m) % m = k
                (pre[r] - k + m) % m = pre[l]
        用哈希表记录pre[l]出现的次数  => 两数之和
     */
    public long countInterestingSubarrays(List<Integer> nums, int m, int k) {
        int n = nums.size();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++)
            arr[i] = (nums.get(i) % m == k) ? 1 : 0;
        int[] pre = new int[n+1];
        for(int i = 0; i < n; i++)
            pre[i+1] = pre[i] + arr[i];
        Map<Integer, Integer> map = new HashMap<>();
        long ans = 0;
        for(int num : pre){
            int target = (num%m - k + m) % m;
            if(map.containsKey(target)) 
                ans += map.get(target);
            map.merge(num%m, 1, Integer::sum);
        }
        return ans;
    }
}
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

2846. 边权重均等查询

困难

现有一棵由 n 个节点组成的无向树，节点按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ui, vi, wi] 表示树中存在一条位于节点 ui 和节点 vi 之间、权重为 wi 的边。

另给你一个长度为 m 的二维整数数组 queries ，其中 queries[i] = [ai, bi] 。对于每条查询，请你找出使从 ai 到 bi 路径上每条边的权重相等所需的 最小操作次数 。在一次操作中，你可以选择树上的任意一条边，并将其权重更改为任意值。

注意：

• 查询之间 相互独立 的，这意味着每条新的查询时，树都会回到 初始状态 。
• 从 ai 到 bi的路径是一个由 不同 节点组成的序列，从节点 ai 开始，到节点 bi 结束，且序列中相邻的两个节点在树中共享一条边。

返回一个长度为 m 的数组 answer ，其中 answer[i] 是第 i 条查询的答案。

示例 1：

输入：n = 7, edges = [[0,1,1],[1,2,1],[2,3,1],[3,4,2],[4,5,2],[5,6,2]], queries = [[0,3],[3,6],[2,6],[0,6]]
输出：[0,0,1,3]
解释：第 1 条查询，从节点 0 到节点 3 的路径中的所有边的权重都是 1 。因此，答案为 0 。
第 2 条查询，从节点 3 到节点 6 的路径中的所有边的权重都是 2 。因此，答案为 0 。
第 3 条查询，将边 [2,3] 的权重变更为 2 。在这次操作之后，从节点 2 到节点 6 的路径中的所有边的权重都是 2 。因此，答案为 1 。
第 4 条查询，将边 [0,1]、[1,2]、[2,3] 的权重变更为 2 。在这次操作之后，从节点 0 到节点 6 的路径中的所有边的权重都是 2 。因此，答案为 3 。
对于每条查询 queries[i] ，可以证明 answer[i] 是使从 ai 到 bi 的路径中的所有边的权重相等的最小操作次数。
1
2
3
4
5
6
7

示例 2：

输入：n = 8, edges = [[1,2,6],[1,3,4],[2,4,6],[2,5,3],[3,6,6],[3,0,8],[7,0,2]], queries = [[4,6],[0,4],[6,5],[7,4]]
输出：[1,2,2,3]
解释：第 1 条查询，将边 [1,3] 的权重变更为 6 。在这次操作之后，从节点 4 到节点 6 的路径中的所有边的权重都是 6 。因此，答案为 1 。
第 2 条查询，将边 [0,3]、[3,1] 的权重变更为 6 。在这次操作之后，从节点 0 到节点 4 的路径中的所有边的权重都是 6 。因此，答案为 2 。
第 3 条查询，将边 [1,3]、[5,2] 的权重变更为 6 。在这次操作之后，从节点 6 到节点 5 的路径中的所有边的权重都是 6 。因此，答案为 2 。
第 4 条查询，将边 [0,7]、[0,3]、[1,3] 的权重变更为 6 。在这次操作之后，从节点 7 到节点 4 的路径中的所有边的权重都是 6 。因此，答案为 3 。
对于每条查询 queries[i] ，可以证明 answer[i] 是使从 ai 到 bi 的路径中的所有边的权重相等的最小操作次数。 
1
2
3
4
5
6
7

提示：

• 1 <= n <= 104
• edges.length == n - 1
• edges[i].length == 3
• 0 <= ui, vi < n
• 1 <= wi <= 26
• 生成的输入满足 edges 表示一棵有效的树
• 1 <= queries.length == m <= 2 * 104
• queries[i].length == 2
• 0 <= ai, bi < n

LCA应用题

https://leetcode.cn/problems/minimum-edge-weight-equilibrium-queries-in-a-tree/solutions/2424060/lca-mo-ban-by-endlesscheng-j54b/

class Solution {
    /** 关键：提炼问题中需要的信息
    【保留出现次数最多的边，其余的边全部修改】
    1. 从 a 到 b 的路径长度（边数）
        = depth[a] - depth[lca] + (depth[b] - depth[lca]) (lca 为 a 和 b 的最近公共祖先)
        ==> 从 a 到 b 的边数为 depth[a] + depth[b] - 2 * depth[lca]
    2. 从 a 到 b 出现次数最多的边
        1 <= wi <= 26  
        ==> 统计从节点 x 到 x的第 2^i 个祖先节点这条路径上 每种边权的出现次数
     */
    public int[] minOperationsQueries(int n, int[][] edges, int[][] queries) {
        List<int[]>[] g = new ArrayList[n]; // x, y, weight
        Arrays.setAll(g, e -> new ArrayList<>());
        for(int[] e : edges){
            int x = e[0], y = e[1], w = e[2] - 1;
            g[x].add(new int[]{y, w});
            g[y].add(new int[]{x, w});
        }

        int m = 32 - Integer.numberOfLeadingZeros(n); // n 的二进制长度
        int[][] pa = new int[n][m];
        for(int i = 0; i < n; i++){
            Arrays.fill(pa[i], -1);
        }

        // cnt:从节点 x 到 x的第 2^i 个祖先节点这条路径上 每种边权的出现次数
        int[][][] cnt = new int[n][m][26];
        int[] depth = new int[n];
        // 一次dfs处理出 从【节点x 到 x父节点】 的 【边数 + 各边权出现次数 + 深度】
        dfs(0, -1, g, pa, cnt, depth);
        
        // 倍增求 【从节点x到 x^i个祖先节点】 的 各边权出现次数
        for(int i = 0; i < m-1; i++){
            for(int x = 0; x < n; x++){
                int p = pa[x][i]; // p:x 的祖先节点
                if(p != -1){
                    int pp = pa[p][i]; // pp : x祖先的祖先节点
                    pa[x][i+1] = pp;
                    for(int j = 0; j < 26; j++){
                        cnt[x][i+1][j] = cnt[x][i][j] + cnt[p][i][j];
                    }
                }
            }
        }

        int[] ans = new int[queries.length];
        for(int qi = 0; qi < queries.length; qi++){
            int x = queries[qi][0], y = queries[qi][1];

            int pathLen = depth[x] + depth[y];
            int[] cw = new int[26];
            if(depth[x] > depth[y]){ // 目的是让x的深度小于y的深度
                int tmp = x; 
                x = y; 
                y = tmp;
            }

            // 让 y 和 x 在同一深度
            for(int k = depth[y] - depth[x]; k > 0; k &= k-1){
                int i = Integer.numberOfTrailingZeros(k);
                int p = pa[y][i];
                for(int j = 0; j < 26; j++){
                    cw[j] += cnt[y][i][j];
                }
                y = p;
            }

            // 求 x 和 y 上的lca节点
            if(y != x){ // 从大到小尝试跳（lca模板）
                for(int i = m-1; i >= 0; i--){
                    int px = pa[x][i], py = pa[y][i];
                    if(px != py){ // 说明 lca节点在pa节点上面，更新x和y
                        for(int j = 0; j < 26; j++)
                            cw[j] += cnt[x][i][j] + cnt[y][i][j];
                        x = px;
                        y = py; // x 和 y 同时上跳 2^i 步
                    }
                }
                for(int j = 0; j < 26; j++)
                    cw[j] += cnt[x][0][j] + cnt[y][0][j];
                x = pa[x][0]; // 循环结束，x和lca节点只有一步之遥，即lca节点是x的父节点
            }

            int lca = x;
            pathLen -= depth[lca] * 2;
            int maxcw = 0; // 边权最大出现次数
            for(int i = 0; i < 26; i++){
                maxcw = Math.max(maxcw, cw[i]);
            }
            ans[qi] = pathLen - maxcw;
        }
        return ans;
    }

    public void dfs(int x, int fa, List<int[]>[] g, int[][] pa, int[][][] cnt, int[] depth){
        pa[x][0] = fa;
        for(int[] e : g[x]){
            int y = e[0], w = e[1];
            if(y != fa){
                cnt[y][0][w] = 1; // 表示 从 y 到 y的第2^0节点(x节点) 有一个边权为w的边
                depth[y] = depth[x] + 1;
                dfs(y, x, g, pa, cnt, depth);
            }
        }
    }
}
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106