第426场周赛

Q1. 仅含置位位的最小整数

3370. 仅含置位位的最小整数

给你一个正整数 n。
返回 大于等于 n 且二进制表示仅包含 置位 位的 最小 整数 x 。
置位 位指的是二进制表示中值为 1 的位。

示例 1：

输入： n = 5

输出： 7

解释：

7 的二进制表示是 "111"。

示例 2：

输入： n = 10

输出： 15

解释：

15 的二进制表示是 "1111"。

示例 3：

输入： n = 3

输出： 3

解释：

3 的二进制表示是 "11"。

提示：

  • 1 <= n <= 1000

解法：

思路： 简单的“位运算”题目，将num中的所有数位变为1即可

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int smallestNumber(int num) {
        int res=0;
        int cnt=0;
        while(num){
            res+=pow(2,cnt);
            cnt++;
            num>>=1;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
int smallestNumber(int n) {
    // 计算 n 的二进制中置位位的个数
    int ones = __builtin_popcount(n);
    // 构造包含相同置位位的最小数
    int result = (1 << ones) - 1;
    while (result < n) {
        result = (result << 1) + 1; // 向左移动并补充置位位
    }
    return result;
}

Q2. 识别数组中的最大异常值 ——转换成”两数之和“

3371. 识别数组中的最大异常值

给你一个整数数组 nums。该数组包含 n 个元素，其中 恰好 有 n - 2 个元素是 特殊数字 。剩下的 两个 元素中，一个是所有 特殊数字 的 和 ，另一个是 异常值 。

异常值 的定义是：既不是原始特殊数字之一，也不是所有特殊数字的和。

注意，特殊数字、和 以及 异常值 的下标必须 不同 ，但可以共享 相同 的值。

返回 nums 中可能的 最大异常值。

示例 1：

输入： nums = [2,3,5,10]

输出： 10

解释：

特殊数字可以是 2 和 3，因此和为 5，异常值为 10。

示例 2：

输入： nums = [-2,-1,-3,-6,4]

输出： 4

解释：

特殊数字可以是 -2、-1 和 -3，因此和为 -6，异常值为 4。

示例 3：

输入： nums = [1,1,1,1,1,5,5]

输出： 5

解释：

特殊数字可以是 1、1、1、1 和 1，因此和为 5，另一个 5 为异常值。

提示：

  • 3 <= nums.length <= 105
  • -1000 <= nums[i] <= 1000
  • 输入保证 nums 中至少存在 一个 可能的异常值。

test1:

最开始最容易想到的就是暴力枚举，$O(n^2)$时间复杂度，TLE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int getLargestOutlier(vector<int>& nums) {
        int sum=0;
        int n=nums.size();
        for(int it:nums){
            sum+=it;
        }
        int res=INT_MIN;
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                int tmp=sum-nums[i]-nums[j];
                if(tmp==nums[i])res=max(res,nums[j]);
                if(tmp==nums[j])res=max(res,nums[i]);
            }
        }
        return res;
    }
};

test2:

**Key:枚举每个数字作为异常值**:
  • 假设当前数字 num 是异常值，则其他数字的和应为 specialSum = totalSum - num。
  • 如果 specialSum 能被 2 整除（对这处细节要进行判断），且 specialSum / 2 是有效的和，则 num 是一个可能的异常值。

other:

统计数字频率:

  • 使用哈希表 unordered_set<int> 来统计每个数字的是否存在。
  • 方便快速检查某个数字是否存在。

计算总和:

  • 将数组的总和存储在 totalSum 中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int getLargestOutlier(vector<int>& nums) {
    int sum=0;
    int n=nums.size();
    unordered_set<int>st;
    for(int it:nums){
        sum+=it;
        st.insert(it);
    }
    sort(nums.begin(),nums.end(),greater<int>());
    int res=INT_MIN;
    for(int i=0;i<=n-1;i++){
        int exception_num=nums[i];
        double special_num=(sum-exception_num)*0.5;
        if(special_num!=1.0*(int)special_num)continue;
        if(st.count((int)special_num))return exception_num;
    }
    return res;
}

出现错误：

解答错误868 / 872 个通过的测试用例

输入

nums =

[6,-31,50,-35,41,37,-42,13]

输出

13

预期结果

-35

为什么呢？——仅检查集合中存在性：
使用 st.count((int)special_num) 来判断 (sum - outlier)/2 是否存在于 nums 中。但题目的条件要求得更严格：

  • 异常值（outlier）和和值（sum number）必须是不同的元素（下标不同）。如果 (sum - outlier)/2 与选择的 outlier 数值相同，那么数组中必须至少有两个相同的该数值元素——一个用来作为和值，一个用来作为异常值。
  • 若 (sum - outlier)/2 与 outlier 不同，也要确保 (sum - outlier)/2 实际存在于数组中作为单独的元素（与 outlier 索引不同的元素），而不仅仅是检查一下集合中是否有这个值。

你的代码目前只是简单判断 (sum - exception_num)/2 是否在 st 中存在，而没有考虑元素的频次与下标独立性。这就会导致当 (sum - exception_num)/2 的值刚好等于 exception_num 时，若数组中该值只有一个出现，也会误判为满足条件。

未考虑元素频次 (Frequency) 问题：
举例来说，在你给出的失败用例中，outlier 被错误地判断为 13。此时 (sum - 13)/2 = 13。
你的代码检查到 13 在数组中存在，就直接返回了 13。但实际上数组中只有一个 13，无法同时作为和值与异常值，这不满足题目要求的“下标不同”的条件。因此，这个判断不应通过。

总结：
需要在代码中增加检查条件：

  • 首先确保 (sum - outlier) 是偶数，这样 (sum - outlier)/2 才是整数。
  • 如果 (sum - outlier)/2 等于 outlier 本身，检查该值在数组中的出现次数是否至少为 2。如果只有 1 个出现次数，则不能同时作为和值和异常值，需跳过这种情况。
  • 如果 (sum - outlier)/2 不等于 outlier，则需要确保该值在数组中至少出现一次，且与 outlier 是不同的元素。

TrueSolv：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int getLargestOutlier(vector<int>& nums) {
        int sum=0;
        int n=nums.size();
        unordered_map<int,int>mp;
        for(int it:nums){
            sum+=it;
            mp[it]++;
        }
        sort(nums.begin(),nums.end(),greater<int>());
        int res=INT_MIN;
        for(int i=0;i<=n-1;i++){
            int exception_num=nums[i];
            if((sum-exception_num)&1)continue;
            int special_num=(sum-exception_num)>>1;
            if(special_num==exception_num&&mp[exception_num]==1)continue;
            if(mp.count(special_num))return exception_num;
        }
        return res;
    }
};

Q3. 连接两棵树后最大目标节点数目 I

3372. 连接两棵树后最大目标节点数目 I

有两棵 无向 树，分别有 n 和 m 个树节点。两棵树中的节点编号分别为[0, n - 1] 和 [0, m - 1] 中的整数。

给你两个二维整数 edges1 和 edges2 ，长度分别为 n - 1 和 m - 1 ，其中 edges1[i] = [ai, bi] 表示第一棵树中节点 ai 和 bi 之间有一条边，edges2[i] = [ui, vi] 表示第二棵树中节点 ui 和 vi 之间有一条边。同时给你一个整数 k 。

如果节点 u 和节点 v 之间路径的边数小于等于 k ，那么我们称节点 u 是节点 v 的 目标节点 。注意 ，一个节点一定是它自己的 目标节点 。

请你返回一个长度为 n 的整数数组 answer ，answer[i] 表示将第一棵树中的一个节点与第二棵树中的一个节点连接一条边后，第一棵树中节点 i 的 目标节点 数目的 最大值 。

注意 ，每个查询相互独立。意味着进行下一次查询之前，你需要先把刚添加的边给删掉。

示例 1：

输入：edges1 = [[0,1],[0,2],[2,3],[2,4]], edges2 = [[0,1],[0,2],[0,3],[2,7],[1,4],[4,5],[4,6]], k = 2

