LeetCode刷题笔记 ---（七）

刚发完一篇博客，过来刷会儿题

ID：994

简单的一道BFS，感觉BFS就是写起来麻烦一点，思路还是很清晰的

answer：

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        vector<vector<int>> steps={{-1,0},{1,0},{0,1},{0,-1}};
        int res=0;
        vector<vector<int>> visit(grid.size(),vector<int>(grid[0].size(),0));
        int count_fresh=0;
        queue<pair<int,int>> bfs;
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){
                if(grid[i][j]==1){
                    count_fresh++;
                }
                if(grid[i][j]==2){
                    bfs.push({i,j});
                }
            }
        }
        if(count_fresh==0)return 0;
        if(bfs.empty())return -1;
        while(!bfs.empty()){
            int count=bfs.size();
            while(count--){
                auto now=bfs.front();bfs.pop();
                visit[now.first][now.second]=1;
                for(auto step:steps){
                    int next_x=now.first+step[0];
                    int next_y=now.second+step[1];
                    if(next_x>=0&&next_x<grid.size()&&next_y>=0&&next_y<grid[0].size()){
                        if(grid[next_x][next_y]==1&&visit[next_x][next_y]==0){
                            count_fresh--;
                            visit[next_x][next_y]=1;
                            grid[next_x][next_y]=2;
                            bfs.push({next_x,next_y});
                        }
                    }
                }
            }
            res++;
        }
        if (count_fresh==0) return res-1;
        return -1;
    }
};

tips:记得提前处理特殊情况，如没有烂橘子，或者没有新鲜橘子

2024.2.5 终于拿到驾照了，继续加油，希望新的一年爱情事业双丰收，加油！

ID：49

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

思路历程：

一开始想到了用哈希，然后看了眼提示，确实是。

确认之后一开始想着用哈希表组，每组记录字符串单词，

后来想开了，用sort函数排完序后，都是一样的，这样直接插入哈希表就行

answer：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        int n= strs.size();
        if(n==0)return{{}};
        map<string,vector<string>> all_string;
        vector<vector<string>> res;
        for(int i=0;i<n;i++){
            string right_string=strs[i];
            sort(strs[i].begin(),strs[i].end());
            all_string[strs[i]].push_back(right_string);
        }
        for(auto c:all_string){
            res.push_back(c.second);
        }
        return res;
    }
};

ID：118

给定一个非负整数 *numRows，*生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

思路历程：

可以用递归，也可以直接加

answer：

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        if(numRows==1)return {{1}};
        if(numRows==2)return {{1},{1,1}};
        vector<vector<int>> res;
        res.push_back({1});res.push_back({1,1});
        int i=2;
        while(i<numRows){
            vector<int>tmp;
            tmp.push_back(1);
            for(int j=0;j<i-1;j++){
                tmp.push_back(res[i-1][j]+res[i-1][j+1]);
            }
            tmp.push_back(1);
            res.push_back(tmp);
            i++;
        }
        return res;
    }
};

今天有点累，做一道简单的先休息吧

ID：128

新年快乐！2024.2.11

这篇拖的好像有点久了，没时间难过了，即将到来的是新年第一题！

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

思路历程：

注意点主要在于遇到重复的数字别忘了跳过

answer：

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int n= nums.size();
        int i=0;
        int res=0;
        if(!n)return 0;
        int tmp_max=1;
        while(i<n-1){
            if(nums[i+1]==nums[i]+1){
                tmp_max++;
            }else if(nums[i+1]==nums[i]){
                i++;
                continue;
            }else{
                res=max(res,tmp_max);
                tmp_max=1;
            }
            i++;
        }
        return max(res,tmp_max);
    }
};

ID：300

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

思路历程：

唉，一开始想着用栈去解决，但是不太对啊，因为每次压栈都是以栈顶为标准，一旦出现1,3,2,3就会出现1,3压栈后，2,3无法入栈

最终结果变为2，而不是3。

所以还是要记录状态，既然要记录状态，那么很容易联想到DP

作为DP去解决的话，思路就很清晰了，向后遍历的同时，向前遍历，找出深度最大且比自己小的值，然后+1

answer：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n=nums.size();
        if(n==1)return 1;
        int i=0;
        vector<int>res(nums.size(),1);
        int res_max=1;
        while(i<n){
            if(i>0){
                int tmp_max=0;
                for(int j=i;j>-1;j--){
                    if(nums[j]<nums[i]){
                        tmp_max=max(tmp_max,res[j]);
                    }
                }
                cout<<tmp_max<<endl;
                res[i]=tmp_max+1;
                res_max=max(res_max,res[i]);
            }
            i++;
        }
        return res_max;
    }
};

