算法leetcode

leetcode第361场周赛：树上难题拆解，树上倍增+树形前缀

字数统计: 4.7k字   |   阅读时长: 20分
, , ,

摘要: 本文是 leetcode 第 361 周赛的记录。主要涉及的算法包括模拟、贪心、数论、频数前缀和、树上倍增、树形前缀

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

总览

2023 年 9 月 23 日进行了 leetcode 第 361 场周赛。距离上次参加周赛（2022年12月25日）有了半年多时间了，这半年多时间就业情况有所下降，一些算法课都不好卖了。leetcode 周赛的主要变化就是赞助的公司变少了，参赛的人数变化不太大，这次也是 4000 多人参赛。

本场比赛没有赞助，奖品还是差点意思，前十名可以得水壶，几个幸运数字可以一个扑克牌，如下：

本场比赛前三题比较普通，考察了模拟、贪心、频数前缀和等高频知识点。D 题比较综合，难度较大，比赛时没写出来。成绩如下：

不过赛后冷静下来发现 D 题是把最近公共祖先和树形前缀结合起来了，而这两个点单独来看我们此前都解决过类似的问题，如果能够拆解出来，即可分别解决。特别是最近公共祖先如果有代码模板的话，比赛时可以直接用，非常舒服。

各个题目涉及到的知识点汇总如下：

往期参加比赛的记录如下：

【连载】leetcode周赛

A 题

给你两个正整数 low 和 high 。

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

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

提示：

1
1 <= low <= high <= 1e4

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

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

算法：模拟

枚举 $[low, high]$ 之间的每个整数 $x$，其位数为 $N = \log_{10}{x} + 1$，如果 $N$ 为奇数则跳过，若 $N$ 为偶数，则判断 $x$ 是否为对称整数。

令 $n = N / 2$，先将前 n 位相加，和为 $s1$，再将后 n 位相加，和为 $s_{2}$，若 $s_{1} = s_{2}$，则答案加一。

代码(C++)

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
class Solution {
public:
    int countSymmetricIntegers(int low, int high) {
        int ans = 0;
        for(int x = low; x <= high; ++x)
        {
            int N = log10(x) + 1;
            if(N % 2 == 1)
                continue;
            int n = N / 2;
            int s1 = 0;
            int t = x;
            for(int i = 0; i < n; ++i)
            {
                s1 += t % 10;
                t /= 10;
            }
            int s2 = 0;
            for(int i = 0; i < n; ++i)
            {
                s2 += t % 10;
                t /= 10;
            }
            if(s1 == s2)
                ans++;
        }
        return ans;
    }
};

B 题

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

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

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

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

提示

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

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

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

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

算法：贪心、数论

这里特殊数字的定义是被 25 整除。从初等数论中的整除规则，一个整数能被25整除当且仅当末尾两位数是 00、25、50、75。

这种整除规则在初等数论的书中一般作为基础知识介绍，如果学奥数的话，最早在小学就可以接触到了，并且也比较好背。这里把常见的整除规则罗列一下：

整数 整除规则
2 一个整数能被2整除当且仅当它的个位数是0、2、4、6、8。
5 一个整数能被5整除当且仅当它的个位数是0、5。
10 一个整数能被10整除当且仅当它的末位数字是0。
4 一个整数能被4整除当且仅当它的末尾两位数能被4整除。
8 一个整数能被8整除当且仅当它的末尾三位数能被8整除。
3 一个整数能被3整除当且仅当它的所有数字之和能被3整除。
9 一个整数能被9整除当且仅当它的所有数字之和能被9整除。
11 将奇位上的数字与偶位上的数字分别加起来,再求它们的差,如果这个差是11的倍数(包括0),那么,原来这个数就一定能被11整除。
25 一个整数能被25整除当且仅当它的末尾两位数是00、25、50或75。

整除规则的好处是可以帮助我们快速判断一个整数能否被另一个整数整除，而不用进行实际计算。比如本题中，我们实际要做的就是找到一个最少的操作次数，使得 x 变为以 00、25、50、75 结尾的形式。

定义一个函数 check(num, s)，表示从 num 中删除若干位，使得以 s 结尾的最少删除次数。这样我们要求的实际上就是以下四个结果的最小值：

1
2
3
4
check(num, "25")
check(num, "75")
check(num, "50")
check(num, "00")

