leetcode4.17-23

Leetcode4.17-4.23

4.17

滑动窗口

904.水果成篮

这个题目有点难理解，意思就是找至多包含两种元素的最长子串，返回其长度

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int i=0;
        int count=1;
        int result=1;
        vector<int> kind(fruits.size(),0);
        kind[fruits[i]]++;
        for(int j=1;j<fruits.size();j++){
            if(kind[fruits[j]]==0){
                kind[fruits[j]]++;
                count++;
            }
            else
            {
                kind[fruits[j]]++;/*注意1*/
            }
            
            while(count>2){
                kind[fruits[i]]--;
                if(!kind[fruits[i]]){
                    count--;
                }
                i++;
            }
            result=result>(j-i+1)?result:j-i+1;
        }
        return result;
    }
};

滑动窗口加哈希表

改了两次bug 终于改对了 第一次是没注意已经放入HASH表中的元素遍历过程中对hash表的影响，即kind[fruits[j]]++;

还有就是我J从1开始，所以result开始时要设置为1；

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int n = fruits.size();
        unordered_map<int, int> cnt;

        int left = 0, ans = 0;
        for (int right = 0; right < n; ++right) {
            ++cnt[fruits[right]];
            while (cnt.size() > 2) {
                auto it = cnt.find(fruits[left]);
                --it->second;
                if (it->second == 0) {
                    cnt.erase(it);
                }
                ++left;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/fruit-into-baskets/solutions/1893352/shui-guo-cheng-lan-by-leetcode-solution-1uyu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

我是用了一个向量起到了HASH的作用，官方直接用了相应的类，直接调用方法方便多了（unordered_map）

4.18

滑动算法

今天看一下labuladong的滑动窗口模板，解决一下这道困扰我很久的问题

unordered_map 就是哈希表（字典），相当于 Java 的 HashMap，它的一个方法 count(key) 相当于 Java 的 containsKey(key) 可以判断键 key 是否存在。

76最小覆盖字串

模板框架

/* 滑动窗口算法框架 */
void slidingWindow(string s) {
    // 用合适的数据结构记录窗口中的数据
    unordered_map<char, int> window;
    
    int left = 0, right = 0;
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        winodw.add(c)
        // 增大窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        /*** debug 输出的位置 ***/
        // 注意在最终的解法代码中不要 print
        // 因为 IO 操作很耗时，可能导致超时
        printf("window: [%d, %d)\n", left, right);
        /********************/
        
        // 判断左侧窗口是否要收缩
        while (left < right && window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            winodw.remove(d)
            // 缩小窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

1. 窗口数据的更新
2. 判断左侧窗口是否收缩的条件
3. 滑动过程中题目所求的结果确认（最大或者最小）

（基本都用HASH表作为窗口数据的统计，然后写出判断条件）

这些点因题而异，但是基本逃不出上面的框架。

class Solution {
public:
    string minWindow(string s, string t) {
        int left=0,right=0;
        int count=0;
        int start=0,len=INT_MAX;
        unordered_map<char,int> need,window;
        for(char c : t) need[c]++;
        while(right<s.size()){
            char c=s[right];
            right++;
            if(need.count(c)){
                window[c]++;
                if(window[c]==need[c]){
                    count++;
                }
            }
            while(count==need.size()){
                if(right-left<len){
                    len=right-left;
                    start=left;
                }
                char d=s[left];
                left++;
                if(need.count(d)){
                   
                    if(need[d]==window[d]){
                        count--;
                    }
                    window[d]--;
                }
            }
        }
        return len==INT_MAX?"":s.substr(start,len);
};
};

4.19

滑动窗口

3 无重复字符的最长子串

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int left=0,right=0;
        unordered_map<char,int> window;
        int result=0;
        while(right<s.size()){
            char c=s[right];
            right++;
            window[c]++;
            while(window[c]>1){
                char d=s[left];
                left++;
                window[d]--;
            }
            result=result>right-left?result:right-left;
        }
        return result;
    }
};

438 找到字符串中所有字母异位词

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int left=0,right=0;
        unordered_map<char,int> need,window;
        for(char c:p) need[c]++;
        int count=0;
        vector<int> result;
        while(right<s.size()){
            char c=s[right];
            right++;
            if(need.count(c)){
                window[c]++;
                if(need[c]==window[c]){
                    count++;
                }
            }
            while(right-left>=p.size()){
                if(count==need.size())
                    result.push_back(left);
                char d=s[left];
                left++;
                if(need.count(d)){
                    if(window[d]==need[d])
                    {
                        count--;
                    }
                    window[d]--;
                }
            }
        }
        return result;
    }
};

两道题都套用了昨天的模板，太爽了，第一次做力扣这么舒服

4.20

151.反转字符串中的单词

这道题如果不用api，单纯的用C++的方式原地反转很复杂

先整个字符串反转，再分别反转字符串里面的单词

单词间可能不止一个空格，第一个单词和最后一个单词外面可能还有空格，要对字符串进行相应的处理

class Solution {
public:
    string reverseWords(string s) {
        reverse(s,0,s.size()-1);
        int i=0,j=0;
        removespace(s);
        while(j<s.size()){
            if(s[j]==' '){
                reverse(s,i,j-1);
                i=j+1;
            }
            j++;
            if(j==s.size()-1){
                reverse(s,i,j);
            }
        }
       return s;

    }
    void reverse(string& s,int start,int end){
        
        while(start<end){
            swap(s[start],s[end]);
            start++;
            end--;
        }
    }
    void removespace(string& s){
        int slow=0,fast=0;
        while(s[fast]==' '){
            fast++;
        }
        while(fast<s.size()){
            if(fast>0&&s[fast]==' '&&s[fast-1]==' '){
                fast++;
            }
            else s[slow++]=s[fast++];
            
        }
        if(slow>0&&s[slow-1]==' '){
            slow--;
        }
        s.resize(slow);
    }
};

4.22

59螺旋矩阵 II

这个属于二维数组的花式遍历部分，直接上代码，最近忙项目，代码题解这能轻微带过，希望刷题量还能保持

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n,vector<int>(n,0));
        int up=0,low=n-1;
        int left=0,right=n-1;
        int num=1;
        while(num<=n*n)
        {
            if(up<=low){
                for(int j=left;j<=right;j++){
                    res[up][j]=num++;
                }
                up++;
            }
            if(left<=right){
                for(int i=up;i<=low;i++){
                    res[i][right]=num++;
                }
                right--;
            }
            if(up<=low){
                for(int j=right;j>=left;j--){
                    res[low][j]=num++;
                }
                low--;
            }
            if(left<=right){
                for(int i=low;i>=up;i--){
                    res[i][left]=num++;
                }
                left++;
            }
        }
        return res;
    }
};