寒假刷题Day8

一、2831. 找出最长等值子数组

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

如果子数组中所有元素都相等，则认为子数组是一个 等值子数组 。注意，空数组是 等值子数组 。

从 nums 中删除最多 k 个元素后，返回可能的最长等值子数组的长度。

子数组 是数组中一个连续且可能为空的元素序列。

代码：

class Solution {
public:
    int longestEqualSubarray(vector<int>& nums, int k) {
        //参考评论，是在下标哈希表上滑窗
        
        //举例说明：
        //比如pos[3] = [1, 3, 5]
        //元素 3 分别在 下标1 下标3 下标5 出现
        //对 pos[3]进行滑窗

        //当left = 0, right = 1 时
        //pos[1] - pos[0] + 1 =  3。表示：在原数组下标1 到下标3的子数组长度
        //right - left + 1 = 2      表示：在原数组下标1 到下标3这段子数组中，相同元素3有两个
        //二者相减即为：该子数组中除去相同元素3的不同元素
        //一旦不同元素的个数超过题目要求的k，就应该缩减窗口
        //否则继续扩大窗口 
        int ans = 0;
        int n = nums.size();
        vector<vector<int>> pos_list(n + 1);
        for (int i = 0; i < n; i++) {
            pos_list[nums[i]].push_back(i);
        }

        for (auto pos : pos_list) {
            int left = 0;
            for (int right = 0; right < pos.size(); right++) {
                while ((pos[right] - pos[left]) - (right - left) > k) {
                    left++;
                }
                //要求的是删除最多k个元素之后 最长等值子数组
                //ans = max(ans, pos[right] - pos[left] + 1);
                ans = max(ans, right - left + 1);
            }
        }
        return ans;
    }
};

思路：

1.记录下标的哈希表+滑动窗口，这题还不太明白，待后续复盘，难度1900有点超过现在的能力

二、209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组

 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

代码：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int ans = n + 1, sum = 0;
        int l = 0;

        for(int r = 0; r < n; ++r){
            sum += nums[r];

            // if(sum < target) continue;

            while(sum >= target){
                ans = min(ans, r - l + 1);
                sum -= nums[l];
                l++;
            }
        }
         return (ans == nums.size() + 1) ? 0 : ans;
    }
};

思路：
1. 从求最长窗口到最短窗口，思路还是遍历r -> 通过右移r维护修正 -> 判断ans

三、2904. 最短且字典序最小的美丽子字符串

给你一个二进制字符串 s 和一个正整数 k 。

如果 s 的某个子字符串中 1 的个数恰好等于 k ，则称这个子字符串是一个 美丽子字符串 。

令 len 等于 最短 美丽子字符串的长度。

返回长度等于 len 且字典序 最小 的美丽子字符串。如果 s 中不含美丽子字符串，则返回一个 空 字符串。

对于相同长度的两个字符串 a 和 b ，如果在 a 和 b 出现不同的第一个位置上，a 中该位置上的字符严格大于 b 中的对应字符，则认为字符串 a 字典序 大于 字符串 b 。

• 例如，"abcd" 的字典序大于 "abcc" ，因为两个字符串出现不同的第一个位置对应第四个字符，而 d 大于 c 。

代码：

class Solution {
public:
    string shortestBeautifulSubstring(string s, int k) {
        if (count(s.begin(), s.end(), '1') < k) {
            return "";
        }
        string ans = s;
        int cnt1 = 0, left = 0;
        for (int right = 0; right < s.length(); right++) {
            cnt1 += s[right] - '0';
            while (cnt1 > k || s[left] == '0') {
                cnt1 -= s[left++] - '0';
            }
            if (cnt1 == k) {
                string t = s.substr(left, right - left + 1);
                if (t.length() < ans.length() || t.length() == ans.length() && t < ans) {
                    ans = move(t);
                }
            }
        }
        return ans;
    }
};

思路：

1. cnt1 -= s[left++] - '0' 巧妙将字符计数转化为数字计数

2.substr的用法，move的用法