周赛361

2843. 统计对称整数的数目

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

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

模拟

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

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

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

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

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

记忆化搜索

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

枚举

枚举删除后以 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整除； // 如果没有，全部删掉使之为0int 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;}
}

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

输入：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 。

输入：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 。

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

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 = k3. 式子变形 (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;}
}

2846. 边权重均等查询

输入：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 的路径中的所有边的权重相等的最小操作次数。

输入：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 的路径中的所有边的权重相等的最小操作次数。 

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, weightArrays.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和yfor(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);}}}
}