而 check 操作可以通过贪心实现，即从右向左枚举，首先找 s[1]，然后在找 s[0] 记录移动次数即可。

代码(C++)

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
class Solution {
public:
    int minimumOperations(string num) {
        int n = num.size();
        int ans = n;
        for(int i = 0; i < n; ++i)
        {
            if(num[i] == '0')
            {
                ans = n - 1;
                break;
            }
        }
        ans = min(ans, check(num, "25"));
        ans = min(ans, check(num, "75"));
        ans = min(ans, check(num, "50"));
        ans = min(ans, check(num, "00"));
        return ans;
    }

    int check(const string& num, string s)
    {
        int n = num.size();
        int ans = n;
        int r = n - 1;
        int t = 0;
        while(r >= 0 && num[r] != s[1])
        {
            r--;
            t++;
        }
        if(r < 0)
            return ans;
        r--;
        while(r >= 0 && num[r] != s[0])
        {
            r--;
            t++;
        }
        if(r < 0)
            return ans;
        ans = min(ans, t);
        return ans;
    }
};

C 题

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

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

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

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

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

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

提示：

1
2
3
4
1 <= nums.length <= 1e5 
1 <= nums[i] <= 1e9
1 <= modulo <= 1e9
0 <= k < modulo

示例 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 。

示例 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 。

算法：频数前缀和

对于数组 nums，影响其趣味子数组个数的主要是满足 nums[i] % m = k 的那些元素，称其为关键元素。

一个子数组 nums[l, r] 为趣味子数组，则需要其中的关键元素个数 cnt 满足 cnt % m = k。

于是一个比较容易想到的思路是，从左到右枚举 $r$，问以 $r$ 结尾的子数组中，有多少个子数组是关键元素个数是 k（模 m 意义下）。

在枚举 $r$ 的过程中维护一个前缀和 s，表示前缀 nums[0..r] 中关键元素的个数；以及一个哈希表 mapping，mapping[s] 表示 nums[0..r-1] 的所有前缀中，关键元素个数为 s（模 m 意义下）的前缀个数。

这样我们通过在 mapping 中寻找前缀为 ((s - k) % m + m) % m 的个数，即为关键元素个数为 k（模 m 意义下）的子数组个数。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    long long countInterestingSubarrays(vector<int>& nums, int modulo, int k) {
        int n = nums.size();
        for(int &x: nums)
            x %= modulo;
        int s = 0;
        unordered_map<int, int> mapping;
        mapping[0] = 1;
        long long ans = 0;
        for(int i = 0; i < n; ++i)
        {
            if(nums[i] == k)
                s = (s + 1) % modulo;
            int target = ((s - k) % modulo + modulo) % modulo;
            ans += mapping[target];
            mapping[s]++;
        }
        return ans;
    }
};

D 题

现有一棵由 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
2
3
4
5
6
7
8
9
1 <= n <= 1e4
edges.length == n - 1
edges[i].length == 3
0 <= ui, vi < n
1 <= wi <= 26
生成的输入满足 edges 表示一棵有效的树
1 <= queries.length == m <= 2e4
queries[i].length == 2
0 <= ai, bi < n

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

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

算法：树上倍增 + 树形前缀

对于每个查询 $(u, v)$，首先找到最近公共祖先 $r$，然后枚举每个可能的边权 $x = 1,\cdots,26$，计算 $uv$ 路径上该边权的数量，记数量最多的边权为 $mode$，数量为 $cnt$，路径 $uv$ 长度为 $l$，于是该查询的答案就是 $l - cnt$。

要高效完成以上查询，有两个关键点，一个是最近公共祖先，一个是 $uv$ 路径上具有边权 $x$ 的边的数量。

最近公共祖先可以通过树上倍增的方式先预处理，之后每个查询可以在 $O(\log n)$ 时间复杂度内得到最近公共祖先。算法和代码模板参考 最近公共祖先问题、树上倍增。

$uv$ 路径上具有边权 $x$ 的边的数量可以通过树形前缀的方式解决，此前我们见过不少这种树形前缀的思路解决祖先链上统计的问题：树的遍历：祖先链上的统计、树形前缀和：在树的DFS过程中维护祖先链的和、力扣1766-互质树。

记 $pre[x][u]$ 表示 $u$ 的祖先链上的各条边中，具有边权 $x$ 的边的数量。这样在查询时，$(u, v)$ 的最近公共祖先为 $r$，于是 $uv$ 路径上具有边权 $x$ 的边的数量即为：