输出：[9,7,9,8,8]

解释：

  • 对于 i = 0 ，连接第一棵树中的节点 0 和第二棵树中的节点 0 。
  • 对于 i = 1 ，连接第一棵树中的节点 1 和第二棵树中的节点 0 。
  • 对于 i = 2 ，连接第一棵树中的节点 2 和第二棵树中的节点 4 。
  • 对于 i = 3 ，连接第一棵树中的节点 3 和第二棵树中的节点 4 。
  • 对于 i = 4 ，连接第一棵树中的节点 4 和第二棵树中的节点 4 。

img

示例 2：

输入：edges1 = [[0,1],[0,2],[0,3],[0,4]], edges2 = [[0,1],[1,2],[2,3]], k = 1

输出：[6,3,3,3,3]

解释：

对于每个 i ，连接第一棵树中的节点 i 和第二棵树中的任意一个节点。

img

提示：

  • 2 <= n, m <= 1000
  • edges1.length == n - 1
  • edges2.length == m - 1
  • edges1[i].length == edges2[i].length == 2
  • edges1[i] = [ai, bi]
  • 0 <= ai, bi < n
  • edges2[i] = [ui, vi]
  • 0 <= ui, vi < m
  • 输入保证 edges1 和 edges2 都表示合法的树。
  • 0 <= k <= 1000

MyTrueSolv

下面是对你的算法思路的详细分析和思考过程示例。

问题回顾：
你有两棵无向树Tree1和Tree2，节点分别为n和m个。对于Tree1中的每个节点 i，你可以选择将Tree1的节点 i 和 Tree2的某个节点 j 用一条边连接起来。连接完成后，从节点 i 出发，你可以在新形成的图中(包含两棵树和新加的那条边)进行最多 k 步的移动。你的目标是在这 k 步之内能到达的 目标节点数目最大化，目标节点不仅包括 Tree1 的节点，也包括 Tree2 的节点。

由于要求对 Tree1 中的每个节点 i 都进行一次这样的查询（并且查询之间互不干扰，即连接完后不保存状态，下一次查询是独立的），我们需要为每个 i 找到：当选择最优的连接对象 j（Tree2中的某个节点）后，从 i 出发可达的节点数目最大值。

思考过程：

  1. 距离与层数限制：
    我们有一个距离限制 k。当把 Tree1 的节点 i 与 Tree2 的节点 j 连接起来时，从 i 出发到达 Tree2 的节点 j 的距离为1（因为新加的那条边就是一条边长）。这样一来，从 i 出发在总距离 k 内能在 Tree2 里继续前进的步数就只有 k - 1 了。

  2. 分开考虑两棵树的可达性：
    我们希望从 i 出发（在 Tree1 中）能到达多少节点，以及在连接到 Tree2 的某个节点 j 后，又能在 Tree2 内额外到达多少节点。

    因此可以将问题拆解为两个独立的子问题：

    • 子问题A：在 Tree1 中，从每个节点出发，半径为 k 的可达节点数是多少？
    • 子问题B：在 Tree2 中，从每个节点出发，半径为 k-1 的可达节点数是多少？

    为什么是 k-1？因为当你从 Tree1 的 i 跳到 Tree2 的 j 时已经用掉了一步，那么留给在 Tree2 中扩展的步数就剩 k-1。

  3. 预处理的思路：
    对 Tree1 来说，我们对每个节点 i 都进行一次 BFS（或DFS）计算在半径 k 内能访问的节点数目，这得到一个数组 counts_in_tree1[i]。

    对 Tree2 来说，我们也对每个节点 j 做同样的处理，不过这里的半径是 k-1，得到 counts_in_tree2[j]。

  4. 最大化目标：
    对于给定的 i，我们要在 Tree2 找一个节点 j 来连接，使得从 i 出发最终可达的节点数最大。可达节点数由两部分组成：

    • 在 Tree1 内部半径 k 可达的节点数：counts_in_tree1[i]
    • 在 Tree2 内部半径 k-1 可达的节点数：counts_in_tree2[j]

    因为每次查询是独立的，我们可以“自由”选择 Tree2 中的节点 j 来实现最大可达数。所以对于给定的 i，最佳选择自然是取 counts_in_tree2[j] 的最大值（我们可以选择能带来最多可达节点数的那个 j）。

    因此，我们不必对每个 i 都遍历 Tree2 来找最大值，只需在预处理时把 Tree2 的 counts_in_tree2[j] 的最大值求出来，并称之为 max_count_in_tree2。

  5. 最终答案：
    对于每个节点 i （Tree1），答案就是 counts_in_tree1[i] + max_count_in_tree2。

    这样就省掉了对每个查询反复搜索 Tree2 的开销。

你的代码逻辑对应上述思路：

  • 首先，你建立了 Tree1 和 Tree2 的邻接表。
  • 对每个节点 i in Tree1，用 BFS 算出半径 k 内可到达的节点数，存入 counts_in_tree1[i]。
  • 对每个节点 j in Tree2，用 BFS 算出半径 (k-1) 内可到达的节点数。然后找到所有 j 中的最大值 max_count_in_tree2。
  • 最后对于每个 i，直接计算 counts_in_tree1[i] + max_count_in_tree2 即为答案。

该思路的优劣势分析：

  • 优点：
    • 清晰地将问题分解为对两棵树分别进行半径搜索的预处理，然后在查询时快速合并结果。
    • 将原本复杂的“选择最优连接点”问题转化为简单地取 max_count_in_tree2 的操作。
  • 潜在问题/不足：
    • 时间复杂度可能较高，因为要对每个节点在 Tree1 和 Tree2 中各进行一次 BFS，复杂度大约 O(n(n+m)+m(n+m))，对于 n,m <= 1000 的情况可能还算可行，但不是很高效。如果数据更大，会有性能压力。
    • 需要仔细证明该贪心选择（即总是选择能给出最大 Tree2 可达数的节点）是正确的。根据题意，每个查询都是独立的，所以为每个 i，可以各自选择 Tree2 中最优的节点 j，这确保了最大值的利用是合理的。

总结：
你的算法本质是通过预处理两个树各自的可达节点数，分离了“搜索 Tree1 内部”和“搜索 Tree2 内部”这两个操作，然后利用查询独立性和自由选择权，将复杂问题化简为：
答案(i) = 在 Tree1 内 i 节点半径 k 可达数 + Tree2 内最大半径 (k-1) 可达数。

这个思路在理解和实现上都比较直观，同时能确保较好的正确性和可理解性。

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
class Solution {
public:
    // Function to compute reachable nodes within distance k using BFS
    int bfs_count(vector<vector<int>>& graph, int start, int k) {
        queue<pair<int, int>> q; // {node, distance}
        vector<bool> visited(graph.size(), false);
        q.push({start, 0});
        visited[start] = true;

        int count = 0;
        while (!q.empty()) {
            auto [node, dist] = q.front();
            q.pop();
            count++;
            if (dist == k) continue;
            for (int neighbor : graph[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.push({neighbor, dist + 1});
                }
            }
        }
        return count;
    }

    vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2, int k) {
        int n = edges1.size() + 1; // Number of nodes in tree1
        int m = edges2.size() + 1; // Number of nodes in tree2

        // Handle special case for k = 0
        if (k == 0) {
            return vector<int>(n, 1); // Each node can only reach itself
        }

        // Build adjacency lists for both trees
        vector<vector<int>> tree1(n), tree2(m);
        for (auto& edge : edges1) {
            tree1[edge[0]].push_back(edge[1]);
            tree1[edge[1]].push_back(edge[0]);
        }
        for (auto& edge : edges2) {
            tree2[edge[0]].push_back(edge[1]);
            tree2[edge[1]].push_back(edge[0]);
        }

        // Precompute the number of nodes within distance k for each node in tree1
        vector<int> counts_in_tree1(n);
        for (int i = 0; i < n; ++i) {
            counts_in_tree1[i] = bfs_count(tree1, i, k);
        }

        // Precompute the maximum number of nodes within distance k - 1 in tree2
        int max_count_in_tree2 = 0;
        for (int i = 0; i < m; ++i) {
            max_count_in_tree2 = max(max_count_in_tree2, bfs_count(tree2, i, k - 1));
        }
        // Compute the answer for each node in tree1
        vector<int> answer(n);
        for (int i = 0; i < n; ++i) {
            answer[i] = counts_in_tree1[i] + max_count_in_tree2;
        }
        return answer;
    }
};

