1、两数之和

借用hash表完成O(n)查找

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> hash;
        int n=nums.size();
        vector<int> res;
        for(int i=0;i<n;i++){
            int t=target-nums[i];
            if(hash.count(t)){
                res.push_back(hash[t]);
                res.push_back(i);
                break;
            }
            hash[nums[i]]=i;
        }
        return res;
    }
};

2、三数之和

保证i > j > k同时避免重复处理。
当num[i]==nums[i-1]时，num[i]处理完，num[i-1]就跳过(j同理)

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(),nums.end());
        int n=nums.size();
        for(int i=0;i<n;i++){
            if(i && nums[i-1]==nums[i]) continue;
            for(int j=i+1,k=n-1;j<k;j++){
                if(j-1>i && nums[j]==nums[j-1]) continue;
                //预先判断k的值
                while(k-1>j && nums[i]+nums[j]+nums[k-1]>=0) k--;
                if(nums[i]+nums[j]+nums[k]==0) res.push_back({nums[i],nums[j],nums[k]});
            }
        }
        return res;
    }
};

3、下一个排列

1、3、2找下一个2、1、3
我们先倒序寻找非上升子序列的头节点k，然后向后遍历第一个比它大的值。
交换二者值之后，翻转k之后的值

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int k=nums.size()-1;
        //倒叙寻找第一个非上升子序列k，遇到相同值向前移动例如511
        while(k>0 && nums[k-1]>=nums[k]) k--;
        if(k==0) reverse(nums.begin(),nums.end());
        else{
            int t=k;
            while(t<nums.size() && nums[t]>nums[k-1]) t++;
            swap(nums[k-1],nums[t-1]);
            reverse(nums.begin()+k,nums.end());
        }
    }
};

4、翻转链表

要求翻转left到right之间的链表
我们采用a、b、c三个一组翻转的方式进行操作

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode* dummmy=new ListNode(-1);
        dummmy->next=head;
        auto a=dummmy;
        for(int i=0;i<left-1;i++){
            a=a->next;
        }
        auto l=a;
        a=a->next;
        auto b=a->next;
        for(int i=0;i<right-left;i++){
            auto c=b->next;
            b->next=a;
            a=b,b=c;
        }
        l->next->next=b;
        l->next=a;
        return dummmy->next;
    }
};

5、最大数

给定vector求解最大的拼接方案
重写sort函数中的cmp排序方法

class Solution {
public:
    static bool cmp(const int &x,const int &y){
        return to_string(x)+to_string(y)>to_string(y)+to_string(x);
    }

    string largestNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end(),cmp);
        string res;
        for(int i=0;i<nums.size();i++){
            res+=to_string(nums[i]);
        }
        int k=0;
        while(k+1<nums.size() && res[k]=='0') k++;
        return res.substr(k);
    }
};

6、无重复字符的最长子串

使用hash表进行每个单词的计数，只要当前单词计数超过一个左端点就收缩

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char,int> hash;
        int res=0;
        for(int i=0,j=0;i<s.size();i++){
            char c=s[i];
            while(hash[c]>0) {
                hash[s[j]]--;
                j++;
            }
            res=max(res,i-j+1);
            hash[c]++;
        }
        return res;
    }
};

7、合并 K 个升序链表

使用堆来获取每次K个链表的最小值，这里需要对堆的排序进行重写
struct cmp内重载()
小根堆注意要return l1->val>l2->val

class Solution {
public:
    struct cmp{
        bool operator()(ListNode* l1,ListNode* l2){
            return l1->val>l2->val;
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*,vector<ListNode*>,cmp> heap;
        for(auto t:lists){
            if(t){
                heap.push(t);
            }
        }
        ListNode* dummy=new ListNode(-1);
        auto tail=dummy;
        while(heap.size()){
            auto t=heap.top();
            heap.pop();
            tail=tail->next=t;
            if(t->next) heap.push(t->next);
        }
        return dummy->next;
    }
};

8、滑动窗口最大值

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        deque<int> q;
        for(int i=0;i<nums.size();i++){
            if(q.size() && i-k+1>q.front()) q.pop_front();
            while(q.size() && nums[i]>=nums[q.back()]) q.pop_back();
            q.push_back(i);
            if(i+1>=k) res.push_back(nums[q.front()]);
        }
        return res;
    }
};

9、最长回文子串 && 最长回文子序列

最长回文子串

