526互联

[Leetcode Weekly Contest]361

发布时间 2023-09-04 19:26:22作者: Jamest
title: '[Leetcode Weekly Contest]361'
date: 2023-08-21 15:18:48
tags: [OJ]
mathjax: true

链接：LeetCode

[Leetcode]2843. 统计对称整数的数目

给你两个正整数 low 和 high 。
对于一个由 2 * n 位数字组成的整数 x ，如果其前 n 位数字之和与后 n 位数字之和相等，则认为这个数字是一个对称整数。
返回在 [low, high] 范围内的 对称整数的数目 。

遍历即可。

class Solution {
    public int countSymmetricIntegers(int low, int high) {
        int res = 0;
        for(int i=low;i<=high;++i) {
            if(isSymmetricIntegers(i)) {
                res ++;
            }
        }
        return res;
    }

    private boolean isSymmetricIntegers(int val) {
        int n = (""+val).length();
        if((n&1)!=0) return false;
        n = n/2;
        int val1 = 0, val2 = 0, i = 0;
        while(val != 0) {
            int num = val % 10;
            val = val / 10;
            if(i < n) val1 += num;
            else val2 += num;
            ++i;
        }
        return val1 == val2;
    }
}

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

给你一个下标从 0 开始的字符串 num ，表示一个非负整数。
在一次操作中，您可以选择 num 的任意一位数字并将其删除。请注意，如果你删除 num 中的所有数字，则 num 变为 0。
返回最少需要多少次操作可以使 num 变成特殊数字。
如果整数 x 能被 25 整除，则该整数 x 被认为是特殊数字。

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

class Solution {
    public int minimumOperations(String num) {
        int res = num.length();
        boolean getZero = false, getFive = false;
        int n = num.length();
        for(int i=n-1;i>=0;--i) {
            char ch = num.charAt(i);
            if(ch == '0') {
                if(!getZero) getZero = true;
                else return n-(i+2);
            }
            if(ch == '5') {
                if(!getFive) getFive = true;
                if(getZero) return n-(i+2);
            }
            if(ch == '2' || ch == '7') {
                if(getFive) return n-(i+2);
            }
        }
        return getZero ? res-1 : res;
    }
}

[Leetcode]2845. 统计趣味子数组的数目

给你一个下标从 0 开始的整数数组 nums ，以及整数 modulo 和整数 k 。
请你找出并统计数组中 趣味子数组 的数目。
如果 子数组 nums[l..r] 满足下述条件，则称其为 趣味子数组 ：
在范围 [l, r] 内，设 cnt 为满足 nums[i] % modulo == k 的索引 i 的数量。并且 cnt % modulo == k 。
以整数形式表示并返回趣味子数组的数目。
注意：子数组是数组中的一个连续非空的元素序列。

前缀和+数学式子变形。对于本题，由于需要统计 \(\textit{cnt}\)，我们可以把满足要求的nums[i] 视作 1，不满足为0， 如此转换后，算出 \(\textit{nums}\) 的前缀和数组 s，那么题目中的cnt mod modulo=k等价于满足 (s[r+1]−s[l])mod modulo=k, 对于这个等式，等同于 \(s[r+1]\%modulo -s[l]\%modulo = k\), 考虑到负数的情况，即\((s[r+1]\%modulo -s[l]\%modulo + modulo) \% modulo = k\)

class Solution {
    public long countInterestingSubarrays(List<Integer> nums, int modulo, int k) {
        int n = nums.size();
        int[] presum = new int[n+1];
        int sum = 0;
        for(int i=0;i<n;++i) {
            if(nums.get(i) %  modulo == k) {
                sum ++;
            }
            presum[i+1] = sum;
        }
        Map<Integer, Integer> map = new HashMap<>();
        long res = 0L;
        for(int num:presum) {
            res += map.getOrDefault((num % modulo - k + modulo) % modulo, 0);
            map.put(num % modulo, map.getOrDefault(num % modulo, 0) + 1);
        }
        return res;
    }
}

[Leetcode]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 条查询的答案。

LCA 模板,对于每个询问，在计算 a 和 b 的最近公共祖先的同时，也同样地维护从 a 到 b 路径上的每种边权的个数 cnt。

class Solution {
    public int[] minOperationsQueries(int n, int[][] edges, int[][] queries) {
        List<int[]>[] g = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for (var 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 的二进制长度
        var pa = new int[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(pa[i], -1);
        }
        var cnt = new int[n][m][26];
        var depth = new int[n];
        dfs(0, -1, g, pa, cnt, depth);

        for (int i = 0; i < m - 1; i++) {
            for (int x = 0; x < n; x++) {
                int p = pa[x][i];
                if (p != -1) {
                    int pp = pa[p][i];
                    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];
                    }
                }
            }
        }

        var 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];
            var cw = new int[26];
            if (depth[x] > depth[y]) {
                int temp = x;
                x = y;
                y = temp;
            }

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

            if (y != x) {
                for (int i = m - 1; i >= 0; i--) {
                    int px = pa[x][i];
                    int py = pa[y][i];
                    if (px != py) {
                        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];
            }

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

    private void dfs(int x, int fa, List<int[]>[] g, int[][] pa, int[][][] cnt, int[] depth) {
        pa[x][0] = fa;
        for (var e : g[x]) {
            int y = e[0], w = e[1];
            if (y != fa) {
                cnt[y][0][w] = 1;
                depth[y] = depth[x] + 1;
                dfs(y, x, g, pa, cnt, depth);
            }
        }
    }
}

参考：LeetCode