力扣周赛题目训练

主要是训练思维题和技巧题

滑动窗口：

  1. 2799. 统计完全子数组的数目
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int countCompleteSubarrays(vector<int> &nums) {
        int m = unordered_set<int>(nums.begin(), nums.end()).size();
        unordered_map<int, int> cnt;
        int ans = 0, left = 0;
        for (int v: nums) 
        { 
            cnt[v]++;
            while (cnt.size() == m) 
            {
                int x = nums[left++];
                if (--cnt[x] == 0)
                    cnt.erase(x);
            }
            ans += left; 
        }
        return ans;
    }
};

2825. 循环增长使字符串子序列等于另一个字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool canMakeSubsequence(string str1, string str2) {
        int m = str1.length(), n = str2.length();
        if (m < n) return false;

        auto rotate = [](char c) { return (c + 1 - 'a') % 26 + 'a'; };

        int i = 0, j = 0;
        for (; i < m && j < n; i ++) 
            if (str1[i] == str2[j] || rotate(str1[i]) == str2[j]) 
                j ++;
        return j == n;
    }
};

2760. 最长奇偶子数组

注意是i=j，这里的逻辑是继续往后移动，不然就i=j，这是前面不一样的地方，其实j++也行但会慢下来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int longestAlternatingSubarray(vector<int>& nums, int threshold) {
        int res=0;
        for (int i=0;i<nums.size();)
        {
            if(nums[i]>threshold||nums[i]%2!=0)
            {
                i++;
                continue;
            }
            int j=i+1;
            while (j<nums.size()&&nums[j]%2!=nums[j-1]%2&&nums[j]<=threshold){
                j++;
            }
            res=max(res,j-i);
            i=j;
        }
        return res;
    }
};

2909. 元素和最小的山形三元组 II

让中间的数字最大，并且和要最小

不过可以不连续，这就启发我们了

本题就是前后缀分解的思想

直接记录两边的最小值然后枚举中间值，这样就可以实现了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int minimumSum(vector<int>& nums) {
        int n=nums.size();
        int ans=1e9;
        vector<int>dp1(n);//记录从0到第i个数字之间的最小数.
        vector<int>dp2(n);//记录从第n-1到第i个数字之间的最小数.
        dp1[0]=nums[0],dp2[n-1]=nums[n-1];
        for(int i=1;i<n;i++){
            dp1[i]=min(dp1[i-1],nums[i]);
        }
        for(int i=n-2;i>=0;i--){
            dp2[i]=min(dp2[i+1],nums[i]);
        }
        for(int cnt=1;cnt<n-1;cnt++){
            int j=nums[cnt];
            int i=dp1[cnt-1],k=dp2[cnt+1];
            if(j>i&&j>k){
                ans=min(ans,i+j+k);
            }
        }
        return ans==1e9?-1:ans;
    }
};

2958. 最多 K 个重复元素的最长子数组

又是子数组，这样子又是双指针

向右移动到不能再向右移动后就开始向左移动

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxSubarrayLength(vector<int> &nums, int k) {
        int ans = 0, left = 0;
        unordered_map<int, int> cnt;
        for (int right = 0; right < nums.size(); right++) {
            cnt[nums[right]]++;
            while (cnt[nums[right]] > k) {
                cnt[nums[left++]]--;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

2841. 几乎唯一子数组的最大和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    long long maxSum(vector<int>& nums, int m, int k) {
        long long Maxn=0;
        long long sum=0;
        unordered_map<int,int> myMap;
        int j=0;
        for(int i=0;i<nums.size();i++)
        {
            sum+=nums[i];
            myMap[nums[i]]++;
            if(i-j>=k)
            {
                sum-=nums[j];
                if(--myMap[nums[j]]==0) 
                    myMap.erase(nums[j]);
                j++;
            }
            if(i-j+1==k&&myMap.size()>=m) Maxn=max(Maxn,sum);
        }
        return Maxn;
    }
};

2874. 有序三元组中的最大值 II

也是技巧性题目

记录三个最大值

由于i<j<k

因此可以记录最大的i，然后i-j，和现今的k

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    long long maximumTripletValue(vector<int> &nums) {
        long long ret = 0;
        int max_delta = 0, max_i = 0;
        for (int e : nums) {
            ret = max(ret, (long long) max_delta * e);
            max_delta = max(max_delta, max_i - e);
            max_i = max(max_i, e);
        }
        return ret;
    }
};

2779. 数组的最大美丽值

这题就有趣起来了

由于是子序列，因此可以先进行排序，转换一下题目条件就是要<2*k，然后就可以双指针秒杀了

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maximumBeauty(vector<int>& nums, int k) {
        int ans = 0, n = nums.size();
        sort(nums.begin(), nums.end());
        for(int l = 0, r = 0; r < n; ++r) {
            while(nums[l] < nums[r] - 2 * k)    ++l;
            ans = max(ans, r - l + 1);
        }
        return ans;
    }
};

2962. 统计最大元素出现至少 K 次的子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    long long countSubarrays(vector<int> &nums, int k) {
        int mx = *max_element(nums.begin(), nums.end());
        long long ans = 0;
        int cnt_mx = 0, left = 0;
        for (int x : nums) 
        {
            cnt_mx += x == mx;
            while (cnt_mx == k) 
            {
                cnt_mx -= nums[left++] == mx;
            }
            ans += left;
        }
        return ans;
    }
};