Leetcode 周赛复盘
第426场周赛
100501. 仅含置位位的最小整数
Easy. 只需要不断将1向左移,直到大于该数即可,返回此时的数-1。
class Solution {
public:
int smallestNumber(int n) {
int i=1;
while(i <= n)
i <<= 1;
return i-1;
}
};
100444. 识别数组中的最大异常值
Medium.
不要慌,首先思考一下,寻找到异常值后,会出现剩下的元素之和等于其中一个元素。这样我们的和肯定是偶数。那么,只需要在累加的时候统计一下数字出现的情况,然后:
- 判断和是否为偶数。
- 一个个挑选出异常值,然后判断和的一半是否存在。存在的情况包括:(1)和的一半与异常值相同且异常值出现了不止一次。(2)和的一半与异常值不同且出现了一次。
- 直到最后找到最大的异常值即可。
class Solution {
public:
int getLargestOutlier(vector<int>& nums) {
int sum = 0;
vector<int> cal(2005,0);
for(auto i:nums)
{
cal[i+1000] ++;
sum += i;
}
int ans = -2005;
for(auto i:nums)
{
sum -= i;
if(sum % 2 != 0)
{
sum+=i;
continue;
}
int temp = sum / 2;
if(temp+1000 >= 0 && temp+1000 <= 2000 && cal[temp+1000])
{
if(temp == i && cal[temp+1000] > 1 || temp != i)
ans = (ans > i) ? ans : i;
}
sum += i;
}
return ans;
}
};
100475. 连接两棵树后最大目标节点数目
首先很明显,要加边的端点在第一棵树上必然是端点i。
接下来需要考虑第二棵树上应该添加到哪个节点。暴力枚举第二个节点。DFS计算距离\(j\)不超过\(k-1\)的节点个数\(cnt_j\)。要注意新添加的边,所以是\(k-1\)。\(cnt_j\)取得最大值,记为\(max_2\)。新添加的边连接到其对应的节点上。
暴力枚举第一棵树节点i,DFS计算距离i不超过k的节点个数。则有\(cnt_i+cnt_j\)为答案。
class Solution {
public:
vector<vector<int> > buildGraph(vector<vector<int> > & edges)
{
// 建立无向图邻接链表。
vector<vector<int> > g(edges.size() + 1); // 边数
for (auto &e: edges)
{
int v1 = e[0];
int v2 = e[1];
g[v1].push_back(v2);
g[v2].push_back(v1);
}
return g;
}
int dfs(int cur, int pa, int dist, vector<vector<int> >&g, int k)
{
// dfs 终点。
if(dist > k)
return 0;
// 计数:当前状态为1.
int cnt = 1;
for(int next:g[cur])
{
// 无向图:下一个节点和上一个节点不形成环。递归累加。
if(next != pa)
cnt += dfs(next, cur, dist+1, g, k);
}
return cnt;
}
vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2, int k) {
int max2 = 0;
if(k > 0)
{
vector<vector<int> > graph2 = buildGraph(edges2);
for(int i = 0; i < edges2.size()+1; i++)
max2 = max(max2, dfs(i, -1, 0, graph2, k-1));
}
vector<vector<int> > graph1 = buildGraph(edges1);
vector<int> ans(edges1.size() + 1);
for(int i = 0; i < ans.size(); i++)
ans[i] = dfs(i,-1,0,graph1,k) + max2;
return ans;
}
};
标签:周赛,cnt,int,sum,vector,ans,节点
From: https://www.cnblogs.com/mumujun12345/p/18581046