LeetCode 刷题笔记（九）

这次的主题是链表、回溯

ID:3

思路历程：第二次刷了，详看上次的题解

answer:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        if(n<=1)return n;
        if(n==2)return s[0]==s[1]?1:2;
        int res=0;
        unordered_set<char>hash;
        int i=0,l=1;
        hash.insert(s[0]);
        while(i<n&&l<n){
            if(hash.find(s[l])!=hash.end()){
                res=max(res,l-i);
                while(hash.find(s[l])!=hash.end()){
                    hash.erase(s[i]);
                    i++;
                }
            }else{
                hash.insert(s[l]);
                l++;
            }
        }
        res=max(res,l-i);
        return res;
    }
};

ID:438

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

思路历程：

一开始想着用map，然后觉得有点麻烦，后来改用暴力求解，每次固定滑窗往右，然后sort子串进行比较

超时...G

后来看了题解，和上面这道题很像

answer:

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        map<char,int> map_s,map_p;
        int n =s.size();
        int count =p.size();
        for(auto c:p)map_p[c]++;
        int i=0,j=0;
        vector<int> res;
        while(j<n){
            char c=s[j];
            map_s[c]++;
            while(map_s[c]>map_p[c])map_s[s[i++]]--;
            if(map_p==map_s)res.push_back(i);
            j++;
        }
        return res;
    }
};

关键点：

while(map_s[c]>map_p[c])map_s[s[i++]]--;保证窗口滑动的关键

每次一旦出现了非窗口需要的字符，就进行左指针滑动

ID: 5

思路历程:

一开始没考虑奇偶，或者说只考虑了偶数回文子串

后来考虑了奇偶，但没进行优化，利用了两个双层循环

优化之后可以一层循环中，同时进行奇偶的回文检验

answer:

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n == 1) return s;
        string ans = string(1, s[0]);
        int ans_length = 1; 
        for (int mid = 0; mid < n; ++mid) {
            int i = mid, j = mid;
            while (i >= 0 && j < n && s[i] == s[j]) {
                if (j - i + 1 > ans_length) {
                    ans_length = j - i + 1;
                    ans = s.substr(i, ans_length);
                }
                i--; j++;
            }
            i = mid, j = mid + 1;
            while (i >= 0 && j < n && s[i] == s[j]) {
                if (j - i + 1 > ans_length) {
                    ans_length = j - i + 1;
                    ans = s.substr(i, ans_length);
                }
                i--; j++;
            }
        }
        return ans;
    }
};

ID:239

思路历程:

有一说一，一开始想的是最好在滑窗中有个状态记录最大值，还是很不错的

但是每次滑动都要更新一下，是新的值最大还是剩下的里面挑

这个更新过程我偷懒了，用了map的底层红黑树机制，让容器自动帮我排列

然后使用了迭代器找了最后一个元素（最大值）

AC了，就是时间有点长

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n=nums.size();
        int i=0,j=0;
        map<int,int> sub;
        while(j<k){
            sub[nums[j]]++;
            j++;
        }
        vector<int> res;
        while(j<n){
            auto c= std::prev(sub.end());
            res.push_back(c->first);
            sub[nums[i]]--;
            if(sub[nums[i]]==0)sub.erase(nums[i]);
            i++;
            sub[nums[j++]]++;
        }
        auto c= std::prev(sub.end());
        res.push_back(c->first);
        return res;
    }
};

其实和官方题解中的优先队列意思差不多

ID:41

...这题目意思真的有点模糊

思路历程:

首先sort数组，然后筛掉所有非正数

此时如果已经筛完了，返回1

如果没筛完第一个不是1，返回1

在正数中循环遍历，如果后一个数!=pre或者!=pre+1 跳出循环

不管有没有遍历完都返回nums[i]+1

answer:

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

ID:54

思路历程:

我一开始就想着用DFS的思路，递归调用走完全程

但最初没有想到维持上次的方向，后来在递归中加了个状态实现了

最后别忘了递归退出条件，我是在递归中由加了个计数器进行状态

answer:

class Solution {
    vector<int>res;
    int dcts[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
    void dfs(vector<vector<int>>& matrix,vector<vector<int>>visit,int nowx,int nowy,int i,int count){
        if(count<=0)return;
            int* dct=dcts[i];
            int nextx=nowx+dct[0];int nexty=nowy+dct[1];
            if(nextx<0||nextx>=matrix.size()||nexty<0||nexty>=matrix[0].size()){//超出边界
                i= i==3?0:i+1;
                dfs(matrix,visit,nowx,nowy,i,count);
            }else{
                if(visit[nextx][nexty]==0){
                    res.push_back(matrix[nextx][nexty]);
                    visit[nextx][nexty]=1;
                    dfs(matrix,visit,nextx,nexty,i,--count);
                }else{//访问过
                    i= i==3?0:i+1;
                    dfs(matrix,visit,nowx,nowy,i,count);
                }
            }
        
    }
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<vector<int>> visit(matrix.size(),vector<int>(matrix[0].size(),0));
        res.push_back(matrix[0][0]);
        visit[0][0]=1;
        dfs(matrix,visit,0,0,0,matrix[0].size()*matrix.size()-1);
        return res;
    }
};

ID:17

思路历程:

一个较为经典的回溯题，要实现全排列的结果

难点在于string类的方法要了解

string类是特殊的vector，因此也有pop_back 操作，（回溯时使用）

answer:

class Solution {
public:
    map<char,string>num_char;
    void init(map<char,string>&num_char){
        num_char['2']="abc";
        num_char['3']="def";num_char['4']="ghi";num_char['5']="jkl";num_char['6']="mno";
        num_char['7']="pqrs";num_char['8']="tuv";num_char['9']="wxyz";
    }
    vector<string> ans;
    string sub_res="";
    void dfs(string digits){
        if(digits.size()==0&&sub_res.size()!=0){
            ans.push_back(sub_res);
            return;
        }
        
        for(auto c:num_char[digits[0]]){
            sub_res+=c;
            dfs(digits.substr(1,digits.size()-1));
            sub_res.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        init(num_char);
        dfs(digits);
        return ans;
    }
};

ID:236

思路历程:

一开始想着用map，但是后来想，既然路径是有序的，不如用vector动态数组

这样路径分叉就返回结果即可

总体主要还是DFS的思路，用来获取到达目标节点的有效路径

但是为了在遇到错误路径时返回分叉点，需要用的回溯

answer:

class Solution {
public:
    bool dfs(TreeNode* root,TreeNode* target,vector<TreeNode*>& line){
        if(!root)return false;
        line.push_back(root);
        if(root==target)return true;
        if(dfs(root->left,target,line)||dfs(root->right,target,line))return true;
        line.pop_back();//回溯
        return false;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode*>line_p;
        vector<TreeNode*>line_q;
        TreeNode* ans=root;
        dfs(root,p,line_p);dfs(root,q,line_q);
        for(int i=0;i<line_p.size()&&i<line_q.size();i++){
            if(line_p[i]!=line_q[i])break;
            ans=line_p[i];
        }
        return ans;
    }
};

ID:200

思路历程:

这道题之前做过，但之前用的是BFS，而且另开了一个visit数组标记状态，用方向数组实现遍历

这次用的DFS，递归走完岛屿，每一次调用递归就是一个岛屿，更好理解

answer:

class Solution {
public:
    void dfs(vector<vector<char>>& grid,int x,int y){
        if(grid[x][y]=='0'){
            return;
        }
        grid[x][y]='0';
        if(x<grid.size()-1)dfs(grid,x+1,y);
        if(x>0)dfs(grid,x-1,y);
        if(y<grid[0].size()-1)dfs(grid,x,y+1);
        if(y>0)dfs(grid,x,y-1);
    }
    int numIslands(vector<vector<char>>& grid) {
        int ans=0;
        int m=grid.size();
        int n=grid[0].size();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]=='1')
                {
                    dfs(grid,i,j);
                    ans++;
                }
            }
        }
        return ans;
    }
};

思路历程:

一开始回溯写的很标准，但是出现了重复的问题，

想要加个set实现去重操作，但是不仅浪费时间，还会有逻辑错误（回头重新加）

比如 [2,3] ->8 会出现 [2,3,3] [3,2,3],[3,3,2]各种

所以最好在递归调用的时候加入一个索引 index, 以记录之前的状态和之后的状态

循环可以直接从index 开始，递归调用的时候，就放入当前 i

answer:

class Solution {
public:
    vector<vector<int>> ans;
    vector<int>sub_ans;
    void bkt(vector<int>&candidates , int target,int index){
        if(target==0){
                ans.push_back(sub_ans);
            return;
        }else{
            for(int i=index;i<candidates.size();i++){
                int rest=target-candidates[i];
                if(rest>=0){
                    sub_ans.push_back(candidates[i]);
                    bkt(candidates,rest,i);
                    sub_ans.pop_back();
                }
            }
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        bkt(candidates,target,0);
        return ans;
    }
};

ID:22

思路历程:

主要还是回溯的思想，关键是状态转移的思想怎么实现？

用剩余左右括号数量来记录

左括号数量要大于等于右括号，然后开始递归调用

answer:

class Solution {
public:
    vector<string> ans;
    string sub_ans="";
    void bkt(int m,int n){// m是'( '剩下值，n是') '剩下值
        if(m<0||n<0)return;
        if(m==0&&n==0){
            ans.push_back(sub_ans);
        }
        if(m<=n){
            sub_ans+='(';
            bkt(m-1,n);
            sub_ans.pop_back();
            sub_ans+=')';
            bkt(m,n-1);
            sub_ans.pop_back();
        }
    }
    vector<string> generateParenthesis(int n) {
        bkt(n,n);
        return ans;
    }
};

ID: 79

思路历程:

一开始虽然想到了DFS，使用索引index作为结束的判断符

但忘记了避免访问已访问的格子（回溯）

同时，选择了分别四个方向判断边界后再递归调用

这样如果左右有相同的字母，则会只返回先执行的一条路

如：ESE，从S出发，如果直接return左边的递归显然不正确

所以建议每次DFS在一开始就判断四个方向是否出界，如果出界直接return false

然后 bool ans = 上||下||左||右四个方向递归的或结果

answer:

class Solution {
public:
    bool bkt(vector<vector<char>>& board,string word,int x,int y,int index){
        if(index==word.size())return true;
        if(x < 0 || x >= board.size() || y < 0 || y >= board[0].size() || board[x][y] != word[index]) return false;
        char tmp = board[x][y];
        board[x][y]='#';
        bool found = bkt(board,word,x-1,y,index+1)||bkt(board,word,x,y-1,index+1)||bkt(board,word,x+1,y,index+1)||bkt(board,word,x,y+1,index+1);
        board[x][y]=tmp;
        return found;
    }
    bool exist(vector<vector<char>>& board, string word) {
        for(int i=0;i<board.size();i++){
            for(int j=0;j<board[0].size();j++){
                if(board[i][j]==word[0]){
                    if(bkt(board,word,i,j,0))return true;
                }
            }
        }
        return false;        
    }
};

省了两道难的，下次重点攻破

爱鹅，信鹅，等鹅，求求速速OC