OtherSolv

算法思路：

  1. 数据准备：
    他使用 e[] 和 E[] 两个数组分别存储 Tree1 和 Tree2 的邻接关系。

  2. 计算 Tree1 中各节点的可达数：
    对于 Tree1 中的每个节点 i，直接调用一个带有剪枝（步数限制）的 DFS 函数 dfs 来计算在不超过 K 步的范围内可达多少个节点。这一步与之前 BFS 不同之处在于，这里直接使用 DFS，在 DFS 时把剩余的步数 rem 作为参数传递，当 rem 为 0 时不再向下搜索。

    如此，对于 Tree1 的每个节点 i，执行一次 dfs(i, -1, K, e) 来计算可达节点数，并将结果存入 ans[i]。

  3. 计算 Tree2 中最大可达数：
    当 K > 0 时，还需要考虑连接到 Tree2 带来的增益。他同样对 Tree2 的每个节点 i 执行一次 dfs(i, -1, K - 1, E) 来计算在 Tree2 中不超过 (K-1) 步的可达节点数。
    然后他取这些值的最大值 best。

  4. 合并结果：
    对于每个 Tree1 的节点 i，将 ans[i] （Tree1 内的可达数）加上 best （Tree2 内最大可达数）作为最终答案并返回。

总结：
你的算法与他的算法在解决问题的核心思路和最终流程上是高度一致的：

  • 在 Tree1 中计算每个节点的可达数。
  • 在 Tree2 中计算可达数的最大值。
  • 将两者相加得到结果。

将问题分解和合并的思路。

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
class Solution {
public:
    vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2, int K) {
        int n = (int)edges1.size() + 1;  // 第一棵树的节点数
        int N = (int)edges2.size() + 1;  // 第二棵树的节点数

        // 使用邻接表存储两棵树的结构
        // e 表示第一棵树的邻接表，E 表示第二棵树的邻接表
        vector<int> e[n], E[N];
        for (auto &edge : edges1) {
            e[edge[0]].push_back(edge[1]);
            e[edge[1]].push_back(edge[0]);
        }
        for (auto &edge : edges2) {
            E[edge[0]].push_back(edge[1]);
            E[edge[1]].push_back(edge[0]);
        }

        // 定义一个匿名递归函数 (lambda) dfs 来计算从某个起点 sn 出发，在不超过 rem 步（距离）的情况下，
        // 能够到达的节点数目。fa 表示父节点，避免回溯重复；rem 表示剩余步数；e 为当前树的邻接表。
        auto dfs = [&](auto &&self, int sn, int fa, int rem, vector<int> *e) -> int {
            int ret = 1;  // 当前节点计数为 1
            if (rem > 0) {
                // 当剩余步数大于 0 时，可以继续向邻接节点扩展
                for (int fn : e[sn]) {
                    if (fn != fa) {
                        // 避免回到父节点，从而形成环
                        ret += self(self, fn, sn, rem - 1, e);
                    }
                }
            }
            return ret;
        };

        // ans[i] 将存储第一棵树中节点 i 在不连接第二棵树的情况下，
        // 能在距离 K 内到达的节点数（包括自身）
        vector<int> ans(n);
        for (int i = 0; i < n; i++) {
            ans[i] = dfs(dfs, i, -1, K, e); 
        }

        // 如果 K > 0，那么连接一条边到第二棵树后，有额外的可达节点。
        // 连接会消耗 1 步距离，因此在第二棵树中，我们只能在 K-1 的范围内搜索可达节点数。
        if (K > 0) {
            int best = 0;
            // 遍历第二棵树的每个节点，计算在 K-1 步内可达的最大节点数
            for (int i = 0; i < N; i++) {
                best = max(best, dfs(dfs, i, -1, K - 1, E));
            }
            // 对于第一棵树中的每个节点 i，都可以选择与第二棵树中能给出 best 节点数的节点相连接。
            // 因为问题允许每个查询（即每个 i）独立地选择不同的第二棵树节点进行连接，
            // 所以直接加上该最大值 best 就能得到连接后可能达到的最大目标节点数。
            for (int i = 0; i < n; i++) {
                ans[i] += best;
            }
        }
        // 返回答案
        return ans;
    }
};

Q4.3373. 连接两棵树后最大目标节点数目 II ——黑白染色，二分图

3373. 连接两棵树后最大目标节点数目 II

有两棵 无向 树，分别有 n 和 m 个树节点。两棵树中的节点编号分别为[0, n - 1] 和 [0, m - 1] 中的整数。

给你两个二维整数 edges1 和 edges2 ，长度分别为 n - 1 和 m - 1 ，其中 edges1[i] = [ai, bi] 表示第一棵树中节点 ai 和 bi 之间有一条边，edges2[i] = [ui, vi] 表示第二棵树中节点 ui 和 vi 之间有一条边。

如果节点 u 和节点 v 之间路径的边数是偶数，那么我们称节点 u 是节点 v 的 目标节点 。注意 ，一个节点一定是它自己的 目标节点 。

请你返回一个长度为 n 的整数数组 answer ，answer[i] 表示将第一棵树中的一个节点与第二棵树中的一个节点连接一条边后，第一棵树中节点 i 的 目标节点 数目的 最大值 。

注意 ，每个查询相互独立。意味着进行下一次查询之前，你需要先把刚添加的边给删掉。

示例 1：

输入：edges1 = [[0,1],[0,2],[2,3],[2,4]], edges2 = [[0,1],[0,2],[0,3],[2,7],[1,4],[4,5],[4,6]]

输出：[8,7,7,8,8]

解释：

  • 对于 i = 0 ，连接第一棵树中的节点 0 和第二棵树中的节点 0 。
  • 对于 i = 1 ，连接第一棵树中的节点 1 和第二棵树中的节点 4 。
  • 对于 i = 2 ，连接第一棵树中的节点 2 和第二棵树中的节点 7 。
  • 对于 i = 3 ，连接第一棵树中的节点 3 和第二棵树中的节点 0 。
  • 对于 i = 4 ，连接第一棵树中的节点 4 和第二棵树中的节点 4 。

img

示例 2：

输入：edges1 = [[0,1],[0,2],[0,3],[0,4]], edges2 = [[0,1],[1,2],[2,3]]

输出：[3,6,6,6,6]

解释：

对于每个 i ，连接第一棵树中的节点 i 和第二棵树中的任意一个节点。

img提示：

  • 2 <= n, m <= 105
  • edges1.length == n - 1
  • edges2.length == m - 1
  • edges1[i].length == edges2[i].length == 2
  • edges1[i] = [ai, bi]
  • 0 <= ai, bi < n
  • edges2[i] = [ui, vi]
  • 0 <= ui, vi < m
  • 输入保证 edges1 和 edges2 都表示合法的树。

GPTTrueSolv

给定两棵无向树 A 和 B，A 有 n 个节点 (编号 0~n-1)，B 有 m 个节点 (编号 0~m-1)。有以下定义：

  • 如果在一张图中，对两个节点 u 与 v 的距离(边数)为 d ，若 d 的奇偶性为偶数，那么称 u 是 v 的“目标节点”(target node)。
  • 题目中可以在第一棵树（A）中的某个节点 i 与第二棵树（B）中的某个节点 j 之间添加一条边，将两棵树连接成一张图。
  • 对于 A 中的每个节点 i，我们希望在 B 中找一个合适的节点 j 去连接，使得 i 的目标节点数量最大化。返回一个长度为 n 的数组，其中第 i 个元素表示此最大目标节点数目。

注意：题目要求对每个 i 的查询都是独立进行的，即在为 i 寻找最优的 j 时，不会影响其他 i 的选择。