遍历每个位置当作子串的中心点来展开，获取最大值

class Solution {
public:
    string longestPalindrome(string s) {
        string res;
        for(int i=0;i<s.size();i++){
            int l=i-1,r=i+1;
            while(l>=0 && r<s.size() && s[l]==s[r]) l--,r++;
            if(res.size()<r-l-1) res=s.substr(l+1,r-l-1);

            l=i,r=i+1;
            while(l>=0 && r<s.size() && s[l]==s[r]) l--,r++;
            if(res.size()<r-l-1) res=s.substr(l+1,r-l-1);
        }
        return res;
    }
};

最长回文子序列

由于子序列的不连续性，因此本题用dp来做，状态$f[i][j]$表示从i到j内最长回文子序列长度。状态转移分为四类：
1、含i也含j（要求s[i]==s[j]）2、含i不含j 3、含j不含i 4、不含i、j
其中第四个可以被2和3包含

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n=s.size();
        vector<vector<int>> f(n,vector<int>(n,0));
        for(int len=1;len<=n;len++){
            for(int i=0;i+len-1<n;i++){
                int j=i+len-1;
                if(i==j) f[i][j]=1;
                else{
                    if(s[i]==s[j]) f[i][j]=max(f[i+1][j-1]+2,f[i][j]);
                    f[i][j]=max(max(f[i][j-1],f[i+1][j]),f[i][j]);
                }
            }
        }
        return f[0][n-1];
    }
};

10、盛最多水的容器

class Solution {
public:
    int maxArea(vector<int>& height) {
        int res=0;
        int i=0,j=height.size()-1;
        while(i<j){
            res=max(res,(j-i)*min(height[i],height[j]));
            if(height[i]<height[j]) i++;
            else j--;
        }
        return res;
    }
};

11、从前序与中序遍历序列构造二叉树

class Solution {
public:
    unordered_map<int,int> hash;

    TreeNode* build(vector<int>& preorder,vector<int>& inorder,int pl,int pr,int il,int ir){
        if(pl>pr) return nullptr;
        int pos=hash[preorder[pl]];
        TreeNode* root=new TreeNode(preorder[pl]);
        root->left=build(preorder,inorder,pl+1,pl-il+pos,il,pos-1);
        root->right=build(preorder,inorder,pl-il+pos+1,pr,pos+1,ir);
        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for(int i=0;i<inorder.size();i++){
            hash[inorder[i]]=i;
        }
        return build(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1);
    }
};

12、编辑距离

$f[i][j]$表示word1的前i位和word2的前j位匹配所要操作的最小次数
这里我们有“增删改”三种变换方式，在状态转移时都要用到

class Solution {
public:
    int minDistance(string word1, string word2) {
        //添加空格表示前0位匹配
        word1=' '+word1,word2=' '+word2;
        int n1=word1.size(),n2=word2.size();
        vector<vector<int>> f(n1,vector<int>(n2,1e8));

        //特殊初始化边界
        for(int i=0;i<n1;i++) f[i][0]=i;
        for(int j=0;j<n2;j++) f[0][j]=j;

        for(int i=1;i<n1;i++){
            for(int j=1;j<n2;j++){
                //增删
                f[i][j]=min(f[i-1][j],f[i][j-1])+1;
                //相等不加次数，否则还是要加1
                if(word1[i]==word2[j]){
                    f[i][j]=min(f[i][j],f[i-1][j-1]);
                }else{
                    //改别忘了
                    f[i][j]=min(f[i][j],f[i-1][j-1]+1);
                }
            }
        }

        return f[n1-1][n2-1];
    }
};

13、最大子数组和

这里是简化版，原问题其实是一道dp问题，f[ i ]表示前i个数组的最大子数组，因此有f[ i ] = max(f[ i - 1 ] , 0) + nums[i]

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int i,j;
        int res=INT_MIN;
        for(i=0,j=0;i<nums.size();i++){
            j=max(j,0);
            j+=nums[i];
            res=max(j,res);
        }
        return res;
    }
};

14、颜色分类

位置关系：j < i < k
j左侧全是0，k右侧全是1

class Solution {
public:
    void sortColors(vector<int>& nums) {
        for(int i=0,j=0,k=nums.size()-1;i<=k;){
            if(nums[i]==0) swap(nums[i++],nums[j++]);
            else if(nums[i]==2) swap(nums[i],nums[k--]);
            else i++;
        }
    }
};