ID：42

思路历程：

一开始想着单调栈，但后来发现和之前一道股票题有点像

都是单调性入手，如果递增结束，就寻找之前的最高点

最高点比自己高，就以自己为参照，如果最高点比自己低，就以最高点为参照

同时，由于可能出现42324这种情况，还需要在更新状态的同时，清空老状态

之前一直都陷入了思维误区，一直以为峰值才能接水，实际上，只要开始出现递增，就可以进行接水。

哪怕多接了，也没关系，可以在后续的接水中清除之前的状态

这里要注意一个问题，就是在找前点的时候，遇到比自己大的第一个点就得停下。如果没有就找前面的最大值

answer：

class Solution {
public:
    int trap(vector<int>& height) {
        int n=height.size();
        vector<int>state(height.size(),0);
        int i=1;
        while(i<n){
            if(height[i]>height[i-1]){
        		//往前找的过程中，如果遇到比自己大的，可以直接停下来
        		//如果没有，就遍历找一个最大值
                int tmp_max=0;
                int max_left=0;
                for(int j=i-1;j>-1;j--){
                    if(height[i]<=height[j]){
                        max_left=j;
                        tmp_max=height[j];
                        break;
                    }
                    if(tmp_max<=height[j]){
                        max_left=j;
                        tmp_max=height[j];
                    }
                }
                state[i]=(i-max_left-1)*min(height[i],tmp_max);
                for(int j=max_left+1;j<i;j++){
                    state[i]-=height[j];
                    state[j]=0;
                }
            }   
            i++;
        }
        i=0;
        int res=0;
        while(i<n)res+=state[i++];
        return res;
    }
};

题解当中的解法更加简单一点，可以选择单调栈，也可以选择DP

ID：189

思路历程：

...很快，很简单

多开一个数组的话非常快，改下下标然后重新赋值数组就行

answer：

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n=nums.size();
        vector<int> res(n,0);
        int i=0;
        k=k%n;
        int tmp_i=n-k;
        int j=0;
        while(k+j<n){
            res[k+j]=nums[j];
            j++;
        }
        while(i<n){
            if(tmp_i+i<n){
                res[i]=nums[tmp_i+i];
                i++;
            }else break;
        }
        nums=res;
    }
};

ID：76

思路历程：

好难的一道题，如果t内的字母不会重复还好，可以双指针一点点往内部缩小范围

但如果有字母重复，那该怎么办

哈希表尝试一下，先将子串全部纳入哈希表，second用来记录个数

我利用双指针，一个从左往右，一个从右往左

如果如果s的哈希表数值等于t了，就停止

通过了一部分样例，但遇到这个例子该怎么办cabwefgewcwaefgcf

刚才的想法还行，但是如果实现的时候先左指针动，然后右指针动，容易出现结果靠右；右指针先动同理

看了题解后：

我可以右指针和左指针同时从起点出发
右指针往右走的时候，将S的map记录进去，而不是一开始就记录

一开始就记录的话，窗口内是否满足不能确定，所以滑动窗口的灵魂就在于，每次满足窗口内状态满足（或者富余了，再进行缩减窗口）
加个计数器来验证状态

如果t中的计数次数>=s，则纳入窗口

检查i的状态，如果s中的字母多了，i往右走

每次查看计数器是否达到t的大小

class Solution {
public:
    string minWindow(string s, string t) {
        int m=s.size();
        int n=t.size();
        map<char,int> t_map;
        map<char,int> s_map;
        if(n>m)return "";
        //记录t的字母
        for(int i=0;i<n;i++){
            if(t_map.find(t[i])!=t_map.end()){
                t_map[t[i]]++;
            }else{
                t_map[t[i]]=1;
            }
        }
        int i=0;
        int count=0;
        string res=s;
        bool flag=false;
        for(int j=0;j<m;j++){
            s_map[s[j]]++;
            if(t_map[s[j]]>=s_map[s[j]]) count++;
            while(s_map[s[i]]>t_map[s[i]]) --s_map[s[i++]];
            if(count==n){
                if(j-i+1<=res.size()){
                    flag=true;
                    res=s.substr(i,j-i+1);
                }
            }
        }
        if(flag)return res;
        else return "";
    }
};

为什么计数器只加不减？

因为某个字母数量满足，计数器就不会再加

不满足才会加，所以一旦到t的大小，就说明每个字母都满足了

那么什么时候更新呢？

就在左指针所在字母的数量超标时，更新，直到当前字母未达标

为什么需要flag？

因为有时候没有匹配到相应子串，需要返回空

这篇博客拖了好久，虽然没什么人看，但还是要和自己说声抱歉

休息可以，懈怠不行

共勉