当前位置：首页 > news >正文

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

news 来源：原创 2024/5/3 16:31:46

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

- 链表相关
- 双指针
- 滑动窗口
- - 209. 长度最小的子数组（滑动窗口）
  - 904. 水果成篮（滑动窗口+哈希）
- 模拟相关
- - 59. 螺旋矩阵 II
- 哈希表
- - 哈希表概述
  - 1. 两数之和（哈希表）
  - 454. 四数相加 II（哈希表）
- 字符串
- - 剑指 Offer 05. 替换空格（O(1)的空间复杂度的方法）
  - 151. 颠倒字符串中的单词（O(1)的空间复杂度的方法）
  - 剑指 Offer 58 - II. 左旋转字符串（O(1)的空间复杂度的方法）
  - 28. 实现 strStr()（KMP）
  - 459. 重复的子字符串（KMP，next数组的性质）
- 栈和队列
- - 相关理论
  - 232. 用栈实现队列（模拟）
  - 225. 用队列实现栈（模拟+只用一个队列实现）

链表相关

单独总结了，这里不再赘述：【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;
    }
};

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;
    }
};

模拟相关

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<<i<<" "<<j<<" "<<now<<endl;
            a[i][j+1]=now++;
            j++;
        }
        if(now>n*n) break;
        //下
        while(i+1<n&&!a[i+1][j]&&now<=n*n) 
        {
            // cout<<i<<" "<<j<<" "<<now<<endl;
            a[i+1][j]=now++;
            i++;
        }
        if(now>n*n) break;
        //左
        while(j>0&&!a[i][j-1]&&now<=n*n)
        {
            // cout<<i<<" "<<j<<" "<<now<<endl;
            a[i][j-1]=now++;
            j--;
        }
        if(now>n*n) break;
        //上
        while(i>0&&!a[i-1][j]&&now<=n*n)
        {
            // cout<<i<<" "<<j<<" "<<now<<endl;
            a[i-1][j]=now++;
            i--;
        }
        if(now>n*n) break;
    }
    return a;
    }
};

哈希表

哈希表概述

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

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

在这里插入图片描述

当我们要使用集合来解决哈希问题的时候，优先使用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 {};
    }
};

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;
    }
};

字符串

剑指 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;
    }
};

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--;
        }
    }
    
};

剑指 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;
    }
};

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;
        }
    }
};

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;
    }
};

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;
        }
    }
};

栈和队列

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();
 */

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();
 */