【LeetCode】思维向题笔记总结（持续更新）

不全。记录的都是个人认为比较有意思的题。具体有哪些题可以看看目录。

链表相关

单独总结了，这里不再赘述：【LeetCode】链表题总结

双指针

也单独总结了，毕竟双指针很经典：【LeetCode】双指针题总结

滑动窗口

209. 长度最小的子数组（滑动窗口）

209. 长度最小的子数组

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
    int now=0,ans=1e5+10,cnt=0;
    int i=0,j=0,temp=0;
    for(j=0;j<nums.size();j++)
    {
        now+=nums[j];
        while(now>=target)
        {
            ans=min(ans,j-i+1);
            temp++;
            now-=nums[i];
            i++;
        }
    }
    if(!temp) ans=0;
    return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

904. 水果成篮（滑动窗口+哈希）

904. 水果成篮

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
    int ans=0;
    unordered_map<int,int>f;
    int last=0;
    for(int i=0;i<fruits.size();i++)
    {
        f[fruits[i]]++;
        while(f.size()>2)
        {
            f[fruits[last]]--;
            if(f[fruits[last]]==0) 
            {
                f.erase(fruits[last]);
                last++;break;
            }
            else last++;
        }
        ans=max(ans,i-last+1);
    }
    
    return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

模拟相关

59. 螺旋矩阵 II

59. 螺旋矩阵 II

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
    vector<vector<int>>a(n,vector<int>(n,0));//二维数组
    int i=0,j=0;
    a[0][0]=1;
    int now=2;
    while(now<=n*n)
    {
        //右
        while(j+1<n&&!a[i][j+1]&&now<=n*n) 
        {
            // cout<
            a[i][j+1]=now++;
            j++;
        }
        if(now>n*n) break;
        //下
        while(i+1<n&&!a[i+1][j]&&now<=n*n) 
        {
            // cout<
            a[i+1][j]=now++;
            i++;
        }
        if(now>n*n) break;
        //左
        while(j>0&&!a[i][j-1]&&now<=n*n)
        {
            // cout<
            a[i][j-1]=now++;
            j--;
        }
        if(now>n*n) break;
        //上
        while(i>0&&!a[i-1][j]&&now<=n*n)
        {
            // cout<
            a[i-1][j]=now++;
            i--;
        }
        if(now>n*n) break;
    }
    return a;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

哈希表

哈希表概述

图和内容参考：代码随想录

当我们遇到了要快速判断一个元素是否出现集合里的时候，可以用哈希表。

当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。

1. 两数之和（哈希表）

