您现在的位置是:首页 >其他 >LeetCode周赛复盘(第344场周赛)网站首页其他

LeetCode周赛复盘(第344场周赛)

HEU_firejef 2024-06-08 12:00:02
简介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即可。

打鸡血

心若在,梦就在,只不过是从头再来。哪怕每次周赛一题都做不出来,都得努力去研究,因为未来的某一天一定能够进步的。

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。