关键观察

  1. 距离奇偶性的可分解性
    在树中，距离的奇偶性有一个重要性质：
    如果我们在一棵树上固定一个根节点 r，那么任意节点 x 的深度为 dist(r, x) ，则 dist(u, v) 的奇偶性 = dist(r, u) XOR dist(r, v) 的奇偶性。也就是说，两个节点的距离的奇偶性取决于它们各自到根的距离的奇偶性是否相同（相同则距离偶，不同则距离奇）。

  2. 连接一条边后距离的变化
    我们在 A 中选择节点 i，在 B 中选择节点 j，连接 i-j。
    对于 A 中的节点 a，与 i 的距离在添加边后并不会变短（因为 A 中节点间原先已最短，不会通过 B 绕路变短），所以 A 中节点到 i 的距离奇偶性保持不变。

    对于 B 中的节点 b，连接后 dist(i, b) = dist(i, j) + dist(j, b)，但 dist(i, j) = 1（新增边）且 dist(i, i)=0，所以：

    1
    dist(i, b) = 1 + dist_B(j, b)

    因此，(i 到 b 的距离奇偶性) = (1 + dist_B(j, b) 的奇偶性) = (dist_B(j, b) 的奇偶性取反)

    当我们从 B 的某个固定根节点（例如 0 号节点）出发时，有： dist_B(j, b) 的奇偶性 = dist_B(0, j) XOR dist_B(0, b) 的奇偶性。

    如果 dist_B(0, b) 与 dist_B(0, j) 的奇偶性相同，则 dist_B(j, b) 为偶数；如果不同则为奇数。

    因此，选择不同的 j 会对在 B 中产生不同的奇偶分布翻转。

  3. 计数目标节点
    将 A 和 B 分别以 0 号节点为根（或者任意节点为根）做一次 BFS 计算每个节点到根的距离奇偶性。

    • 对 A 来说：
      定义 A_even = A 中距离 root_A=0 节点为偶数的节点数量
      定义 A_odd = A 中距离 root_A=0 节点为奇数的节点数量

      对于 A 中节点 i，如果 dist_A(0, i) 为偶数，那么与 i 距离为偶数的 A 中节点数量 = A_even，因为 i 与 root_A=0 的奇偶性相同的节点与 i 的距离就是偶数。
      同理，如果 dist_A(0, i) 为奇数，则偶距离节点数量 = A_odd。

    • 对 B 来说：
      定义 B_even = B 中距离 root_B=0 节点为偶数的节点数量
      定义 B_odd = B 中距离 root_B=0 节点为奇数的节点数量

      当我们连接 i 与 j 时，B 中的目标节点数是 B 中与 dist_B(j, b) 为偶数的节点数。但由于 dist(i, b)=1+dist_B(j, b)，要 i 的目标节点 b 的条件是 dist(i, b) 为偶数，即 dist_B(j, b) 为奇数。

      当 dist_B(0, j) 为偶数时：
      dist_B(j, b) 奇偶性 = dist_B(0, j) XOR dist_B(0, b) = 0 XOR dist_B(0, b)的奇偶性 = dist_B(0, b)的奇偶性
      此时想要 dist_B(j,b) 为奇数 => b 的 dist_B(0,b) 为奇数 => 这样的 b 有 B_odd 个。

      当 dist_B(0, j) 为奇数时：
      dist_B(j, b) 为奇数的情况是 dist_B(0,b) 与 dist_B(0,j) 奇偶性不同。由于 dist_B(0,j)为奇数，此时要 dist_B(j,b)为奇数，b 必须有 dist_B(0,b)为偶数，即有 B_even 个。

    因此，连接点 j 的奇偶性决定了在 B 中有多少目标节点数（偶距离节点数）。我们可以选择 j 使得在 B 中的目标节点数达到最大值，即： max_B = max(B_even, B_odd)

  4. 最终结果
    对每个 i：

    • 如果 dist_A(0,i) 为偶数，A 中的偶距离节点数为 A_even
    • 如果 dist_A(0,i) 为奇数，A 中的偶距离节点数为 A_odd

    B 中我们可以自由选择 j，从而在 B 中获得 max_B 个偶距离节点。

    因此，
    answer[i] = (dist_A(0,i)为偶时：A_even；为奇时：A_odd) + max_B

时间复杂度

  • 构建两棵树的邻接表：O(n + m)
  • 各做一次 BFS 求深度奇偶性和计数：O(n + m)
  • 最终输出结果：O(n)

总体 O(n + m) 可行。

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
class Solution {
public:
    vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2) {
        int n = (int)edges1.size() + 1;
        int m = (int)edges2.size() + 1;
        // 构建树 A
        vector<vector<int>> adjA(n);
        for (auto &e : edges1) {
            adjA[e[0]].push_back(e[1]);
            adjA[e[1]].push_back(e[0]);
        }
        // 构建树 B
        vector<vector<int>> adjB(m);
        for (auto &e : edges2) {
            adjB[e[0]].push_back(e[1]);
            adjB[e[1]].push_back(e[0]);
        }
        // BFS 求 A 中每个点到 0 的距离奇偶性，并统计 A_even, A_odd
        vector<int> distA(n, -1);
        distA[0] = 0;
        
        queue<int>q; q.push(0);
        while(!q.empty()){
            int u = q.front();q.pop();
            for (auto w : adjA[u]) {
                if (distA[w] == -1) {
                    distA[w] = distA[u]+1;
                    q.push(w);
                }
            }
        }
        
        int A_even=0, A_odd=0;
        for (int i=0;i<n;i++){
            if (distA[i]%2==0) A_even++; else A_odd++;
        }
        // BFS 求 B 中每个点到 0 的距离奇偶性，并统计 B_even, B_odd
        vector<int> distB(m, -1);
        distB[0]=0;
        
        queue<int>q;q.push(0);
        while(!q.empty()){
            int u = q.front();q.pop();
            for (auto w : adjB[u]) {
                if (distB[w]==-1) {
                    distB[w]=distB[u]+1;
                    q.push(w);
                }
            }
        }
        
        int B_even=0, B_odd=0;
        for (int i=0;i<m;i++){
            if (distB[i]%2==0) B_even++; else B_odd++;
        }
        int max_B = max(B_even,B_odd);
        vector<int> answer(n);
        for (int i=0;i<n;i++){
            if (distA[i]%2==0) {
                // i 与 root_A parity 相同 => 偶距离节点数 = A_even
                answer[i]=A_even+max_B;
            } else {
                answer[i]=A_odd+max_B;
            }
        }
        return answer;
    }
};

OtherSolv

DFS解法

对于一棵树，我们把这棵树的所有节点染成黑色或者白色，规则如下：

黑色节点的所有邻居都是白色。
白色节点的所有邻居都是黑色。

这个想法来自国际象棋的棋盘：所有黑色格子的四方向邻居都是白色格子，所有白色格子的四方向邻居都是黑色格子。也可以从图论的角度理解，因为树一定是二分图。

染色后，从任意节点出发，每走一步，节点的颜色都会改变。所以：

  • 从某个节点走奇数步之后，一定会走到异色节点上。
  • 从某个节点走偶数步之后，一定会走到同色节点上。
    所以从任意黑色节点出发，所找到的目标节点，一定都是黑色；从任意白色节点出发，所找到的目标节点，一定都是白色。