15、KMP匹配

注意点1：两个字符串下标从1开始
注意点2：待匹配串（长串）下标从1开始

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5+10,M = 1e6+10;

int ne[N];
int n1,n2;
char s1[N],s2[M];

int main(){
    cin>>n1>>s1+1>>n2>>s2+1;

    for(int i=2,j=0;i<=n1;i++){
        while(j && s1[j+1]!=s1[i]) j=ne[j];
        if(s1[i]==s1[j+1]) j++;
        ne[i]=j;
    }

    for(int i=1,j=0;i<=n2;i++){
        while(j && s1[j+1]!=s2[i]) j=ne[j];
        if(s1[j+1]==s2[i]) j++;
        if(j==n1){
            cout<<i-n1<<" ";
            j=ne[j];
        }
    }
    return 0;
}

16、括号生成

有效的括号序列：任意前缀左括号个数>右括号个数

class Solution {
public:
    vector<string> res;
    string s;

    void dfs(int n,int l,int r){
        if(l+r==2*n && l==r){
            res.push_back(s);
            return;
        }
        if(l>n || r>n) return;

        //左括号随时可压入
        s+="(";
        dfs(n,l+1,r);
        s.pop_back();

        //右括号仅在有左括号时可压入 
        if(l>r) {
            s+=")";
            dfs(n,l,r+1);
            s.pop_back();   
        }
    }

    vector<string> generateParenthesis(int n) {
        dfs(n,0,0);
        return res;
    }
};

17、LRU 缓存

本题首先要明确，我们使用链表的结构去实现LRU的原理。因此我们声明了Node作为双链表的节点，用于insert和pop操作
对于get和put都要O(1)时间内完成，因此想到了hash表。由于我们get和put都以key为基础进行操作，因此first为key，second就为对应Node节点

class LRUCache {
public:
    struct Node{
        int key,value;
        Node *left,*right;
        Node(int k,int v){
            key=k,value=v;
            left=NULL;
            right=NULL;
        }
    };
    Node *L,*R;
    int n;
    unordered_map<int,Node*> hash;

    //清除p节点
    void pop(Node* p){
        p->left->right=p->right;
        p->right->left=p->left;
    }

    //往表头添加p节点
    void insert(Node* p){
        p->right=L->right;
        p->left=L;
        L->right->left=p;
        L->right=p;
    }

    LRUCache(int capacity) {
        n=capacity;
        L=new Node(-1,-1),R=new Node(-1,-1);
        //双链表初始化
        L->right=R;
        R->left=L;
    }

    int get(int key) {
        if(hash.count(key)){
            auto t=hash[key];
            pop(t);
            insert(t);
            return t->value;
        }
        return -1;
    }

    void put(int key, int value) {
        if(hash.count(key)){
            auto t=hash[key];
            t->value=value;
            pop(t);
            insert(t);
        }else{
            if(hash.size()==n){
                auto p=R->left;
                pop(p);
                //记得在hash表中擦除
                hash.erase(p->key);
            }
            auto t=new Node(key,value);
            hash[key]=t;
            insert(t);
        }
    }
};

18、寻找峰值

本题实际山是二分的应用，我们每次枚举出mid点，当mid比其右侧元素大，则mid就作为一种可能结果，r=mid搜索左半边；反之mid小于右侧元素去右侧找

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l=0,r=nums.size()-1;
        while(l<r){
            int mid=l+r>>1;
            //等号跟谁并不重要
            if(nums[mid]>=nums[mid+1]) r=mid;
            else l=mid+1;
        }
        return r;
    }
};

19、接雨水

本题核心思路——单调栈
分析案例可知，我们每当当前元素大于前一个元素，那么就存在有凹槽累计雨水的可能。此时我们获取前前一个元素(如果有的话)，计算二者高度最小值并与前一个元素高度做差，乘以宽度计算雨水累积值(即使为负数也没关系，后面会填平)

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> stk;
        int res=0;
        for(int i=0;i<height.size();i++){
            while(stk.size() && height[stk.top()]<=height[i]){
                auto top=stk.top();
                stk.pop();
                if(stk.empty()) break;
                res+=(i-stk.top()-1)*(min(height[i],height[stk.top()])-height[top]);
            }
            stk.push(i);
        }
        return res;
    }
};

20、复原ip地址