1. 两数之和

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int>mp;
        for(int i=0;i<nums.size();i++)
        {
            int temp=target-nums[i];
            //找到了
            if(mp.find(temp)!=mp.end())
            {
                return {i,mp[temp]};
            }
            //没找到
            else
            {
                mp[nums[i]]=i;
            }
        }
        return {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

454. 四数相加 II（哈希表）

454. 四数相加 II

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int,int>mp;
        for(int i:nums1)
            for(int j:nums2)
            {
                mp[i+j]++;
            }
        
        int ans=0;

        for(int i:nums3)
            for(int j:nums4)
            {
                int temp=i+j;
                if(mp.find(0-temp)!=mp.end())
                {
                    ans+=mp[0-temp];
                }
            }
     
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

字符串

剑指 Offer 05. 替换空格（O(1)的空间复杂度的方法）

剑指 Offer 05. 替换空格

参考：代码随想录

class Solution {
public:
    string replaceSpace(string s) {
        //O(1)的空间复杂度

        int size1=s.size();
        int sp=0;
        for(int i=0;s[i];i++)
        {
            if(s[i]==' ')sp++;
        }

        //扩大长度
        s.resize(s.size()+2*sp);
        for(int i=s.size()-1,j=size1-1;j>=0;i--,j--)
        {
            if(s[j]!=' ') s[i]=s[j];
            else
            {
                s[i]='0';
                s[i-1]='2';
                s[i-2]='%';
                i-=2;
            }
        }
        return s;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

151. 颠倒字符串中的单词（O(1)的空间复杂度的方法）

151. 颠倒字符串中的单词

在原串上操作。参考：代码随想录

class Solution {
public:
    string reverseWords(string s) {
        deleteExtraSpace(s);
        reverse(s.begin(),s.end());
        int l=0,r=0;
        for(int i=0;i<s.size();i++){
            if(s[i]==' '){
                r=i-1;
                swapp(s,l,r);
                l=i+1;
            }
        }
        swapp(s,l,s.size()-1);
        return s;
    }

    void deleteExtraSpace(string &s){
        int now=0;
        for(int i=0;i<s.size();i++){
            if(s[i]!=' '){

                //不是第一个单词 要添加空格
                if(now!=0){
                    s[now++]=' ';
                }
                while(i<s.size()&&s[i]!=' '){
                    s[now++]=s[i++];
                }
            }
        }
        
        s.resize(now);
    }

    void swapp(string &s,int l,int r){
        while(l<r){
            swap(s[l],s[r]);
            l++,r--;
        }
    }
    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

剑指 Offer 58 - II. 左旋转字符串（O(1)的空间复杂度的方法）

剑指 Offer 58 - II. 左旋转字符串

题解：

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        reverse(s.begin(),s.begin()+n);
        reverse(s.begin()+n,s.end());
        reverse(s.begin(),s.end());
        return s;
    }
};
1
2
3
4
5
6
7
8
9

28. 实现 strStr()（KMP）

28. 实现 strStr()

参考：
代码随想录
帮你把KMP算法学个通透！（理论篇）
帮你把KMP算法学个通透！（求next数组代码篇）

i后缀末尾，j前缀末尾。

class Solution {
public:
    int strStr(string haystack, string needle) {
    if(needle=="") return 0;

    //next数组
    int next[needle.size()];
    getNext(next,needle);

    //进行匹配
    int j=0;//是短的串的指针
    for(int i=0;i<haystack.size();i++){
        while(j&&needle[j]!=haystack[i]) j=next[j-1];

        if(haystack[i]==needle[j]) j++;

        //完全匹配了
        if(j==needle.size()) return (i-j+1);
    }
    return -1;
    }

    void getNext(int *next,string s){
        //j 前缀末尾
        //i 后缀末尾
        int j=0;

        //初始化
        next[0]=0;

        //生成next数组
        for(int i=1;i<s.size();i++){

            //不匹配就回退
            while(j&&s[i]!=s[j]) j=next[j-1];

            //匹配
            if(s[i]==s[j]) j++;

            //更新next数组
            next[i]=j;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

459. 重复的子字符串（KMP，next数组的性质）

459. 重复的子字符串

参考：代码随想录

思维版：

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string ss=s+s;
        ss.erase(ss.begin());
        ss.erase(ss.end()-1);
        if(ss.find(s)!=-1) return true;
        else return false;
    }
};
1
2
3
4
5
6
7
8
9
10

KMP版：

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        
        int next[s.size()];
        getNext(s,next);

        int len=s.size();
        if(next[len-1]!=0&&len%(len-(next[len-1]))==0) return true;
        return false;
    }

    void getNext(string s,int *next){
        int j=0;
        next[0]=0;
        for(int i=1;i<s.size();i++){
            while(j&&s[i]!=s[j]) j=next[j-1];

            if(s[i]==s[j]) j++;

            next[i]=j;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

栈和队列

相关理论

看这里

232. 用栈实现队列（模拟）

232. 用栈实现队列

• 要有一个输入栈和输出栈
• 等输出栈空，再把输入栈的放进去（可自行模拟得出此结论）

class MyQueue {
public:
    //要有一个输入栈，一个输出栈
    stack<int>in;
    stack<int>out;

    MyQueue() {

    }
    
    void push(int x) {
        in.push(x);
    }
    
    int pop() {
        int ans= peek();       
        out.pop();
        return ans;
    }
    
    int peek() {
        //out空了之后才能把in中的放进去
        if(out.empty())
        {
            while(in.size()){
            out.push(in.top());
            in.pop();
            }
        }
        return out.top();
    }
    
    bool empty() {
        if(in.empty()&&out.empty()) return true;
        else return false;
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

225. 用队列实现栈（模拟+只用一个队列实现）

225. 用队列实现栈

• 如果用两个队列实现栈，那其实就是两个队列倒来倒去——使得其中一个队列只剩一个元素的时候，它就是栈顶
• 可以只用一个队列实现，详见代码

class MyStack {
public:
    MyStack() {

    }
    queue<int>q;
    void push(int x) {
        q.push(x);
    }
    
    int pop() {    
        int num=q.size()-1;
        while(num--){
            q.push(q.front());
            q.pop();
        }
        int ans=q.front();
        q.pop();
        return ans;
    }
    
    int top() {
        return q.back();
    }
    
    bool empty() {
        return q.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

150.逆波兰表达式求值（经典）

string转成int可以用stoi()

150.逆波兰表达式求值

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        //遇到数字入栈，遇到运算符则取两个栈顶计算后入栈
        stack<int>st;
        for(string s:tokens){
            if(check(s)){
                //先出来的是除数 减数
                int num1,num2;
                num1=st.top();
                st.pop();
                num2=st.top();
                st.pop();

                // int ans=num2 num1
                int ans;
                if(s=="+") ans=num1+num2;
                else if(s=="-") ans=num2-num1;
                else if(s=="*") ans=num1*num2;
                else ans=num2/num1;

                st.push(ans);
            }else{
                st.push(toInt(s));//stoi也可以
            }
        }

        return st.top();
    }

    int toInt(string s){
        int num=0;
        int flag=1;
        for(char c:s){
            if(c=='-'){
                flag=-1;
            }else{
                num=num*10+c-'0';
            }
            
        }
        return flag*num;
    }

    bool check(string s){
        if(s=="+"||s=="-"||s=="*"||s=="/") return true;
        else return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

239. 滑动窗口最大值（单调队列+滑动窗口+双端队列实现）

239. 滑动窗口最大值

一道好题！
关于为什么以及如何实现单调队列：看这里

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int>ans;
        Myque que;
        //先放k个
        for(int i=0;i<k;i++){
            que.push(nums[i]);
        }

        ans.push_back(que.front());

        //滑动
        for(int i=k;i<nums.size();i++){
            que.pop(nums[i-k]);
            que.push(nums[i]);
            ans.push_back(que.front());
        }

        return ans;
    }

    //单调队列+滑动窗口
    //维护一个队列，其中只能是递减的，则队头是最大的
    class Myque{
        public:
        deque<int>que;

        //pop 想要弹出某个值，那么要求这个值在队列中且在队头才能弹出
        void pop(int num){
            if(que.size()&&que.front()==num){
                que.pop_front();
            }
        }

        //push 想要加入值，且要求递减，则必须要求队列中末尾的值大于新加入的值
        void push(int num){
            while(que.size()&&que.back()<num){//这里不能等于！
                que.pop_back();
            }
            que.push_back(num);
        }

        //front 获取队头
        int front(){
            return que.front();
        }
    };
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

347. 前 K 个高频元素（小顶堆+map）

347. 前 K 个高频元素

• 用map统计频率
• 用小顶堆来维护频率最大的k个元素：按频率来排序，则小的在上
• 维护一个大小为k的堆，当堆大小超出k时，弹出的是频率小的元素
• 堆的cmp是快排的cmp相反：cmp的l>r是从大到小，而堆的l>r是小的在上
• 注意：类中要写public，否则默认private

参考

class Solution {
public:

    //优先队列的排序方式：与快排的cmp相反
    //我们要的是小顶堆
    class cmp{
        public:
        bool operator()(const pair<int,int>&lhs,const pair<int,int>&rhs){
            return lhs.second>rhs.second;//排的是出现的次数，也就是second
        }
    };

    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int>mp;
        for(int num:nums){
            mp[num]++;
        }

        priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> pq;

        //把mp放进小顶堆
        unordered_map<int,int>::iterator it;
        for(it=mp.begin();it!=mp.end();it++){
            pq.push(*it);
            if(pq.size()>k) pq.pop();
        }

        //k个空间
        vector<int>ans(k);

        //小顶堆，小的在前，所以要反向遍历
        for(int i=0;i<k;i++){
            ans[k-i-1]=pq.top().first;
            pq.pop();
        }

        return ans;
    }

    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41