不妨从节点 0 开始 DFS。（你想从其他节点开始 DFS 也可以。无论从哪个点开始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
class Solution {
public:
    vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2) {
        // count函数：
        // 输入：某棵树的边集
        // 输出：pair(构建好的图, cnt数组)
        //   其中 cnt[0]为以0为根深度为偶数的节点数
        //        cnt[1]为以0为根深度为奇数的节点数
        auto count = [](vector<vector<int>>& edges) {
            int n = (int)edges.size() + 1;
            vector<vector<int>> g(n);
            // 构建无向图的邻接表
            for (auto &e : edges) {
                int x = e[0], y = e[1];
                g[x].push_back(y);
                g[y].push_back(x);
            }

            // cnt[0]: 偶数深度的节点数
            // cnt[1]: 奇数深度的节点数
            array<int,2> cnt = {0,0};

            // 使用 DFS 遍历，从0号节点出发，fa为父节点，d为当前节点深度奇偶性(0偶1奇)
            auto dfs = [&](auto&& self, int x, int fa, int d)->void {
                cnt[d]++;
                for (int y : g[x]) {
                    if (y != fa) self(self, y, x, d ^ 1);
                }
            };

            // 从0号节点出发，深度为0(偶)
            dfs(dfs, 0, -1, 0);

            return make_pair(g, cnt);
        };

        // 处理树 B，得到B中偶数深度与奇数深度节点的数量
        auto [_, cnt2] = count(edges2);
        int max2 = max(cnt2[0], cnt2[1]); // B中最大可获取的偶距离节点数

        // 处理树 A，得到A中偶数深度与奇数深度节点的数量
        auto [g, cnt1] = count(edges1);

        // 初始化答案数组，每个节点的答案基础部分为max2（来自B的最大值）
        vector<int> ans(g.size(), max2);

        // 再次对A进行DFS，以确定A中每个节点的奇偶深度，然后加上A内部与其深度奇偶性相同的节点数
        auto dfs = [&](auto&& self, int x, int fa, int d)->void {
            // 当前节点 x 的奇偶深度为 d，A中对应奇偶深度的节点数为 cnt1[d]
            ans[x] += cnt1[d];
            for (int y : g[x]) {
                if (y != fa) self(self, y, x, d ^ 1);
            }
        };
        // 从0开始DFS，此时深度奇偶为0
        dfs(dfs, 0, -1, 0);

        return ans;
    }
};

其他：

这段代码中的 dfs 函数是采用 Lambda 表达式 + 递归调用自身 的写法，并通过参数传递自身 (auto&& dfs) 来实现递归。下面是详细说明：

1
2
3
4
5
6
auto dfs = [&](auto&& dfs, int x,int fa,int d)->void {
    cnt[d]++; // 根据当前节点深度奇偶性计数
    for(int y:g[x]) {
        if(y != fa) // 确保不走回头路避免死循环
            dfs(dfs, y, x, d^1); // 递归调用自身，对子节点进行遍历
};

为什么要这样写？

  1. Lambda 递归的需要：
    在 C++ 中，Lambda 表达式默认不能直接引用自己，即无法在 Lambda 内直接调用自身名字。这是因为 Lambda 表达式没有在其作用域内定义自身的标识符。

    为了解决这个问题，需要通过额外的参数将自身的函数引用捕获进去。

    1
    auto dfs = [&](auto&& dfs, int x,int fa,int d)->void { ... };

    这里 dfs 是一个 Lambda 对象，在定义时将自身通过第一个形参 auto&& dfs 传递进去，这样就可以在函数体内使用 dfs(dfs, ...) 来递归调用自身。

  2. 参数含义：

    • x: 当前遍历的节点编号。
    • fa: 当前节点的父节点编号，用于防止回溯时走回头路形成环。
    • d: 当前节点的深度奇偶性（0表示偶数深度，1表示奇数深度）。d^1 是通过异或操作翻转深度的奇偶性。

  3. 计数原理：
    cnt[d]++ 会根据当前节点的深度奇偶性进行统计。例如：

    • 当 d = 0 时，表示当前节点位于偶数深度，这时 cnt[0] 自增。
    • 当 d = 1 时，表示当前节点位于奇数深度，这时 cnt[1] 自增。

    最终 cnt[0] 和 cnt[1] 会记录整棵树中分别有多少节点在偶数深度和奇数深度上。

  4. 递归过程： 对于每个节点 x，我们会遍历其所有邻居 y。若 y 不是 fa（父节点），则继续向下递归搜索子树，深度奇偶性也随层级深入不断翻转 (d^1)。

  • 这种写法是为了解决 Lambda 内部递归调用的技术手段。
  • fa 参数保证树的 DFS 不会回溯成环。
  • d 参数用来在 DFS 过程中实时记录节点深度的奇偶性，以实现快速统计奇偶深度节点数量。

第145场双周赛

Q1. 使数组的值全部为 K 的最少操作次数

3375. 使数组的值全部为 K 的最少操作次数

给你一个整数数组 nums 和一个整数 k 。

如果一个数组中所有 严格大于 h 的整数值都 相等 ，那么我们称整数 h 是 合法的 。

比方说，如果 nums = [10, 8, 10, 8] ，那么 h = 9 是一个 合法 整数，因为所有满足 nums[i] > 9 的数都等于 10 ，但是 5 不是 合法 整数。

你可以对 nums 执行以下操作：

  • 选择一个整数 h ，它对于 当前 nums 中的值是合法的。
  • 对于每个下标 i ，如果它满足 nums[i] > h ，那么将 nums[i] 变为 h 。

你的目标是将 nums 中的所有元素都变为 k ，请你返回 最少 操作次数。如果无法将所有元素都变 k ，那么返回 -1 。

示例 1：

输入：nums = [5,2,5,4,5], k = 2

输出：2

解释：

依次选择合法整数 4 和 2 ，将数组全部变为 2 。

示例 2：

输入：nums = [2,1,2], k = 2

输出：-1

解释：

没法将所有值变为 2 。

示例 3：

输入：nums = [9,7,5,3], k = 1

输出：4

解释：

依次选择合法整数 7 ，5 ，3 和 1 ，将数组全部变为 1 。

提示：

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100
  • 1 <= k <= 100

MySolv

转换

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
class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        // 使用 set 去重并自动排序
        // new_arr 中保存了所有的 distinct 值，且从小到大有序
        set<int> st(nums.begin(), nums.end());
        vector<int> new_arr(st.begin(), st.end());

        int maxx = new_arr.back();    // 数组中最大的 distinct 值
        int minn = new_arr.front();  // 数组中最小的 distinct 值

        // 情况1：k 大于数组中的最大值 maxx
        // 因为操作只能往下降值（将大于h的值变为h），
        // 无法把值增大到 k，所以如果 k > maxx 则不可能实现。
        if (k > maxx) return -1;

        // 情况2：k 小于数组中的最小值 minn
        // 例如：nums 的 distinct 值为 [3,5,7,9]，k=1
        // 因为 k 比所有 distinct 值都小，我们需要一层一层往下压。
        // 每一个 distinct 层需要一次操作，最终压到 k，总共需要 distinct.size() 次操作。
        if (k < minn) {
            return (int)new_arr.size();
        }

        // 情况3：k 等于最大 distinct 值 maxx
        // 这里有特殊情况要考虑：
        // (a) 如果 distinct.size() == 1 且 唯一值就是 k，那么数组本来就全为 k，不需要操作，返回0。
        // (b) 否则无法通过操作来把其他值变成 k，因为如果存在比 k 小的 distinct 值，则无法提高它们的值（只能降不能升）。
        // 根据题意与之前逻辑，这里直接返回 -1。
        if (k == maxx) {
            if (new_arr.size() == 1 && minn == k) return 0;
            return -1;
        }
        // 情况4：k 等于最小 distinct 值 minn
        // 例如 distinct = [2,5,5,10] (最终 unique为[2,5,10])，k=2
        // 我们需要把所有大于2的数都压到2的层，一般每个 distinct 值需要一次操作。
        // 比 k 大的 distinct 值有 (new_arr.size() - 1) 个（除去 k 本身那一层）
        // 所以需要 new_arr.size() - 1 次操作。
        if (k == minn) {
            return (int)new_arr.size() - 1;
        }
        // 情况5：如果 k 在 (minn, maxx) 之间
        // 例如 distinct = [2,4,5], k=3
        // 我们无法直接在降值操作中“跳跃”到 k，因为中间有比 k 小的 distinct 值 (2)，
        // 无法将它们变到更大的值 k。这样就不可能让所有值最终变为 k。
        // 因此返回 -1。
        return -1;
    }
};