在最近公共祖先的树上倍增预处理过程中，我们还顺便预处理的每个节点的深度 $d[u]$，于是 $uv$ 路径的长度即为：

代码(C++)

其中 dfs，get_fa 两个函数为 LCA 预处理阶段的组件；lowbit，highbit，lca 为 LCA 查询阶段的组件。均为代码模板。

树形前缀 pre 在 LCA 预处理阶段的 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
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
void dfs(int u, int prev, const vector<vector<vector<int>>>& g, vector<int>& d, vector<int>& parent, vector<vector<int>>& pre)
{
    // 访问从 u 出发的所有边
    for(const vector<int>& e: g[u])
    {
        int v = e[0];
        int w = e[1];
        if(v == prev)
            continue;
        d[v] = d[u] + 1;
        parent[v] = u;
        for(int x = 1; x <= 26; ++x)
            pre[x][v] = pre[x][u];
        pre[w][v]++;
        dfs(v, u, g, d, parent, pre);
    }
}

void get_fa(int N, int K, vector<vector<int>>& fa, const vector<int>& parent)
{
    // fa[i][j] := 从 i 爬 2 ^ j 步所到点的 id
    // fa[i][0] := 从 i 爬 1 步所到点的 id
    for(int i = 0; i < N; ++i)
        fa[i][0] = parent[i];
    for(int j = 1; j < K; ++j)
        fa[0][j] = -1;
    for(int j = 1; j < K; ++j)
        for(int i = 1; i < N; ++i)
        {
            if(fa[i][j - 1] == -1)
                fa[i][j] = -1;
            else
                fa[i][j] = fa[fa[i][j - 1]][j - 1];
        }
}

int lowbit(int n)
{
    return n & (-n);
}

int highbit(int n)
{
    int p = lowbit(n);
    while(p != n)
    {
        n -= p;
        p = lowbit(n);
    }
    return p;
}

int lca(int x, int y, const vector<int>& d, const vector<vector<int>>& fa)
{
    // d[x] >= d[y]
    if(d[x] < d[y])
        return lca(y, x, d, fa);
    // 将 y 向上调整直到和 x 一个深度
    int delta = d[x] - d[y];
    while(delta > 0)
    {
        x = fa[x][log2(highbit(delta))];
        delta -= highbit(delta);
    }
    if(x == y)
        return x;
    int n = d.size();
    int m = log2(n);
    while(true)
    {
        if(fa[x][0] == fa[y][0])
            break;
        int k = 1;
        while(k <= m)
        {
            if(fa[x][k] == -1 || fa[y][k] == -1)
                break;
            if(fa[x][k] == fa[y][k])
                break;
            ++k;
        }
        x = fa[x][k - 1];
        y = fa[y][k - 1];
    }
    return fa[x][0];
}

class Solution {
public:
    vector<int> minOperationsQueries(int n, vector<vector<int>>& edges, vector<vector<int>>& queries) {
        vector<vector<vector<int>>> g(n);
        for(vector<int>& e: edges)
        {
            int u = e[0];
            int v = e[1];
            int w = e[2];
            g[u].push_back({v, w});
            g[v].push_back({u, w});
        }

        // 预处理1：d, perent, pre
        vector<int> d(n, 0);
        vector<int> parent(n, -1);
        vector<vector<int>> pre(27, vector<int>(n));
        dfs(0, -1, g, d, parent, pre);

        // 预处理2：fa
        int K = log2(n) + 1;
        vector<vector<int>> fa(n, vector<int>(K));
        get_fa(n, K, fa, parent);

        // 查询
        int m = queries.size();
        vector<int> result(m, -1);
        for(int i = 0; i < m; ++i)
        {
            int u = queries[i][0];
            int v = queries[i][1];
            int r = lca(u, v, d, fa);
            int mode = -1;
            int cnt = -1;
            for(int x = 1; x <= 26; ++x)
            {
                int tmp = pre[x][u] - pre[x][r];
                tmp += pre[x][v] - pre[x][r];
                if(tmp > cnt)
                {
                    cnt = tmp;
                    mode = x;
                }
            }
            int l = (d[u] - d[r]) + (d[v] - d[r]);
            result[i] = l - cnt;
        }
        return result;
    }
};
Share