今天试了往期两次周赛，一次独立做出两题，一次独立做出三题，加油！
1. 合并相似的物品
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
很方便地用map统计即可。
代码
class Solution {
public:
static bool cmp(vector<int>& a, vector<int>& b) {
if (a[0] == b[0]) return a[1] < b[1];
else return a[0] < b[0];
}
vector<vector<int>> mergeSimilarItems(vector<vector<int>>& items1, vector<vector<int>>& items2) {
vector<vector<int>> ans;
map<int,int> mp;
for (auto& item1 : items1) mp[item1[0]] += item1[1];
for (auto& item2 : items2) mp[item2[0]] += item2[1];
for (auto& elem : mp) ans.push_back({elem.first, elem.second});
// sort(ans.begin(), ans.end(), cmp);
return ans;
}
};2. 统计坏数对的数目
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
想到了先求好数对的数目再减掉，但没想到移项的方法。解题时不能忘了数学的方法，多尝试操作式子。
代码
class Solution {
public:
long long countBadPairs(vector<int>& nums) {
long long n = nums.size();
for (int i = 0; i < n; ++i) {
nums[i] = nums[i] - i;
}
map<int,long long> mp;
for (auto& num : nums) mp[num]++;
long long ans = (n * (n - 1))/2;
for (auto& elem : mp) if (elem.second > 1) ans -= (elem.second - 1)*elem.second/2;
return ans;
}
};3. 任务调度器 II
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
遍历一遍数组即可。用一个map记录每个任务上次出现位置，初始为0。记录ans为当前所在天数，初始为1。如果当前天数大于当前任务上次出现位置+space，则可以做任务，更新任务出现位置，++天数；否则直接将ans更新到人物上次出现位置+space+1即可，而不用慢慢++。
代码
class Solution {
public:
long long taskSchedulerII(vector<int>& tasks, int space) {
long long ans = 1;
int n = tasks.size();
int i = 0;
map<long, long> last;
while (i < n) {
if (last[tasks[i]] == 0 || ans > last[tasks[i]] + space) {
last[tasks[i]] = ans;
++i;
++ans;
} else ans = last[tasks[i]] + space + 1;
}
return ans - 1;
}
};4. 将数组排序的最少替换次数
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
我的思路是从前向后遍历，区间最小值作为其左侧元素的分割标准，逐渐缩小区间，递归计算。但题解逆向思维，从后向前遍历，能够用一次遍历确定下一元素的分割情况，从而计算总操作数。
解题不能太直，正着比较复杂的时候，不妨反着来看看。
代码
class Solution {
public:
long long minimumReplacement(vector<int>& nums) {
int n = nums.size();
long long ans = 0LL;
int m = nums[n - 1];
for (int i = n - 2; i >= 0; --i) {
int k = (nums[i] - 1) / m;
ans += k;
m = nums[i] / (k + 1);
}
return ans;
}
};5.
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
多举几个例子，不难发现，所有元素归零需要的步数，等于数组中非零元素的种类，所以统计这个数字即可。
代码
class Solution {
public:
int minimumOperations(vector<int>& nums) {
map<int, int> mp;
for (auto& num : nums) if (num) mp[num] = 1;
return mp.size();
}
};6. 分组的最大数量
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
一开始以为自己思路不靠谱，结果真过了。
我的想法是，如果要符合要求分组，那么将数组排列，第一组分一个，第二组分两个，以此类推，且每个人成绩按次序非减，最后一组人不够的时候塞到前一个组即可，这样出来的分组一定满足要求，且组数也最大。而现在只要这个组数，所以我们不关心元素次序，只要根据元素数量来计算分组数即可。显然，根据等差数列的计算公式，确定分组数x之后，总的人数的区间是确定的，于是，我们可以使用二分法，查找总人数所处区间对应的分组数x。显然x的下界是1，而总人数最大为10的5次方，则分组数上界可以设为500。接下来，只要二分查找1-500这个区间即可，当某个x计算得到的上下界能满足总人数时，就返回这个x（mid）。
代码
class Solution {
public:
int maximumGroups(vector<int>& grades) {
int n = grades.size(); //总人数
int low = 1, high = 500;
int mid = 0;
// 二分查找分组数
while (low <= high) {
mid = low + (high - low) / 2;
if (n < (1 + mid) * mid / 2) high = mid - 1;
else if (n > (mid + 1) * (mid + 2) / 2 - 1) low = mid + 1;
else break;
}
return mid;
}
};7. 找到离给定两个节点最近的节点
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
首先构造两个结点的直线路径，这需要用到两个数组和两个map（防止成环）。
然后根据两个结点的路径，分别给每个结点打上时间戳（或者说步数），不可达结点标记为-1。
遍历每个结点，当结点上两个node的时间戳均不为-1，则说明两者都可达，取两者到这个点的最大步数，以及当前结点编号，记录并取得编号最小的最小最大步数的结点即可。
看了dalao的题解，基本思路一样，但在求路径长这个问题上，dalao用了更高级简便的做法，因此效率更高。
代码
class Solution {
public:
int closestMeetingNode(vector<int>& edges, int node1, int node2) {
int n = edges.size();
vector<int> seq1;
map<int,int> nodes1;
int cur = node1;
while (true) {
if (nodes1[cur] !=0 ) break;
else {
nodes1[cur] = 1;
seq1.push_back(cur);
}
if (edges[cur] == -1) break;
else cur = edges[cur];
}
vector<int> seq2;
map<int,int> nodes2;
cur = node2;
while (true) {
if (nodes2[cur] !=0 ) break;
else {
nodes2[cur] = 1;
seq2.push_back(cur);
}
if (edges[cur] == -1) break;
else cur = edges[cur];
}
int ans = INT_MAX;
int len = INT_MAX;
int a = seq1.size(), b = seq2.size();
vector<int> node1Time(n, -1);
for (int i = 0; i < a; ++i) {
node1Time[seq1[i]] = i;
}
vector<int> node2Time(n, -1);
for (int i = 0; i < b; ++i) {
node2Time[seq2[i]] = i;
}
for (int i = 0; i < n; ++i) {
if (node1Time[i] != -1 && node2Time[i] != -1) {
if (max(node1Time[i], node2Time[i]) < len) {
len = max(node1Time[i], node2Time[i]);
ans = i;
} else if (max(node1Time[i], node2Time[i]) == len) {
ans = min(ans, i);
}
}
}
return ans == INT_MAX ? -1 : ans;
}
};8. 图中的最长环
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
使用一个全局时间戳，记录首次达到一个结点的时间。每次以一个新到达的结点为首，记录当前时间为start，去遍历他的路径。如果在遍历过程中碰到了访问过，且时间戳大于start的结点，说明这是一个环，其长度为当前时间减掉上次访问时间。在这个过程中，路径上任意结点组成的环必定被发现，换句话说，这个过程中没发现环，那么下次再遇到这个路径中的结点，就不用再遍历其路径了。也就是，每次遍历完一个连通子图。
代码
class Solution {
public:
int longestCycle(vector<int>& edges) {
int ans = -1;
int n = edges.size();
vector<int> time(n, 0);
for (int i = 0, clock = 1; i < n; ++i) {
if (time[i]) continue;
for (int x = i, startTime = clock; x >= 0; x = edges[x]) {
if (time[x]) {
if (time[x] >= startTime) {
ans = max(ans, clock - time[x]);
}
break;
}
time[x] = clock++;
}
}
return ans;
}
};
Comments NOTHING