Q2. 破解锁的最少时间 I ——暴力枚举、贪心间的选择

3376. 破解锁的最少时间 I

Bob 被困在了一个地窖里，他需要破解 n 个锁才能逃出地窖，每一个锁都需要一定的 能量 才能打开。每一个锁需要的能量存放在一个数组 strength 里，其中 strength[i] 表示打开第 i 个锁需要的能量。

Bob 有一把剑，它具备以下的特征：

  • 一开始剑的能量为 0 。
  • 剑的能量增加因子 X 一开始的值为 1 。
  • 每分钟，剑的能量都会增加当前的 X 值。
  • 打开第 i 把锁，剑的能量需要到达 至少 strength[i] 。
  • 打开一把锁以后，剑的能量会变回 0 ，X 的值会增加一个给定的值 K 。

你的任务是打开所有 n 把锁并逃出地窖，请你求出需要的 最少 分钟数。

请你返回 Bob 打开所有 n 把锁需要的 最少 时间。

示例 1：

输入：strength = [3,4,1], K = 1

输出：4

解释：

时间 能量 X 操作 更新后的 X
0 0 1 什么也不做 1
1 1 1 打开第 3 把锁 2
2 2 2 什么也不做 2
3 4 2 打开第 2 把锁 3
4 3 3 打开第 1 把锁 3

无法用少于 4 分钟打开所有的锁，所以答案为 4 。

示例 2：

输入：strength = [2,5,4], K = 2

输出：5

解释：

时间 能量 X 操作 更新后的 X
0 0 1 什么也不做 1
1 1 1 什么也不做 1
2 2 1 打开第 1 把锁 3
3 3 3 什么也不做 3
4 6 3 打开第 2 把锁 5
5 5 5 打开第 3 把锁 7

无法用少于 5 分钟打开所有的锁，所以答案为 5 。

提示：

  • n == strength.length
  • 1 <= n <= 8
  • 1 <= K <= 10
  • 1 <= strength[i] <= 10^6

MyTrueSolv

看到1<=n<=8,考虑暴力枚举，每次枚举出一个开锁顺序，然后模拟计算开锁时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
typedef long long ll;
class Solution {
public:
    int findMinimumTime(vector<int>& strength, int K) {
        int n=strength.size();
        vector<int>myorder(n);
        for(int i=0;i<n;i++)myorder[i]=i;
        int ans=INT_MAX;
        do{
            int time=0;
            ll X=1;  
            ll energy=0;
            for (int i=0;i<n;i++) {
                int s=strength[myorder[i]];
                ll need=(s + X - 1)/X;  
                time+=(int)need;
                energy=0;
                X+=K;
            }
            ans=min(ans,time);
        }while(next_permutation(myorder.begin(),myorder.end()));
        return ans;
    }
};

贪心策略严格来说，是一种直觉。更多要求的是在贪心算法通过后的数学证明。

如本题，二分搜索+贪心，每次开e恰好能打开的最大锁，贪心失败

1
2
3
4
strength =
[7,3,6,18,22,50]
K =
4

贪心开锁顺序：[3, 7, 6, 22, 18, 50], 当e:17->38时，直接开18,e=0,x=21；e=21,x=21; e=42, x=21;e=63,x=21,开玩全部锁，t=4; 最优开锁顺序：[3, 7, 6, 22, 50, 18]，当e:17->38时，选择开50, e=38, x=17; e=55,x=17,开50，e=0,x=21;e=21,x=21,开18，开完全部锁，t= 3;

Q3.使两个整数相等的数位操作 ——质数筛+Dijkstra数位

3377. 使两个整数相等的数位操作

给你两个整数 n 和 m ，两个整数有 相同的 数位数目。

你可以执行以下操作 任意 次：

  • 从 n 中选择 任意一个 不是 9 的数位，并将它 增加 1 。
  • 从 n 中选择 任意一个 不是 0 的数位，并将它 减少 1 。

任意时刻，整数 n 都不能是一个 质数 ，意味着一开始以及每次操作以后 n 都不能是质数。

进行一系列操作的代价为 n 在变化过程中 所有 值之和。

请你返回将 n 变为 m 需要的 最小 代价，如果无法将 n 变为 m ，请你返回 -1 。

一个质数指的是一个大于 1 的自然数只有 2 个因子：1 和它自己。

示例 1：

输入：n = 10, m = 12

输出：85

解释：

我们执行以下操作：

  • 增加第一个数位，得到 n = 20 。
  • 增加第二个数位，得到 n = 21 。
  • 增加第二个数位，得到 n = 22 。
  • 减少第一个数位，得到 n = 12 。

示例 2：

输入：n = 4, m = 8

输出：-1

解释：

无法将 n 变为 m 。

示例 3：

输入：n = 6, m = 2

输出：-1

解释：

由于 2 已经是质数，我们无法将 n 变为 m 。

提示：

  • 1 <= n, m < 10^4
  • n 和 m 包含的数位数目相同。

MyTrueSolv

题目的目标是将整数 n 通过一系列位操作（+1 或 -1）转变为整数 m，且在整个过程中任何中间状态都不能是质数。算法返回转换的最小代价，代价是所有中间状态值的和。如果无法完成转换，返回 -1。

  1. 预处理质数

使用埃拉托色尼筛法生成一个布尔数组 zhishu，存储从 0 到 9999 的数是否为质数。

  1. 初始化与边界检查
  • 将 n 和 m 转换为字符串形式以确保操作时保留位数信息。
  • 检查起始值 n 或目标值 m 是否为质数，若是则立即返回 -1。
  • 初始化 dist 数组，用于记录到达某个状态的最小代价，初始时所有值为 LLONG_MAX，起点 n 的代价为其自身。
  • 使用优先队列 pq 实现 Dijkstra 算法，起点 (dist[in], in) 入队。
  1. Dijkstra 算法扩展节点

Dijkstra 算法的核心思想是：

  • 每次从优先队列中取出当前代价最小的状态 (cd, u)。
  • 对 u 的每一位尝试进行 +1 或 -1 操作，生成新的状态 v。
  • 若新状态满足以下条件：
    • 位数未发生变化（即保留原始长度 len）。
    • v 不是质数。
    • 更新 dist[v]，并将新状态 (nd, v) 入队。

扩展过程：

  • 对于每一位：
    • 如果位值不为 9，则尝试 +1 操作。
    • 如果位值不为 0，则尝试 -1 操作。
  • 通过条件检查确保新状态合法。
  1. 终止条件
  • 如果当前节点 u 等于目标值 m，返回当前累计代价 cd，即最小代价。
  • 如果优先队列为空且未能到达目标值，返回 -1。
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
typedef long long ll;

// 使用埃拉托色尼筛法生成质数表，返回一个布尔数组，标记从 0 到 maxVal 是否为质数
vector<bool> Findzhishu(ll maxVal){
    vector<bool> zhishu(maxVal+1, true);
    zhishu[0] = false; zhishu[1] = false; // 0 和 1 不是质数
    for(ll i = 2; i * i <= maxVal; i++){ // 遍历到 √maxVal
        if(zhishu[i]){
            for(ll j = i * i; j <= maxVal; j += i){ // 将 i 的倍数标记为非质数
                zhishu[j] = false;
            }
        }
    }
    return zhishu;
}

// 将数字 x 转换为固定长度的字符串，必要时在前面补零
string f(ll x, ll length){
    string s = to_string(x);
    while((ll)s.size() < length){ // 如果长度不足，则补零
        s = "0" + s;
    }
    return s;
}