本题是一道dfs问题，关键点在于枚举出所有可能情况。传入两个数值参数，u表示走到第几位，k表示累积了几位有效位
精髓在于dfs最后的for循环，我们要从当前位置u开始向后遍历所有可能情况，同时要满足：1、没有前导0；2、数值不超过255

class Solution {
public:
    vector<string> res;

    vector<string> restoreIpAddresses(string s) {
        dfs(0,0,s,"");
        return res;
    }

    void dfs(int u,int k,string s,string path){
        if(u==s.size()){
            if(k==4){
                path.pop_back();
                res.push_back(path);
                return;
            }
        }
        if(k==4) return ;

        for(int i=u;i<s.size();i++){
            //去除前导0
            if(i>u && s[u]=='0') continue;
            int t=stoi(s.substr(u,i-u+1));
            if(t<=255) dfs(i+1,k+1,s,path+to_string(t)+'.');
            else break;
        }
    }
};

21、字符串解码

这里与20题有一丝相近，但是与常规dfs又有些许不同
本题子dfs都是为主dfs服务的，我们在主dfs中不断调用子dfs解码字符串

class Solution {
public:
    string decodeString(string s) {
        int u=0;
        return dfs(u,s);
    }

    string dfs(int &u,string s){
        string res;
        while(u<s.size() && s[u]!=']'){
            //注意这里是if，else判断流程
            if(s[u]>='a' && s[u]<='z') res+=s[u++];
            else{
                int k=u;
                while(s[u]>='0' && s[u]<='9') u++;
                int x=stoi(s.substr(k,u-k+1));
                u++;
                string r=dfs(u,s);
                u++;
                while(x--) res+=r;
            }
        }
        return res;
    }
};

22、组合总数

无重复元素，因此直接dfs即可
这里dfs和以前的全排列等问题不同，不是靠循环推动结果的累计，而是通过dfs的不断调用，每次枚举我能拿多少个当前元素然后向后走

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates,target,0);
        return res;
    }

    void dfs(vector<int>& candidates,int target,int u){
        if(target==0){
            res.push_back(path);
            return ;
        }
        if(u==candidates.size()) return;
        //有点类似背包问题
        for(int k=0;k*candidates[u]<=target;k++){
            for(int j=0;j<k;j++) path.push_back(candidates[u]);
            dfs(candidates,target-candidates[u]*k,u+1);
            for(int j=0;j<k;j++) path.pop_back();
        } 
    }
};

23、组合总数II

本题与22题最大的区别就是存在重复元素，且每个元素只能用一次
因此我们在进行dfs之前要对元素进行排序，且在dfs时要跳过相同元素

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        dfs(candidates,target,0);
        return res;
    }

    void dfs(vector<int>& candidates,int target,int u){
        if(target==0){
            res.push_back(path);
            return ;
        }
        if(u==candidates.size()) return;
        int k=u;
        while(k<candidates.size() && candidates[k]==candidates[u]) k++;
        for(int t=0;t<=k-u;t++){
            if(candidates[u]*t<=target){
                for(int i=0;i<t;i++) path.push_back(candidates[u]);
                dfs(candidates,target-t*candidates[u],k);
                for(int i=0;i<t;i++) path.pop_back();
            }
        }
    }
};

24、二叉搜索树的最近公共祖先 && 二叉树的最近公共祖先

二叉搜索树

通过有序这一关键性质，当root可以把p和q分到两个子树中时，就找到了公共祖先（p和q也有可能是root，因此带上等号）

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(p->val>q->val) swap(p,q);
        if(p->val<root->val && q->val<root->val) return lowestCommonAncestor(root->left,p,q);
        if(p->val<=root->val && q->val>=root->val) return root;
        return lowestCommonAncestor(root->right,p,q);
    }
};

普通二叉树

借用dfs来寻找既包括p右包括q的节点，这里使用返回值来表示“包括”这一概念，含左节点为1，含右节点为2，两个都含就变成了3

class Solution {
public:
    TreeNode* res=nullptr;

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root,p,q);
        return res;
    }

    int dfs(TreeNode* root,TreeNode* p,TreeNode* q){
        int status=0;
        if(root->left) status|=dfs(root->left,p,q);
        if(root->right) status|=dfs(root->right,p,q);
        if(root==p) status|=1;
        if(root==q) status|=2;
        if(status==3 && res==nullptr) res=root;
        return status;
    }
};