当前位置：首页 > article >正文

刷题日记5

article 2025/2/26 5:53:13

2025.2.17

1358. 包含所有三种字符的子字符串数目

class Solution {
public:
    int numberOfSubstrings(string s) {
        int l=0,r=0,res=0;
        vector<int>num(3,0);
        while(r<s.size()){
            int tmp=s[r]-'a';
            num[tmp]++;
            while(num[0]&&num[1]&&num[2]){
                tmp=s[l]-'a';
                num[tmp]--;
                l++;
            }
            res+=l;
            r++;
        }
        return res;
    }
};

思考：1.题目是求目标子数组，长度是越长越好，那么规律就是找到每一个符合条件的最短子数组，res+=1+l-1=l;因为最短的符合条件的子数组，再在他的左边加数，也还是符合。

2.双指针构成滑动窗口，右指针遍历整个数组，当a,b,c都出现时，左指针右移，缩小窗口。那么什么时候统计满足条件的子数组个数？右指针每次右移时，更新res+=l;

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

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int k) {
        int l=0,r=0,max=0;
        int cnt=0;
        long long res=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]>max)max=nums[i]; 
        }
        while(r<nums.size()){
            if(nums[r]==max)cnt++;
           while(cnt>=k){
            if(nums[l]==max)cnt--;
            l++;
           }
           res+=l;
           r++;
        }
        return res;
    }
};

思考：和上一题一样。

2025.2.18

3325. 字符至少出现 K 次的子字符串 I

class Solution {
public:
    int numberOfSubstrings(string s, int k) {
        int l=0,r=0,res=0;
        vector<int>num(26,0);
        while(r<s.size()){
            num[s[r]-'a']++;//右指针遍历，
            //右指针对应的字符出现的次数>=k时，缩短窗口
            while(num[s[r]-'a']>=k){
                num[s[l]-'a']--;
                l++;
            }
            res+=l;
            r++;
        }
        return res;
    }
};

思考：1.右指针遍历，并且每次累加指针对应字符的出现次数。

2.右指针每次遍历时，累加完出现次数，还判断次数是否超过k。如果超过就缩小窗口大小。

3.res=+l。右指针每次右移一次都执行res+=l；

2799. 统计完全子数组的数目

class Solution {
public:
    int countCompleteSubarrays(vector<int>& nums) {
        unordered_map<int,int>m;
        for(int i=0;i<nums.size();i++){
            m[nums[i]]++;
        }
        int k=m.size();
        unordered_map<int,int>map;
        int l=0,r=0,res=0;
        while(r<nums.size()){
            map[nums[r]]++;
            while(map.size()==k){
                if(!--map[nums[l]])map.erase(nums[l]);
                l++;
            }
            res+=l;
            r++;
        }
        return res;
    }
};

思路：思想都一样，res+=l;这其中不同的区别就是二层循环的判断条件。

2537. 统计好子数组的数目

class Solution {
public:
    long long countGood(vector<int>& nums, int k) {
        int l=0,r=0,cnt=0;
        long long res=0;
        unordered_map<int,int>map;
        while(r<nums.size()){
            cnt+=map[nums[r]]++;
            while(cnt>=k){
                cnt-=--map[nums[l]];
                l++;
            }
            res+=l;
            r++;
        }
        return res;
    }
};

思考：1.卡壳的地方是：如何统计右移后数字对的对数。二层循环中的条件如何设置。

2.模拟一下就知道了。从0到1，cnt+=0。从1到2，cnt+=1。从2到3，cnt+=2。

同理：从3到2，cnt-=2.从2到1，cnt-=1。从1到0，cnt-=0。

2025.2.19

713. 乘积小于 K 的子数组

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int l=0,r=0,res=0,cnt=1;
        while(r<nums.size()){
            cnt*=nums[r];
            while(cnt>=k&&l<=r){
                cnt=cnt/nums[l];
                l++;
            }
            res+=r-l+1;
            r++;
        }
        return res;
    }
};

思考：1.数组越短越好，res+=r-l+1

2.注意二层循环可能因为cnt一直>=k，一直循环下去，导致数组越界。需要加上l<=r、

3258. 统计满足 K 约束的子字符串数量 I

class Solution {
public:
    int countKConstraintSubstrings(string s, int k) {
        int l=0,r=0,res=0;
        vector<int>num(2,0);
        while(r<s.size()){
            num[s[r]-'0']++;
            while(num[0]>k&&num[1]>k){
                num[s[l]-'0']--;
                l++;
            }
            res+=r-l+1;
            r++;
        }
        return res;
    }
};

2302. 统计得分小于 K 的子数组数目

class Solution {
public:
    long long countSubarrays(vector<int>& nums, long long k) {
        int l=0,r=0;
        long long res=0,cnt=0;;
        while(r<nums.size()){
            cnt+=nums[r];
            while(cnt*(r-l+1)>=k){
                cnt-=nums[l];
                l++;
            }
            res+=r-l+1;
            r++;
        }
        return res;
    }
};

思考：公式真好用，直接秒。

查看全文

http://www.kler.cn/a/561337.html