LeetCode Contest 361

7020. Count Symmetric Integers

给你两个正整数 low 和 high 。

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

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

测试样例：

输入：low = 1, high = 100

输出：9

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

解答：搜索范围很小，没必要用困难写法。暴力计算。

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

    private boolean isSymmetric(int n) {
        String num = String.valueOf(n);
        if (num.length() %  2 == 0) {
            int left = 0, right = 0;
            int point = num.length() / 2;
            for (int i = 0; i < num.length(); ++i) {
                if (i < point) {
                    left += num.charAt(i);
                } else {
                    right += num.charAt(i);
                }
            }
            return left == right;
        }
        return false;
    }
}

8040. Minimum Operations to Make a Special Number

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

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

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

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

测试样例：

输入：num = "2245047"

输出：2

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

解答：能被25整除，数字结尾必然是00，25，50和75。先计算一下，如果让当前数字结尾符合要求所需要的删除次数。还有一种可能是把所有数字都删除，这种情况下，可以查看一下当前数字有多少个0（0不需要被删除）。

class Solution {
    private static final String[] endWith = {"00", "50", "25", "75"};

    public int minimumOperations(String num) {
        int min = num.length() - countZero(num);
        for (String e : endWith) {
            min = Math.min(cal(num, e), min);
        }
        return min;
    }

    private int cal(String num, String e) {
        int[] result = {-1,-1};
        int p = 1, c = 0;
        for (int i = num.length() - 1; i >= 0; --i) {
            if (num.charAt(i) == e.charAt(p)) {
                result[p--] = i;
                if (p == -1) {
                    return c - 1;
                }
            }
            ++c;
        }
        return num.length();
    }

    private int countZero(String num) {
        int count = 0;
        for (int i = 0; i < num.length(); ++i) {
            if (num.charAt(i) == '0') {
                ++count;
            }
        }
        return count;
    }
}

6952. Count of Interesting Subarrays

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

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

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

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

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

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

测试样例

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

解答：这道题目主要考察前缀和。题目比较绕，但是逻辑很简单，查看前缀和是否可以用差值凑出k。

class Solution {
    public long countInterestingSubarrays(List<Integer> nums, int modulo, int k) {
        HashMap<Integer, Integer> mem = new HashMap<>();
        mem.put(0, 1);
        int count = 0;
        long res = 0;
        for (int n : nums) {
            int add = (n % modulo == k ? 1 : 0);
            count = (count + add) % modulo;
            if (count < k) {
                res += mem.getOrDefault(modulo - k + count, 0);
            } else {
                res += mem.getOrDefault(count - k, 0);
            }
            mem.put(count, mem.getOrDefault(count, 0) + 1);
        }
        return res;
    }
}

100018. Minimum Edge Weight Equilibrium Queries in a Tree

现有一棵由 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 条查询的答案。

测试样例

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

解答：这题感觉很难，但是好像通过率很高的样子。。。我能想到的思路是假定0点是root，那么从0点开始，计算一下每个数到0所经过的权重边。但是实际上，任意2点之间的最短路径可能不经过0点，所以我们还需要寻找LCA。因为query数还挺多的，我能想到的是利用倍增法+折半搜索寻找这个目标节点。

有这些准备之后，遍历query，寻找最长共同祖节点，最后计算路径上的权重。

class Solution {
    class TreeAncestor {
        private TreeMap<Integer, Integer>[] parentMap;
        private HashSet<Integer> pow;

        public TreeAncestor(int n, int[] parent) {
            parentMap = new TreeMap[n];
            parentMap[0] = new TreeMap<>();
            for (int i = 0; i < n; ++i) {
                parentMap[i] = initialParent(i, parent);
            }

            int d = 1;
            pow = new HashSet<>();
            while (d <= n) {
                pow.add(d);
                d *= 2;
            }
        }

        private TreeMap<Integer, Integer> initialParent(int p, int[] parent) {
            if (parentMap[p] == null) {
                int d = 1, last = parent[p];
                parentMap[p] = new TreeMap<>();
                parentMap[p].put(1, last);
                for (;;) {
                    TreeMap<Integer, Integer> tmp = initialParent(last, parent);
                    if (tmp.containsKey(d)) {
                        last = tmp.get(d);
                        parentMap[p].put(2 * d, last);
                        d *= 2;
                    } else {
                        break;
                    }
                }
            }
            return parentMap[p];
        }

        public int getKthAncestor(int node, int k) {
            if (k == 0) {
                return node;
            } else if (pow.contains(k) || node == 0) {
                return parentMap[node].getOrDefault(k, -1);
            } else {
                Map.Entry<Integer, Integer> kv = parentMap[node].floorEntry(k);
                if (kv == null || kv.getKey() < k / 2) return -1;
                else if (kv.getKey().equals(k)) return kv.getValue();
                else return getKthAncestor(kv.getValue(), k - kv.getKey());
            }
        }
    }

    private List<int[]>[] edges;
    private int[][] mem;
    private int[] depth, parent;
    private TreeAncestor treeAncestor;

    public int[] minOperationsQueries(int n, int[][] _edges, int[][] queries) {
        edges = new List[n];
        for (int i = 0; i < n; ++i) {
            edges[i] = new ArrayList<>();
        }
        for (int[] e : _edges) {
            e[2] -= 1;
            edges[e[0]].add(e);
            edges[e[1]].add(e);
        }

        mem = new int[n][26];
        depth = new int[n];
        parent = new int[n];

        dfs(0, -1, 0, new int[26]);
        treeAncestor = new TreeAncestor(n, parent);

        int[] res = new int[queries.length];
        for (int i = 0; i < res.length; ++i) {
            res[i] = getResult(queries[i][0], queries[i][1]);
        }
        return res;
    }

    private void dfs(int pos, int last, int curDepth, int[] mark) {
        for (int i = 0; i < 26; ++i) {
            mem[pos][i] = mark[i];
        }
        depth[pos] = curDepth;
        parent[pos] = last;

        for (int[] e : edges[pos]) {
            int nextNode = e[0] == pos ? e[1] : e[0];
            if (nextNode != last) {
                mark[e[2]] += 1;
                dfs(nextNode, pos, curDepth + 1, mark);
                mark[e[2]] -= 1;
            }
        }
    }

    private int getResult(int n1, int n2) {
        int d1 = depth[n1], d2 = depth[n2];
        int min = Math.min(d1, d2);
        int st = 0, ed = min;
        while (st < ed) {
            int mid = (st + ed + 1) / 2;
            int p1 = treeAncestor.getKthAncestor(n1, transLateFromSeed(d1, mid)), p2 = treeAncestor.getKthAncestor(n2, transLateFromSeed(d2, mid));
            if (p1 != p2) {
                ed = mid - 1;
            } else {
                st = mid;
            }
        }
        int commonParent = treeAncestor.getKthAncestor(n1, transLateFromSeed(d1, st));
        int[] cal = new int[26];
        for (int i = 0; i < 26; ++i) {
            cal[i] += mem[n1][i];
            cal[i] += mem[n2][i];
            cal[i] -= 2 * mem[commonParent][i];
        }
        int max = 0, sum = 0;
        for (int i = 0; i < 26; ++i) {
            sum += cal[i];
            max = Math.max(cal[i], max);
        }
        return sum - max;
    }

    private int transLateFromSeed(int totalDepth, int needDepth) {
        return totalDepth - needDepth;
    }
}