class Solution {
public:
    ll minOperations(ll n, ll m){
        // 将输入的 n 和 m 转换为字符串，方便进行逐位操作
        string str_n = to_string(n), str_m = to_string(m);
        ll len = (ll)str_n.size(); // 确定数字长度（n 和 m 长度相同）

        // 生成质数表，范围是 0 到 9999
        vector<bool> iszhishu = Findzhishu(9999);

        // 将 str_n 和 str_m 转换为整数(不用m,n；为方便标识)
        ll in = stoi(str_n), im = stoi(str_m);

        // 如果初始值或目标值为质数，直接返回 -1
        if(iszhishu[im] || iszhishu[in]) return -1;

        // 初始化 dist 数组，存储从起点到各状态的最小代价
        const ll MAX = 10000;
        vector<ll> dist(MAX, LLONG_MAX); // 使用 LLONG_MAX 表示无穷大
        dist[in] = in; // 起点代价为起点自身的值

        // 使用优先队列实现 Dijkstra 算法
        priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<>> pq;
        pq.push({dist[in], in}); // 起点入队

        // Dijkstra 算法主循环
        while(!pq.empty()){
            auto [cd, u] = pq.top(); // 取出当前代价最小的状态
            pq.pop();

            // 如果当前代价大于记录的最小代价，跳过该状态
            if(cd > dist[u]) continue;

            // 如果已经到达目标值，返回最小代价
            if(u == im) return cd;

            // 将当前数字 u 转换为固定长度的字符串，方便逐位操作
            string su = f(u, len);

            // 遍历每一位，尝试进行 +1 或 -1 操作
            for(ll i = 0; i < len; i++){
                char c = su[i];
                // 尝试 +1 操作
                if(c != '9'){ // 如果当前位不是 9，可以加 1
                    string sv = su;
                    sv[i] = (char)(c + 1);
                    ll v = stoi(sv); // 转换回整数
                    // 检查新状态是否有效（长度不变，且不是质数）
                    if((ll)to_string(v).size() == len && !iszhishu[v]){
                        ll nd = cd + v; // 计算新代价
                        if(nd < dist[v]){ // 如果新代价更小，更新 dist 并入队
                            dist[v] = nd;
                            pq.push({nd, v});
                        }
                    }
                }
                // 尝试 -1 操作
                if(c != '0'){ // 如果当前位不是 0，可以减 1
                    string sv = su;
                    sv[i] = (char)(c - 1);
                    ll v = stoi(sv); // 转换回整数
                    // 检查新状态是否有效（长度不变，且不是质数）
                    if((ll)to_string(v).size() == len && !iszhishu[v]){
                        ll nd = cd + v; // 计算新代价
                        if(nd < dist[v]){ // 如果新代价更小，更新 dist 并入队
                            dist[v] = nd;
                            pq.push({nd, v});
                        }
                    }
                }
            }
        }
        // 如果无法到达目标值，返回 -1
        return -1;
    }
};

巧妙的Dijkstra算法转换——将数位看成固有模板中的节点

Q4.统计最小公倍数图中的连通块数目 —— 并查集、anchor策略

3378. 统计最小公倍数图中的连通块数目

给你一个长度为 n 的整数数组 nums 和一个 正 整数 threshold 。

有一张 n 个节点的图，其中第 i 个节点的值为 nums[i] 。如果两个节点对应的值满足 lcm(nums[i], nums[j]) <= threshold ，那么这两个节点在图中有一条 无向 边连接。

请你返回这张图中 连通块 的数目。

一个 连通块 指的是一张图中的一个子图，子图中任意两个节点都存在路径相连，且子图中没有任何一个节点与子图以外的任何节点有边相连。

lcm(a, b) 的意思是 a 和 b 的 最小公倍数 。

示例 1：

输入：nums = [2,4,8,3,9], threshold = 5

输出：4

解释：

img

四个连通块分别为 (2, 4) ，(3) ，(8) ，(9) 。

示例 2：

输入：nums = [2,4,8,3,9,12], threshold = 10

输出：2

解释：

img

两个连通块分别为 (2, 3, 4, 8, 9) 和 (12) 。

提示：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • nums 中所有元素互不相同。
  • 1 <= threshold <= 2 * 10^5

MyTrueSolv

算法总体思路：

  1. 将输入数组 nums 按照与 threshold 的大小关系进行分类：

    • large_vals: 所有大于 threshold 的元素，这些元素因为值过大无法与其他元素形成 LCM <= threshold 的边，因此各自独立组成一个连通块。
    • small_vals: 所有小于或等于 threshold 的元素，这部分元素之间可能存在连通关系。

  2. 若 small_vals 为空，则没有小值节点可连通，结果即为所有大值节点的数量。

  3. 对 small_vals 进行排序，并检查其中是否包含 1。

    • 若包含 1，则由于对任意 x ≤ threshold，LCM(1,x)=x ≤ threshold，因此 1 可将所有小值节点连成一个连通块。这时小值部分形成 1 个连通块，加上大值部分返回结果。

  4. 若 small_vals 中没有 1，则需要尝试通过公因子连接小值节点：

    • 使用 pos_of 数组快速从值映射到下标位置。
    • 利用并查集 (Union-Find) 维护小值节点的连接状态。
    • 核心做法：对于每个 d 从 1 到 threshold：
      • 找出所有是 d 倍数且出现在 small_vals 中的元素列表 idxs。
      • 若 idxs 中元素数量不少于 2，就尝试将它们连接起来。
      • 使用 “锚点(Anchor)” 策略：
        将 idxs[0] 的值作为初始锚点 anchor_val，
        依次遍历 idxs 后续元素 b，检查 LCM(anchor_val, b) 是否 ≤ threshold：
        • 若是，则说明 anchor_val 可将该元素也连进来（Union 操作）。
        • 若否，则无法通过当前锚点连接该元素，将该元素更新为新的 anchor_val，以尝试从新锚点出发连通后续元素。

    这样通过遍历所有因子 d，尝试用锚点策略建立尽可能多的连通关系，从而确保不会漏掉潜在的满足 LCM 条件的连接。

  5. 最终，小值节点在并查集内形成若干连通分量，加上大值节点独立分量的数量，得到最终答案。

带注释代码示例：

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct UF {
    vector<int> p;
    UF(int n): p(n) {
        for(int i=0;i<n;i++) p[i]=i;
    }
    // 并查集查找操作，带路径压缩
    int findp(int x) {
        return p[x]==x ? x : (p[x]=findp(p[x]));
    }
    // 并查集合并操作
    void uni(int a,int b) {
        a=findp(a); b=findp(b);
        if(a!=b) p[a]=b;
    }
};

class Solution {
public:
    int countComponents(vector<int>& nums,int threshold) {
        int n=(int)nums.size();
        vector<int> small_vals;
        vector<int> large_vals;

        // 将 nums 中元素分为大值(> threshold)和小值(≤ threshold)
        for(int i=0;i<n;i++){
            if(nums[i]>threshold) {
                // 大值节点各自独立
                large_vals.push_back(nums[i]);
            } else {
                // 小值节点可能互相连通
                small_vals.push_back(nums[i]);
            }
        }

        // 结果初始为大值节点数量（它们各自一个连通块）
        int res=(int)large_vals.size();

        // 若没有小值节点，直接返回大值块数
        if(small_vals.empty()){
            return res;
        }

        // 对小值排序，方便后续处理
        sort(small_vals.begin(),small_vals.end());

        // 检查是否有1存在
        bool has_1=(small_vals[0]==1);
        if(has_1){
            // 有1存在时，小值部分全部可与1连为一体
            res+=1;
            return res;
        }

        int maxVal=threshold;
        // pos_of[val] 用于快速查找值在 small_vals 中的下标
        vector<int> pos_of(maxVal+1,-1);
        for (int i=0;i<(int)small_vals.size();i++) {
            pos_of[small_vals[i]]=i;
        }

        // 使用并查集维护小值节点连通性
        UF uf((int)small_vals.size());

        // 对每个 d 从1到threshold
        // 收集 small_vals 中是 d 的倍数的元素
        // 再尝试用锚点策略将它们连通
        for (int d=1; d<=threshold; d++) {
            vector<int> idxs;
            // 枚举 d 的倍数 x
            for (int x=d; x<=threshold; x+=d) {
                if (pos_of[x]!=-1) {
                    idxs.push_back(x);
                }
            }

            // 若该因子 d 对应的小值元素不足2个，不需尝试连通
            if ((int)idxs.size()<2) continue;

            // 使用 anchor 策略
            int anchor_val = idxs[0];
            int anchor_idx = pos_of[anchor_val];
            for (int i=1;i<(int)idxs.size();i++){
                ll a=anchor_val,b=idxs[i];
                ll g=std::gcd(a,b);
                ll l=(a/g)*b; // lcm(a,b)
                if (l<=threshold) {
                    // 该元素 b 可通过 anchor_val 连入同一连通块
                    uf.uni(anchor_idx, pos_of[b]);
                } else {
                    // 无法用当前 anchor 连接 b
                    // 将 b 设为新的 anchor
                    anchor_val=b;
                    anchor_idx=pos_of[b];
                }
            }
        }

        // 统计并查集中小值部分的连通块数量
        unordered_set<int> leaders;
        for (int i=0;i<(int)small_vals.size();i++) {
            leaders.insert(uf.findp(i));
        }
        res+=(int)leaders.size();

        return res;
    }
};

