当前位置：首页 > news >正文

第426场周赛：仅含置位位的最小整数、识别数组中的最大异常值、连接两棵树后最大目标节点数目 Ⅰ、连接两棵树后最大目标节点数目 Ⅱ

news 来源：原创 2025/6/26 23:41:41

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

1、题目描述

给你一个正整数 n。

返回大于等于 n 且二进制表示仅包含置位位的最小整数 x 。

置位位指的是二进制表示中值为 1 的位。

2、解题思路

我们需要找到一个整数 x，使得：

x ≥ n
x 的二进制表示中仅包含置位位，并且 x 是比 n 大于或等于的最小整数。

解法

通过不断构造形如 111...111 的数并判断是否大于等于 n：

初始化一个结果变量 ret，初始值为 1（二进制为 1）。
如果当前 ret 小于 n，则将其左移一位后，最低位补 1。这相当于在二进制末尾追加一个 1，使其逐渐变成 11、111 等。
当 ret 大于等于 n 时，停止循环并返回 ret。

3、代码实现

class Solution {
public:int smallestNumber(int n) {int ret = 1; // 初始结果while (ret < n) {ret = (ret << 1) | 1; // 左移一位后补 1}return ret;}
};

4、复杂度分析

时间复杂度：O(1)。该算法通过一系列固定次数的位操作计算最小整数，无论 n 的大小如何，位运算的次数是固定的。
空间复杂度：O(1)。算法只使用常数空间。

Q2、识别数组中的最大异常值

1、题目描述

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

异常值的定义是：既不是原始特殊数字之一，也不是表示这些数字元素和的数字。

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

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

2、解题思路

要解这个问题，我们可以按照以下步骤进行：

首先理解数组的结构：
- 数组中有 n-2 个特殊数字，这些数字的和是 sum。
- 剩下的两个数字中一个是 sum，另一个是 abnormal。
- 我们需要确定这两个数字分别是什么，并且找出最大的异常值。
步骤：
- 计算数组中所有元素的总和 totalSum。
- 对于每个元素，假设它是 abnormal，并计算其他元素的和（即 totalSum - abnormal）。
- 检查这个和是否可以分解成一个 sum 和 n-3 个特殊数字的和。
- 如果可以，则返回这个 abnormal 数字。
分析：
- 我们可以通过检查每个元素是否是可能的 abnormal 来找到解。
- 通过每次尝试去找 abnormal 和其对应的 sum。

解法

我们先来尝试通过遍历数组来实现这个思路。具体实现时，我们首先计算总和，然后假设某个元素是异常值，计算剩余部分的和来判断它是否是有效的特殊数字之和。

避免重复查找：可以通过将数组元素存储在哈希集合中，这样查找 half 是否存在可以在常数时间 O(1) 内完成。
改进的步骤：
- 计算整个数组的总和 totalSum。
- 对于每个元素，假设它是异常值 abnormal，计算 sum = totalSum - abnormal。
- 如果 sum 是偶数，可以继续判断其一半 half = sum / 2 是否是数组中的其他元素。为了更高效地查找，我们将 nums 中的元素存入哈希表 unordered_map。

3、代码实现

class Solution {
public:int getLargestOutlier(vector<int>& nums) {int n = nums.size();int totalSum = 0;// 用来存储最大的异常值int maxAbnormal = INT_MIN;// 使用哈希集合存储数组中的元素, 快速查找unordered_map<int, vector<int>> hash;for (int i = 0; i < n; ++i) {hash[nums[i]].push_back(i);totalSum += nums[i];}// 遍历数组中的每一个元素，假设它是异常值for (int i = 0; i < n; ++i) {int abnormal = nums[i];int sum = totalSum - abnormal; // 假设剩余的和是 sumif (sum % 2) {continue;}int half = sum / 2;// 判断 sum 是否可以通过删除一个特殊值来得到// sum 应该是 nums 中的一个元素，并且这个元素的下标不是 ibool valid = false;if (hash.count(half)) {auto v = hash[half];for (const auto& index : v) {if (index != i) {valid = true;break;}}}// 如果找到了合法的 sum，更新最大异常值if (valid) {maxAbnormal = max(maxAbnormal, abnormal);}}return maxAbnormal == INT_MIN ? -1 : maxAbnormal; // 如果没有找到异常值，则返回 -1}
};

4、时间复杂度分析

时间复杂度：
- 构建哈希集合 unordered_map 的时间复杂度是 O(n)。
- 遍历数组，针对每个元素计算 sum 和 half，并通过哈希集合判断 half 是否存在，时间复杂度是 O(1)。因此，整个遍历过程的时间复杂度是 O(n)。
- 总体时间复杂度是 O(n)。
空间复杂度：我们使用了一个额外的哈希集合 unordered_map 来存储数组元素，因此空间复杂度是 O(n)。

Q3、连接两棵树后最大目标节点数目 Ⅰ

1、题目描述

有两棵无向树，分别有 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 的目标节点数目的最大值。

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

2、解题思路

树的表示与遍历：
- 我们需要计算每个节点到其他节点的路径长度。对于树来说，路径长度等于两个节点之间的跳跃边数。
- 我们可以使用**深度优先搜索（DFS）或者广度优先搜索（BFS）**来计算从某一节点到其他节点的路径长度。
距离矩阵的构建：
- 为了快速计算两个节点之间的距离，可以利用 BFS 在每棵树上预处理节点之间的最短路径。具体来说，使用 BFS 可以得到从某个节点到所有其他节点的距离。
处理每个查询：
- 对于每个节点 i，我们需要找出在第二棵树上与 i 连接的节点，使得路径的边数小于等于 k，并且尽可能多。
- 因为每个查询之后边会被删除，因此每个查询的结果是独立的。
最大目标节点的数目：
- 我们需要遍历树2中的每个节点，计算在第一棵树中的每个节点与该节点的连接，满足条件的目标节点的最大数目。

解决步骤

预处理树1和树2的每个节点到其他节点的最短距离，可以通过 BFS 来实现。
处理每个查询，对于每个查询，检查连接第一棵树的节点到第二棵树的每个节点的路径，计算最大目标节点数。

3、代码实现

class Solution {
public:vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2, int k) {int n = edges1.size() + 1; // 第一棵树的节点数int m = edges2.size() + 1; // 第二棵树的节点数// 构建树1和树2的邻接表vector<vector<int>> adj1(n), adj2(m);for (auto& edge : edges1) {adj1[edge[0]].push_back(edge[1]);adj1[edge[1]].push_back(edge[0]);}for (auto& edge : edges2) {adj2[edge[0]].push_back(edge[1]);adj2[edge[1]].push_back(edge[0]);}// 计算每个节点到其他节点的最短距离vector<vector<int>> dist1(n), dist2(m);for (int i = 0; i < n; i++) {dist1[i] = bfs(i, adj1, n);}for (int i = 0; i < m; i++) {dist2[i] = bfs(i, adj2, m);}// 对每个节点 i 计算最大目标节点数vector<int> result(n, 0);// 预计算树2每个节点的目标节点数vector<int> targetCount2(m, 0);for (int j = 0; j < m; ++j) {int count2 = 0;for (int x = 0; x < m; ++x) {if (dist2[j][x] < k) {count2++;}}targetCount2[j] = count2;}// 对树1的每个节点，计算其最大目标节点数for (int i = 0; i < n; i++) {int targetCount1 = 0;int maxTargets = 0;// 对于树 1 的目标节点个数for (int j = 0; j < n; ++j) {if (dist1[i][j] <= k) {++targetCount1;}}// 对每个树2中的节点 j, 检查目标节点数for (int j = 0; j < m; j++) {// 计算树 1 的节点 i 到树 2 的节点 j 的路径是否符合要求int count = targetCount1 + targetCount2[j];maxTargets = max(maxTargets, count);}result[i] = maxTargets;}return result;}// BFS 计算从一个节点到其他节点的最短路径vector<int> bfs(int start, const vector<vector<int>>& adj, int n) {vector<int> dist(n, -1); // -1表示未访问queue<int> q;dist[start] = 0;q.push(start);while (!q.empty()) {int node = q.front();q.pop();for (int neighbor : adj[node]) {if (dist[neighbor] == -1) { // 如果未访问过dist[neighbor] = dist[node] + 1;q.push(neighbor);}}}return dist;}
};

BFS计算最短距离：bfs 函数用于计算从某个节点出发，所有其他节点的最短路径。
构建邻接表：首先我们将每棵树的边表示为邻接表 adj1 和 adj2，分别对应第一棵和第二棵树。
计算每个节点的最短路径：通过 bfs 从每个节点出发，计算到其他所有节点的最短距离，并存储在 dist1 和 dist2 中。
遍历计算最大目标节点数：对于每个节点 i，我们遍历第二棵树的所有节点，计算其目标节点的数量。

Q4、连接两棵树后最大目标节点数目 Ⅱ

1、题目描述

有两棵无向树，分别有 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 的 目标节点 数目的 最大值 。

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

2、解题思路

节点目标的定义：

目标节点的定义是：如果节点 u 和节点 v 之间的路径的边数是偶数，那么 u 是 v 的目标节点。
每个节点一定是它自己的目标节点。

树的层次分组：

由于目标节点数目与路径的边数是否为偶数相关，我们可以将树的节点按层次分组。即，我们可以利用 深度优先搜索（DFS）对每棵树进行层次划分。
在每棵树中，通过 DFS 遍历节点，并将节点根据奇偶层分到两个组中。对于树1，按奇偶层分组后的节点数目可以用来计算目标节点数。

最大目标节点数：

对于第一棵树中的每个节点 i，我们要计算该节点通过与第二棵树中节点连接后，能得到的最大目标节点数。
由于目标节点的定义是与路径的奇偶性相关，因此树2中的每层节点数可以影响树1中每个节点的目标节点数。

优化：

通过 DFS 预处理每棵树的节点层次信息，然后利用这些信息计算每个节点的目标节点数。这样可以避免每次连接时重新计算所有节点之间的路径关系，显著提高效率。

3、代码实现

class Solution {
private:// 构建邻接表void buildGraph(vector<vector<int>>& graph, const vector<vector<int>>& edges) {for (const auto& edge : edges) {int u = edge[0], v = edge[1];graph[u].push_back(v);graph[v].push_back(u);}}// 更新树 1 中每个节点的目标节点数void updateTargetNodes(vector<int>& result, const vector<vector<int>>& layers1) {for (const auto& layer : layers1) {int layerSize = layer.size();for (int node : layer) {result[node] += layerSize; // 增加该层节点数}}}// 深度优先搜索函数, 按奇偶层分组void dfs(int node, int parent, int layer, vector<vector<int>>& graph, vector<vector<int>>& layers) {// 将当前节点加入对应层的分组layers[layer].push_back(node);// 遍历相邻节点, 递归调用 DFSfor (int neighbor : graph[node]) {// 跳过父节点if (neighbor == parent) {continue;}// 切换层次 (奇偶层)dfs(neighbor, node, 1 - layer, graph, layers);}}public:vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2) {int n = edges1.size() + 1; // 第一个树的节点数int m = edges2.size() + 1; // 第二个树的节点数// 构建邻接表，表示两棵树vector<vector<int>> graph1(n), graph2(m);buildGraph(graph1, edges1);buildGraph(graph2, edges2);// 存储每个树按层分组的节点vector<vector<int>> layers1(2), layers2(2);// 进行 DFS 遍历，分层存储节点dfs(0, -1, 0, graph1, layers1);dfs(0, -1, 0, graph2, layers2);// 找到树2中节点数量最多的层int maxLayerSizeInTree2 = max(layers2[0].size(), layers2[1].size());// 初始化答案数组，每个节点的目标节点数默认为树2最大层的节点数vector<int> result(n, maxLayerSizeInTree2);// 对树1中的每个节点，增加与该层节点数相等的目标节点数updateTargetNodes(result, layers1);return result;}
};

代码讲解

构建图：
- buildGraph 函数通过给定的边列表（edges1 和 edges2）构建图的邻接表。
DFS 遍历：
- dfs 函数用于对树进行深度优先搜索，并按层将节点分到两个层（奇层和偶层）。我们通过层次分组来记录树中每个节点的奇偶层信息。
计算最大目标节点数：
- updateTargetNodes 函数通过遍历树1的奇偶层，更新每个节点的目标节点数。目标节点数的增加量就是该层的节点数。
最终答案：
- 对于树1中的每个节点，初始时其目标节点数设置为树2中最大的层数（即maxLayerSizeInTree2），然后再根据树1中该节点所处的层次进行更新。

4、时间复杂度

构建图的时间复杂度为 O(n + m)，因为我们需要处理每一条边。
DFS 遍历的时间复杂度为 O(n + m)，每个节点和边都只访问一次。
计算每个节点的目标节点数的时间复杂度为 O(n)，其中我们遍历树1的节点和层。

因此，总时间复杂度为 O(n + m)

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

1、题目描述

2、解题思路

3、代码实现

4、复杂度分析

Q2、识别数组中的最大异常值

1、题目描述

2、解题思路

3、代码实现

4、时间复杂度分析

Q3、连接两棵树后最大目标节点数目 Ⅰ

1、题目描述

2、解题思路

3、代码实现

Q4、连接两棵树后最大目标节点数目 Ⅱ

1、题目描述

2、解题思路

3、代码实现

4、时间复杂度

相关文章：