您现在的位置是:首页 >其他 >LeetCode周赛复盘(第344场周赛)网站首页其他
LeetCode周赛复盘(第344场周赛)
文章目录
1、找出不同元素数目差数组
1.1 题目链接
1.2 题目描述
给你一个下标从 0 开始的数组 nums ,数组长度为 n 。
nums 的 不同元素数目差 数组可以用一个长度为 n 的数组 diff 表示,其中 diff[i] 等于前缀 nums[0, …, i] 中不同元素的数目 减去 后缀 nums[i + 1, …, n - 1] 中不同元素的数目。
返回 nums 的 不同元素数目差 数组。
注意 nums[i, …, j] 表示 nums 的一个从下标 i 开始到下标 j 结束的子数组(包含下标 i 和 j 对应元素)。特别需要说明的是,如果 i > j ,则 nums[i, …, j] 表示一个空子数组。
1.3 解题代码
class Solution {
public:
unordered_map<int, int> hash1;
unordered_map<int, int> hash2;
vector<int> distinctDifferenceArray(vector<int>& nums) {
int n = nums.size();
int perifix_sum[n+5];
int suffix_sum[n+5];
vector<int> res;
memset(perifix_sum, 0, sizeof(perifix_sum));
memset(suffix_sum, 0, sizeof(suffix_sum));
for(int i = 0; i < n; ++i){
if(i == 0){
perifix_sum[i] = 1;
} else{
if(hash1[nums[i]] == 0){
perifix_sum[i] = perifix_sum[i-1] + 1;
} else{
perifix_sum[i] = perifix_sum[i-1];
}
}
hash1[nums[i]]++;
}
for(int i = n-1; i >= 0; --i){
if(i == n-1){
suffix_sum[i] = 0;
} else{
if(hash2[nums[i+1]] == 0){
suffix_sum[i] = suffix_sum[i+1] + 1;
} else{
suffix_sum[i] = suffix_sum[i+1];
}
hash2[nums[i+1]]++;
}
}
for(int i = 0; i < n; ++i){
res.push_back(perifix_sum[i] - suffix_sum[i]);
}
return res;
}
};
1.4 解题思路
(1) 题目说明了要求出的是该字母(包含)前面的不同字母数减去该字母(不包含)后面的不同字母数。所以想到了利用类前后缀和(动态规划)来解决问题。
(2) 求类前后缀和的时候,用哈希表进行辅助,帮忙判断是否出现相同单词。
(3) 最后按照题目要求,对应位置相减求出每一个位置的答案。
2、频率跟踪器
2.1 题目链接
2.2 题目描述
请你设计并实现一个能够对其中的值进行跟踪的数据结构,并支持对频率相关查询进行应答。
实现 FrequencyTracker 类:
FrequencyTracker():使用一个空数组初始化 FrequencyTracker 对象。
void add(int number):添加一个 number 到数据结构中。
void deleteOne(int number):从数据结构中删除一个 number 。数据结构 可能不包含 number ,在这种情况下不删除任何内容。
bool hasFrequency(int frequency): 如果数据结构中存在出现 frequency 次的数字,则返回 true,否则返回 false。
2.3 解题代码
class FrequencyTracker {
public:
unordered_map<int, int> hash;
unordered_map<int, int> freq;
FrequencyTracker() {
hash.clear();
}
void add(int number) {
if(hash[number] != 0){
freq[hash[number]]--;
}
hash[number]++;
freq[hash[number]]++;
}
void deleteOne(int number) {
if(hash[number] > 0){
freq[hash[number]]--;
hash[number]--;
freq[hash[number]]++;
}
}
bool hasFrequency(int frequency) {
if(freq[frequency] != 0){
return true;
}
return false;
}
};
/**
* Your FrequencyTracker object will be instantiated and called as such:
* FrequencyTracker* obj = new FrequencyTracker();
* obj->add(number);
* obj->deleteOne(number);
* bool param_3 = obj->hasFrequency(frequency);
*/
2.4 解题思路
(1) 数据结构部分,我们考虑用两个哈希表来辅助记录,hash用来记录某个数字出现的数目。freq用来记录出现的次数数目是否存在。
(2) 每当加入一个数字,hash表自增,如果hash表中原来该数字出现的数目num不为0,则freq中num数目-1,num+1数目+1。如果为0的话,则只有num+1数目+1。
(3) 每当删除一个数字,先判断是否该数字存在,不存在则不变化,如果存在,记录该数字出现的数目为num。如果num == 1的话,freq中的num数目-1,如果num > 1的话,freq中的num数目-1,num-1数目+1。
(4) 判断是否出现x次的元素只需要判断freq中对应的x是否为0,为0则为false,否则为true。
3、6418. 有相同颜色的相邻元素数目
3.1 题目链接
3.2 题目描述
给你一个下标从 0 开始、长度为 n 的数组 nums 。一开始,所有元素都是 未染色 (值为 0 )的。
给你一个二维整数数组 queries ,其中 queries[i] = [indexi, colori] 。
对于每个操作,你需要将数组 nums 中下标为 indexi 的格子染色为 colori 。
请你返回一个长度与 queries 相等的数组 answer ,其中 answer[i]是前 i 个操作 之后 ,相邻元素颜色相同的数目。
更正式的,answer[i] 是执行完前 i 个操作后,0 <= j < n - 1 的下标 j 中,满足 nums[j] == nums[j + 1] 且 nums[j] != 0 的数目。
3.3 解题代码
class Solution {
public:
vector<int> colorTheArray(int n, vector<vector<int>>& queries) {
int m = queries.size();
vector<int> answer;
int index[n+1];
int mark[n+1];
memset(mark, 0, sizeof(mark));
memset(index, 0, sizeof(index));
if(n == 1){
for(int i = 0; i < m; ++i){
answer.push_back(0);
}
return answer;
}
for(int i = 0; i < m; ++i){
int idx = queries[i][0];
int colour = queries[i][1];
if(index[idx] == colour){
if(i == 0){
answer.push_back(0);
} else{
answer.push_back(answer[i-1]);
}
continue;
}
index[idx] = colour;
if(i == 0){
answer.push_back(0);
continue;
}
int num = 0;
if(idx == 0){
if(index[0] == index[1]){
mark[1] = 1;
num++;
} else{
if(mark[1] == 1){
mark[1] = 0;
num--;
}
}
answer.push_back(answer[i-1] + num);
} else if(idx == n-1){
if(index[idx] == index[idx-1]){
mark[idx] = 1;
num++;
} else{
if(mark[idx] == 1){
mark[idx] = 0;
num--;
}
}
answer.push_back(answer[i-1] + num);
} else{
if(index[idx] == index[idx-1]){
mark[idx] = 1;
num++;
} else{
if(mark[idx] == 1){
mark[idx] = 0;
num--;
}
}
if(index[idx] == index[idx+1]){
mark[idx+1] = 1;
num++;
} else{
if(mark[idx+1] == 1){
mark[idx+1] = 0;
num--;
}
}
answer.push_back(answer[i-1] + num);
}
}
return answer;
}
};
3.4 解题思路
(1) 如果n == 1的话,则无论怎么变,答案都为0.
(2) 接下来讨论其他情况。用index来记录变色情况,用mark来表示原来的状态。mark[i] == 1表示index[i] 和 index[i-1]相同,mark[I] == 0 表示不相同。
(3) 下面遍历查询数组,用idx 表示 queries[i][0], 意思为位置,用colour表示queries[i][1],意思为涂的颜色。如果涂的颜色和之前的没变化,则需要判断是第几次涂色,是第一次涂色,直接答案为0,否则的话和前一次答案一样。如果涂的颜色和之前的有变化,如果是第0次涂色,则答案为0,否则的话则需要判断。
(4) 如果idx == 0或者idx == n-1,只需要判断idx == 1或者idx == n-2 的位置是否与0 或者 n - 1相同,相同的话更新mark,答案在原来的基础上+1,不相同根据mark判断是否减少了答案,不要忘记更新mark哟。如果idx > 0 并且 idx < n-1 ,此时则需要判断修改后 idx 与 idx-1的位置相不相同, idx 与idx + 1的位置相不相同,按照与0和n-1位置一样的方式更新mark和答案。
(5) 最后返回answer数组即可。
4、使二叉树所有路径值相等的最小代价
4.1 题目链接
4.2 题目描述
给你一个整数 n 表示一棵 满二叉树 里面节点的数目,节点编号从 1 到 n 。根节点编号为 1 ,树中每个非叶子节点 i 都有两个孩子,分别是左孩子 2 * i 和右孩子 2 * i + 1 。
树中每个节点都有一个值,用下标从 0 开始、长度为 n 的整数数组 cost 表示,其中 cost[i] 是第 i + 1 个节点的值。每次操作,你可以将树中 任意 节点的值 增加 1 。你可以执行操作 任意 次。
你的目标是让根到每一个 叶子结点 的路径值相等。请你返回 最少 需要执行增加操作多少次。
注意:
满二叉树 指的是一棵树,它满足树中除了叶子节点外每个节点都恰好有 2 个节点,且所有叶子节点距离根节点距离相同。
路径值 指的是路径上所有节点的值之和。
4.3 解题代码
class Solution {
public:
int minIncrements(int n, vector<int>& cost) {
int leaf_num = n / 2;
int res = 0;
for(int i = leaf_num - 1; i >= 0; --i){
int max0 = max(cost[2 * i + 1], cost[2 * i + 2]);
int min0 = min(cost[2 * i + 1], cost[2 * i + 2]);
cost[2 * i + 1] = max0;
cost[2 * i + 2] = max0;
res += (max0 - min0);
cost[i] += max0;
}
return res;
}
};
4.4 解题思路
(1) 自底向上讨论问题。答案记录为res。
(2) 首先从最底层的非叶子节点开始遍历,一直到根节点。取两个叶子结点的最大值为max0,两个节点的最小值为min0,那么 res += (max0 - min0)。然后当前遍历到的节点加上max0.
(3) 最后返回res即可。
打鸡血
心若在,梦就在,只不过是从头再来。哪怕每次周赛一题都做不出来,都得努力去研究,因为未来的某一天一定能够进步的。