总结：
算法将问题分解为对大值与小值的处理，对于小值利用因子倍数及锚点策略寻找满足 LCM 条件的连接边，从而将小值节点合并成若干连通分量。最后将小值和大值的连通分量数相加即得到结果。

解释 Anchor 策略：

在这道题中，我们需要对满足 LCM(nums[i], nums[j]) <= threshold 的节点对进行连通，而我们是通过遍历所有可能的公因子或因子分组来尝试连接节点的。在一个因子组内，我们会有多个节点，它们都具备某个共同因子。

所谓的 “anchor（锚点）策略” 是指在处理一组有序元素时，为了将尽可能多的元素连入同一连通组件，我们选择该组中当前最具有代表性的元素作为“锚点”（anchor），然后尝试用这个锚点去连接后续的元素。如果后续元素与锚点的 LCM 值在阈值以内，那么就将它合并到同一个连通块中；如果后续元素无法通过当前锚点连入（即 LCM 超过阈值），则将后续的这个元素改为新的锚点，并继续向后尝试连接。

在本题中的应用：

  1. 我们对 1..threshold 中的每个整数 d，找到 nums 中所有是 d 的倍数的元素，并将这些元素整理成一组。
  2. 将这组倍数元素按数值大小排序后，我们从第一个元素开始，将其作为锚点（anchor）。
  3. 依次遍历该组中剩下的元素，逐个判断它与锚点的 LCM 是否 ≤ threshold：
    • 若是，则说明该元素可被锚点带入同一个连通分量中，执行并查集 union 操作。
    • 若否，则当前锚点无法将这个元素连入，那么就将该元素更新为新的锚点，再继续检查后面元素。

通过这种策略，每一组以共享因子 d 划分出来的元素会尝试用尽可能少的“锚点变化”来构建连接。这样做的好处在于：

  • 如果一个较小的“锚点”元素能成功连接多个后续元素，这就可以最大程度地连通该因子组内的元素。
  • 当无法连接时，切换锚点保证我们不遗漏尝试通过其他可能的连接路径来连通后续元素。

简言之，”anchor 策略”在这道题中通过逐步更新代表元素（锚点），在不遗漏潜在连通性的情况下，尽可能高效且简化地尝试将因子组内的元素连成连通分量，从而达到正确构建连通图的目的。

OtherSolv

算法总体思路

  1. 分离问题：

    • 将小于等于 threshold 的元素按值构建分组关系，尝试通过因子关系连通这些节点。
    • 大于 threshold 的节点由于无法满足 LCM 条件，不会参与连通性判断，初始时每个节点为独立连通块。

  2. 并查集维护连通性：

    • 使用并查集来动态维护小值节点间的连通关系。
    • 每次发现两个节点可以连通时，将它们的父节点合并，同时连通块数量减 1。

  3. 因子分组与连通性检查：

    • 对于每个因子 g 从 1 到 threshold：
      • 找到当前因子组中最小的倍数 min_x，并将其作为起点。
      • 依次检查当前因子的其他倍数 y，若满足条件（即存在于 nums 中），尝试将其与起点 min_x 连通。
    • 每次成功连通两个节点时，连通块数量减 1。

  4. 结果返回：

    • 初始连通块数等于 nums.size()，每次连通两个节点减少 1，最终返回剩余的连通块数。
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
class Solution {
public:
    int countComponents(vector<int>& nums, int threshold) {
        int n = nums.size();
        vector<int> fa(n);
        // 初始化并查集，每个节点初始时是自己的父节点
        iota(fa.begin(), fa.end(), 0);

        // 非递归实现的并查集查找操作（路径压缩）
        auto find = [&](int x) -> int {
            int rt = x;
            // 找到根节点
            while (fa[rt] != rt) {
                rt = fa[rt];
            }
            // 路径压缩：将沿途的节点直接连接到根节点
            while (fa[x] != rt) {
                int tmp = fa[x];
                fa[x] = rt;
                x = tmp;
            }
            return rt;
        };

        // 记录每个数值对应的下标（仅限 <= threshold 的数值）
        vector<int> idx(threshold + 1, -1);
        for (int i = 0; i < n; i++) {
            if (nums[i] <= threshold) {
                idx[nums[i]] = i; // idx[x] 表示值为 x 的节点在 nums 中的下标
            }
        }

        // 遍历因子 g，从 1 到 threshold
        for (int g = 1; g <= threshold; g++) {
            int min_x = -1;
            // 找到当前因子 g 的最小倍数 min_x（存在于 nums 中）
            for (int x = g; x <= threshold; x += g) {
                if (idx[x] >= 0) { // 只处理在 nums 中的数值
                    min_x = x;
                    break;
                }
            }
            // 如果当前因子的倍数组中没有任何有效的数，跳过
            if (min_x < 0) {
                continue;
            }

            // 找到 min_x 所在连通块的根节点
            int fi = find(idx[min_x]);
            // 计算当前因子 g 的最大有效倍数上界
            int upper = (long long) g * threshold / min_x;

            // 遍历 g 的其他倍数 y，尝试与 min_x 连通
            for (int y = min_x + g; y <= upper; y += g) {
                if (idx[y] >= 0) {
                    // 找到 y 的根节点
                    int fj = find(idx[y]);
                    // 如果 min_x 和 y 不在同一个连通块中，则合并它们
                    if (fj != fi) {
                        fa[fj] = fi; // 合并操作
                        n--; // 连通块数减少
                    }
                }
            }
        }
        // 返回剩余的连通块数量
        return n;
    }
};

代码关键点分析

  1. 并查集路径压缩的实现：

    • find 函数中，通过两次循环实现了路径压缩：
      • 第一个循环用于找到根节点。
      • 第二个循环将沿途的所有节点直接挂载到根节点，从而加速后续的查找操作。
    • 这种非递归方式的路径压缩在实际应用中效率高且易于理解。

  2. 因子分组：

    • 每次遍历因子 g，通过枚举其倍数找到所有与该因子相关的值。因子倍数 g*k 确保了同一因子组的连通性。

  3. 跳过冗余计算：

    • 使用 min_x 作为起点，避免了重复检查相同因子的其他倍数组。
    • upper 上界优化了对可能倍数的遍历范围，减少了不必要的计算。

  4. 连通块合并逻辑：

    • 每次合并两个节点时直接更新父节点，并将总连通块数量减 1。

与其他算法的比较

  1. 简洁性：

    • 该算法简化了因子分组逻辑，直接从因子 g 入手，不涉及复杂的质因数分解或倍数分组的额外步骤。

  2. 效率：

    • 通过记录有效值的下标以及跳过无关值，优化了因子遍历的时间复杂度。
    • 路径压缩的并查集进一步加速了连通性检查和更新。

  3. 鲁棒性：

    • 因为跳过了不在 nums 中的倍数，该算法能有效避免冗余计算，适用于各种 threshold 和 nums 的大小组合。

总结
该算法的核心是利用并查集来维护连通性，通过因子 g 遍历和倍数查找构建连通关系，同时通过路径压缩和上界优化减少冗余操作。代码简洁，逻辑清晰，是一种非常高效且易于实现的解决方案。

第427场周赛