二叉树

1. 101. 对称二叉树

  1. class Solution {
  2. public:
  3.     bool isSymmetric(TreeNode* root) {
  4.         return check(root,root);
  5.     }
  6.     //从根开始设两个指针，分别往左右子树走
  7.     // 比较左的左子与右的右子，左的右子与右的左子
  8.     bool check(TreeNode* node1,TreeNode* node2){
  9.         if(!node1&&!node2) return true;
  10.         if(!node1||!node2) return false;
  11.         return (node1->val)==(node2->val)&&check(node1->left,node2->right)&&check(node1->right,node2->left);
  12.     }
  13. };

时间O(N) ，空间O(N)，栈的使用

  1. class Solution {
  2. public:
  3.     bool isSymmetric(TreeNode* root) {
  4.         return check(root,root);
  5.     }
  6.     //从根开始设两个指针，分别往左右子树走
  7.     bool check(TreeNode* node1,TreeNode* node2){
  8.         stack<TreeNode*> st;
  9.         st.push(node1);
  10.         st.push(node2);
  12.         while(!st.empty()){
  13.             //连续取出两个比较
  14.             node1=st.top();
  15.             st.pop();
  16.             node2=st.top();;
  17.             st.pop();
  19.             if(!node1&&!node2) continue;
  20.             if(!node1||!node2) return false;
  21.             if(node1->val!=node2->val) return false;
  23.             //左的左子与右的右子 推入栈等待比较
  24.             st.push(node1->left);
  25.             st.push(node2->right);
  27.             //左的右子与右的左子 推入栈等待比较
  28.             st.push(node1->right);
  29.             st.push(node2->left);
  30.         }
  32.         return true;
  33.     }
  34. };

时间O(N) ，空间O(N)，栈的使用

2. 617. 合并二叉树

  1. class Solution {
  2. public:
  3.     TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
  4.         if(!root1&&!root2) return NULL;
  5.         if(!root1||!root2) return root1==NULL?root2:root1;
  7.         //cpy ctr 
  8.         TreeNode* root=new TreeNode(root1->val+root2->val);
  9.         root->left=mergeTrees(root1->left,root2->left);
  10.         root->right=mergeTrees(root1->right,root2->right);
  12.         return root;
  13.     }
  14. };

时间复杂度O(min(m,n))，空间复杂度O(min(m,n))

  1. class Solution {
  2. public:
  3.     TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
  4.         if(!root1&&!root2) return NULL;
  5.         if(!root1||!root2) return root1==NULL?root2:root1;
  7.         //cpy ctr 
  8.         TreeNode* root=new TreeNode(root1->val+root2->val);
  10.         //队列，先进先出，保存访问节点，依次访问
  11.         queue<TreeNode*> q1,q2,q;
  12.         q1.push(root1);
  13.         q2.push(root2);
  14.         q.push(root);
  16.         while(!q1.empty()&&!q2.empty()){
  17.             TreeNode *node=q.front(); q.pop();
  18.             TreeNode *node1=q1.front(); q1.pop();
  19.             TreeNode *node2=q2.front(); q2.pop();
  21.             if(node1->left!=NULL && node2->left!=NULL){
  22.                 TreeNode *left=new TreeNode(node1->left->val+node2->left->val);
  23.                 node->left=left;  
  24.                 q.push(left);
  25.                 q1.push(node1->left);
  26.                 q2.push(node2->left);
  27.             }else if(node1->left!=NULL){  //q2左子=NULL,把q1左子作为左子
  28.                 node->left=node1->left;  
  29.             }else if(node2->left!=NULL){  //q1左子=NULL,把q2左子作为左子
  30.                 node->left=node2->left;
  31.             } 
  33.             if(node1->right!=NULL && node2->right!=NULL){
  34.                 TreeNode *right=new TreeNode(node1->right->val+node2->right->val);
  35.                 node->right=right;
  36.                 q.push(right);
  37.                 q1.push(node1->right);
  38.                 q2.push(node2->right);
  39.             }else if(node1->right!=NULL){  //q2右子=NULL,把q1右子作为右子
  40.                 node->right=node1->right;
  41.             }else if(node2->right!=NULL){  //q1右子=NULL,把q2右子作为右子
  42.                 node->right=node2->right;
  43.             } 
  44.         }
  46.         return root;
  47.     }
  48. };

时间复杂度O(min(m,n))，空间复杂度O(min(m,n))

3. 96. 不同的二叉搜索树

  1. class Solution {
  2. public:
  3.     int numTrees(int n) {
  4.         return count(1,n);
  5.     }
  7.     int count(int low,int high){
  8.         if(low>high) return 1;
  9.         int result=0;
  10.         //i值作为根节点，左子树有[low,i-1],右子树[i+1,high];
  11.         for(int i=low;i<=high;i++){
  12.             int left=count(low,i-1);
  13.             int right=count(i+1,high);
  14.             result+=left*right;
  15.         }
  16.         return result;
  17.     }
  18. };
  1. class Solution {
  2. public:
  3.     vector<vector<int>> memo;
  4.     int numTrees(int n) {
  5.         memo.resize(n+1,vector<int>(n+1,0));
  6.         return count(1,n);
  7.     }
  9.     int count(int low,int high){
  10.         if(low>high) return 1;
  11.         if(memo[low][high]!=0){
  12.             return memo[low][high];
  13.         }
  14.         int result=0;
  15.         //i值作为根节点，左子树有[low,i-1],右子树[i+1,high];
  16.         for(int i=low;i<=high;i++){
  17.             int left=count(low,i-1);
  18.             int right=count(i+1,high);
  19.             result+=left*right;
  20.         }
  21.         memo[low][high]=result;
  22.         return result;
  23.     }
  24. };
  1. class Solution {
  2. public:
  3.     int numTrees(int n) {
  4.         if(n<=2){
  5.             return n;
  6.         }
  7.         //base  dp[i]代表 BST中i个节点可组成的种数
  8.         vector<int> dp(n+1,0);
  10.         //edge
  11.         dp[0]=1;
  12.         dp[1]=1;
  13.         dp[2]=2;
  15.         //relation
  16.         for(int i=3;i<=n;i++){
  17.             for(int j=1;j<=i;j++){  //根的位置 从第一个开始取
  18.                 // 根左边的num*右边的num
  19.                 dp[i]+=(dp[j-1]*dp[i-j]);  
  20.             }
  21.         }
  22.         return dp[n];
  23.     }
  24. };

4. 98. 验证二叉搜索树

  1. class Solution {
  2. public:
  3.     bool isValidBST(TreeNode* root) {
  4.         return helper(root,LONG_MIN,LONG_MAX);
  5.     }
  7.     // 左子树都小于 根，右子树都大于
  8.     bool helper(TreeNode* root,long long m_min,long long m_max){
  9.         if(root==NULL) return true;
  10.         if(root->val<=m_min||root->val>=m_max) return false;
  12.         return helper(root->left,m_min,root->val) && helper(root->right,root->val,m_max);
  13.     }
  14. };
  1. class Solution {
  2. public:
  3.     bool isValidBST(TreeNode* root) {
  4.         if(root==NULL) return true;
  5.         stack<TreeNode*> st;
  6.         TreeNode *cur=root;
  7.         TreeNode *pre=NULL;
  8.         while(cur!=NULL||!st.empty()){
  9.             if(cur!=NULL){
  10.                 st.push(cur);  //root推入栈等待访问
  11.                 cur=cur->left;   //先访问左
  12.             }else{
  13.                 cur=st.top();   //开始访问
  14.                 st.pop();
  15.                 if(pre!=NULL&&pre->val>=cur->val){   //比较次序
  16.                     return false;
  17.                 }
  19.                 pre=cur;  //更新pre 和cur
  20.                 cur=cur->right;  //看右子
  21.             }
  22.         }
  23.         return true;
  24.     }    
  25. };
  1. class Solution {
  2. public:
  3.     //中序遍历后 看是不是从小到大
  4.     vector<int> res;
  5.     bool isValidBST(TreeNode* root) {
  6.         res.clear();
  7.         traverse(root);
  8.         for(int i=1;i<res.size();i++){
  9.             if(res[i]<=res[i-1]) return false;
  10.         }
  11.         return true;
  12.     }
  14.     void traverse(TreeNode *root){
  15.         if(root==NULL) return ;
  16.         traverse(root->left);
  17.         res.push_back(root->val);
  18.         traverse(root->right);
  19.     }
  20. };

5. 236. 二叉树的最近公共祖先

  1. class Solution {
  2. public:
  3.     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
  4.         if(root==NULL) return NULL;
  5.         if(root==p||root==q) return root;
  7.         //在左子树找 ，递归 ，  用函数后可认为左右子树已经算出结果
  8.         TreeNode* left=lowestCommonAncestor(root->left,p,q);
  9.         //在左子树找
  10.         TreeNode* right=lowestCommonAncestor(root->right,p,q);
  12.         //左子树没找到，看右子树
  13.         if(left==NULL) return right;
  14.         //右子树没找到，看左子树
  15.         if(right==NULL) return left;
  16.         //都找到了，LCA为root
  17.         if(left&&right) return root;
  19.         return NULL;
  20.     }
  21. };

时间复杂度是 O(n)O(n)：每个结点最多遍历一次或用主定理，空间复杂度是 O(n)O(n)：需要系统栈空间

6.124. 二叉树中的最大路径和

  1. class Solution {
  2. public:
  3.     int result=INT_MIN;
  4.     int maxPathSum(TreeNode* root) {
  5.         maxPath(root);
  6.         return result;
  7.     }
  9.     int maxPath(TreeNode* root){
  10.         if(root==NULL) return 0;
  12.         int left=max(maxPath(root->left),0);
  13.         int right=max(maxPath(root->right),0);
  14.         //与 记录的最大值 比较
  15.         result=max(result,left+right+root->val);
  16.         //往左边 还是右边继续计算
  17.         return max(left+root->val,right+root->val);
  18.     }
  19. };

7. 297. 二叉树的序列化与反序列化

  1. class Codec {
  2. public:
  3.     string SEP=",";
  4.     string NO="NONE";
  5.     // Encodes a tree to a single string.
  6.     string serialize(TreeNode* root) {
  7.         if(!root) return NO;
  8.         string left=serialize(root->left);
  9.         string right=serialize(root->right);
  10.         //前序
  11.         return to_string(root->val)+SEP+left+SEP+right;
  12.     }
  14.     // Decodes your encoded data to tree.
  15.     TreeNode* deserialize(string data) {
  16.         list<string> dataList;
  17.         string str;
  18.         for(char &c:data){
  19.             if(c==','){
  20.                 dataList.push_back(str);
  21.                 str.clear();
  22.             }else{
  23.                 str.push_back(c);
  24.             }
  25.         }
  26.         if(!str.empty()){
  27.             dataList.push_back(str);
  28.             str.clear();
  29.         }
  30.         return helper(dataList);
  31.     }
  33.     TreeNode* helper(list<string>& dataList){
  34.         //dataList存储着所有节点，前序的
  35.         string str=dataList.front();
  36.         if(str=="NONE"){
  37.             dataList.pop_front();
  38.             return NULL;
  39.         }
  40.         TreeNode* root=new TreeNode(stoi(str));
  41.         dataList.pop_front();
  42.         root->left=helper(dataList);
  43.         root->right=helper(dataList);
  44.         return root;
  45.     }
  46. };

8. 437. 路径总和 III

  1. class Solution {
  2. public:
  3.     //穷举法：递归遍历每一个节点的所有可能的路径，然后将这些路径数目加起来即为返回结果。
  4.     //超时
  5.     int pathSum(TreeNode* root, int targetSum) {
  6.         if(!root){
  7.             return 0;
  8.         }
  9.         //根的种数、左子树种数和右子树种数
  10.         int res=nodeSum(root,targetSum);
  11.         res+=pathSum(root->left,targetSum);
  12.         res+=pathSum(root->right,targetSum);
  13.         return res;
  14.     }
  15.     int nodeSum(TreeNode* node,int targetSum){
  16.         if(!node){
  17.             return 0;
  18.         }
  19.         int res=0;
  20.         if(node->val==targetSum){
  21.             res++;
  22.         }
  23.         //递归求得左、右子树的路径数
  24.         res+=nodeSum(node->left,targetSum-node->val);
  25.         res+=nodeSum(node->right,targetSum-node->val);
  26.         return res;
  27.     }
  28. };
  1. class Solution {
  2. public:
  3.     //存下来--->前缀和 (sum,count) 深度优先遍历
  4.     unordered_map<long long,int> prefix;
  5.     int pathSum(TreeNode* root, int targetSum) {
  6.         prefix[0]=1;
  7.         return dfs(root,0,targetSum);
  8.     }
  9.     //注意curSum是long long类型
  10.     int dfs(TreeNode* root,long long curSum,int targetSum){
  11.         if(!root){
  12.             return 0;
  13.         }
  14.         curSum+=root->val;
  15.         int res=0;
  16.         //当前节点前缀和为curSum，在已保存的前缀中查找是否有curSum-targetSum的 从此节点到当前节点的路有几条
  17.         if(prefix.count(curSum-targetSum)){
  18.             res=prefix[curSum-targetSum];
  19.         }
  20.         //更新前缀和
  21.         prefix[curSum]++;
  22.         //左子树符合条件的
  23.         res+=dfs(root->left,curSum,targetSum);
  24.         //右子树符合条件的
  25.         res+=dfs(root->right,curSum,targetSum);
  26.         prefix[curSum]--;
  28.         return res;
  29.     }
  30. };
class Solution {
public:
    //深度优先遍历，从上到下计算和
    int res=0;
    int pathSum(TreeNode* root, int targetSum) {
        if(!root){
            return 0;
        }
        dfs1(root,targetSum);
        return res;
    }
    //往左子右子走
    void dfs1(TreeNode* root,int targetSum){
        if(!root) return ;
        dfs2(root,root->val,targetSum);
        dfs1(root->left,targetSum);
        dfs1(root->right,targetSum);
    }
    //计算本节点是否满足
    void dfs2(TreeNode* root,long long val,int targetSum){
        if(targetSum==val){
            res++;
        }
        if(root->left){
            dfs2(root->left,val+root->left->val,targetSum);
        }
        if(root->right){
            dfs2(root->right,val+root->right->val,targetSum);
        }
    }

};

数学方法

1. 7. 整数反转

关键在于溢出判断，result*10+digit可能溢出，要在范围之内。

class Solution {
public:
    //数学方法：依次取出个十百...计算
    int reverse(int x) {
        int result=0;
        while(x!=0){
            //结果超出界限时返回0
            // result*10+digit要在范围之内
            if(result<INT_MIN/10||result>INT_MAX/10){
                return 0;
            }
            int digit=x%10;
            x/=10;
            result=result*10+digit;
        }
        return result;
    }
};

2. 136. 只出现一次的数字

哈希表

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int,int> map;
        for(int &num:nums){
            map[num]++;
        }
        for(int &num:nums){
            if(map[num]==1){
                return num;
            }
        }
        return 0;
    }
};

按位异或
异或运算有以下三个性质。

  • 任何数和 0 做异或运算，结果仍然是原来的数。
  • 任何数和其自身做异或运算，结果是 0。
  • 异或运算满足交换律和结合律。

经过两次异或，number变为0；

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result=0;
        for(int &num:nums){
            result^=num;
        }
        return result;
    }
};

3. 66. 加一

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int n=digits.size();
        for(int i=n-1;i>=0;i--){
            //找到第一个9，倒着找
            if(digits[i]!=9){
                digits[i]++;
                for(int j=i+1;j<n;j++){
                    digits[j]=0;
                }
                return digits;
            }
        }
        //全是9
        vector<int> ans(n+1,0);
        ans[0]=1;
        return ans;
    }
};

4. 128. 最长连续序列

class Solution {
public:
    //枚举法
    //找每个元素x 的+1、+2、+3看是否存在
    //放入hash表中,将O(n)--->O(n)
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> num_set;
        for(const int &num:nums){
            num_set.insert(num);
        }
        int res=0;

        for(const int &num:nums){
            //
            if(!num_set.count(num-1)){
                int y=num;
                while(num_set.count(y+1)){
                    y++;
                }
                res=max(res,y-num+1);
            }
        }
        return res;
    }
};

//动态规划：先排序，然后找
//并查集：待补充

5. 406. 根据身高重建队列

class Solution {
public:
    //根据第一个元素降序，第二个元素升序排列
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(),people.end(),[](const vector<int>& u,const vector<int>& v){
            return u[0]>v[0] || (u[0]==v[0]&&u[1]<v[1]);
        });
        //依次插入队列，根据第二元素
        vector<vector<int>> res;
        for(const vector<int>& v:people){
            res.insert(res.begin()+v[1],v);
        }
        return res;
    }
};

6. 461. 汉明距离

除数法

class Solution {
public:
    //均除以2 看余数是否相等 
    int hammingDistance(int x, int y) {
        int dis=0;
        while(x>1||y>1){
            if(x%2!=y%2){
                dis++;
            }
            x/=2;
            y/=2;
        }
        //剩下的一位数 也要看是否相等
        if(x!=y) dis++;
        return dis;
    }
};

内置函数

class Solution {
public:
    // 内置函数：计算二进制表达中 1 的数量
    int hammingDistance(int x, int y) {
        return __builtin_popcount(x^y);
    }
};
  • 时间复杂度：O(1)
  • 空间复杂度：O(1)

移位计数

class Solution {
public:
    // 移位计数
    int hammingDistance(int x, int y) {
       int s=x^y,res=0;
       while(s!=0){
           res+=s&1;
           s=s>>1;
       }
       return res;
    }
};

Brian Kernighan 算法

class Solution {
public:
    // Brian Kernighan 算法:对任何一个数 n ，n & ( n − 1 ) 的结果是n的比特位最右端的1变为0的结果
    int hammingDistance(int x, int y) {
       int s=x^y,res=0;
       while(s){
           s=s&(s-1);
           res++;
       }
       return res;
    }
};

7. 23. 合并K个升序链表

class Solution {
public:
    //依次合并两个
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* res=nullptr;
        for(int i=0;i<lists.size();i++){
            res=mergeTwoLists(res,lists[i]);
        }
        return res;
    }
    ListNode* mergeTwoLists(ListNode* a,ListNode* b){
        if(!a||!b) return a?a:b;
        ListNode *aPtr=a,*bPtr=b;
        ListNode head;
        ListNode *newList=&head;

        while(aPtr && bPtr){
            if(aPtr->val<bPtr->val){
                newList->next=aPtr;
                aPtr=aPtr->next;
            }else{
                newList->next=bPtr;
                bPtr=bPtr->next;
            }
            newList=newList->next;
        }
        newList->next=aPtr?aPtr:bPtr;
        return head.next;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    //分治法选择 要合并的两个
    ListNode* mergeKLists(vector<ListNode*>& lists) {        
        return merge(lists,0,lists.size()-1);
    }
    ListNode* merge(vector<ListNode*> &lists,int l,int r){
        if(l>r) return nullptr;
        if(l==r) return lists[l];
        int mid=(l+r)>>1;
        return mergeTwoLists(merge(lists,l,mid),merge(lists,mid+1,r)); 
    }
    ListNode* mergeTwoLists(ListNode* a,ListNode* b){
        if(!a||!b) return a?a:b;
        ListNode *aPtr=a,*bPtr=b;
        ListNode head;
        ListNode *newList=&head;

        while(aPtr && bPtr){
            if(aPtr->val<bPtr->val){
                newList->next=aPtr;
                aPtr=aPtr->next;
            }else{
                newList->next=bPtr;
                bPtr=bPtr->next;
            }
            newList=newList->next;
        }
        newList->next=aPtr?aPtr:bPtr;
        return head.next;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    //优先级队列，取出每个链表的头节点放入队列中，自动排好序
    struct Status{
        int val;
        ListNode* ptr;
        bool operator < (const Status& s) const{
            return val>s.val;
        }
    };
    priority_queue<Status> q;
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        for(auto node:lists){
            if(node){
                q.push({node->val,node});
            }
        }

        ListNode head,*tail=&head;
        while(!q.empty()){
            auto f=q.top();
            q.pop();
            tail->next=f.ptr;
            tail=tail->next;
            if(f.ptr->next){
                q.push({f.ptr->next->val,f.ptr->next});
            }
        }
        return head.next;
    }
};

8. 31. 下一个排列

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        //找到要交换的位置 
        int i=nums.size()-2;
        while(i>=0&&nums[i]>=nums[i+1]){
            i--;
        }

        //从后往前找第一个满足 大于要交换的数，保证改动的幅度最小 
        if(i>=0){
            int j=nums.size()-1;
            while(j>=0&&nums[i]>=nums[j]){
                j--;
            }
            //交换
            swap(nums[i],nums[j]);
        }
        //保证后边升序，没有找到也升序排列
        reverse(nums.begin()+i+1,nums.end());
    }
};

9. 48. 旋转图像

直接翻转

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n=matrix.size();
        //水平翻转
        for(int i=0;i<n/2;i++){
            for(int j=0;j<n;j++){
                swap(matrix[i][j],matrix[n-1-i][j]);
            }
        }

        //主对角线翻转
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                swap(matrix[i][j],matrix[j][i]);
            }
        }

    }
};

10. 238. 除自身以外数组的乘积

class Solution {
public:    
    //L*R
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        vector<int> L(n,0),R(n,0);
        vector<int> res(n);

        L[0]=1;
        R[n-1]=1;
        for(int i=1;i<n;i++){
            L[i]=L[i-1]*nums[i-1];
        }
        for(int i=n-2;i>=0;i--){
            R[i]=R[i+1]*nums[i+1];
        }
        for(int i=0;i<n;i++){
            res[i]=L[i]*R[i];
        }
        return res;
    }
};

class Solution {
public:
    //L*R 空间压缩至O(1)
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        vector<int> res(n);

        res[0]=1;
        for(int i=1;i<n;i++){
            res[i]=res[i-1]*nums[i-1];
        }
        int R=1;
        for(int i=n-1;i>=0;i--){
            res[i]*=R;
            R*=nums[i];
        }
        return res;
    }
};

动态规划

1. 647. 回文子串

动态规划

class Solution {
public:
    int countSubstrings(string s) {
        int res=0;
        int n=s.length();

        //define dp[i][j] 表示 开始位置i，结束位置j 的字符串是不是回文
        vector<vector<bool>> dp(n,vector<bool>(n,false));

        //edge        

        //relation  
        for(int i=n-1;i>=0;i--){
            for(int j=i;j<n;j++){
                if(s[i]==s[j]){
                    if(j-i<=1){
                        res++;
                        dp[i][j]=true;
                    }else{
                        if(dp[i+1][j-1]){
                            res++;
                            dp[i][j]=true;
                        }
                    }
                }
            }
        }
        return res;
    }
};

2. 42. 接雨水

class Solution {
public:
    //暴力破解，找每一单元的存水量再相加。每一单元的...取决于其左边和右边最高。
    //超时
    int trap(vector<int>& height) {
        int n=height.size();
        if(n<3){
            return 0;
        }

        int res=0;
        for(int i=1;i<n-1;i++){
            int leftHigh=maxHeight(height,0,i-1);
            int rightHigh=maxHeight(height,i,n-1);

            //木桶原理，两者选小
            int curHeight=min(leftHigh,rightHigh);
            //减去原始高度
            if(curHeight>height[i]){
                res+=(curHeight-height[i]);
            }
        }
        return res;
    }

    int maxHeight(vector<int>& height,int left,int right){
        int res=height[left];
        for(int i=left+1;i<=right;i++){
            res=max(res,height[i]);
        }
        return res;
    }

};

class Solution {
public:
    //动态规划，找每一单元的存水量再相加。每一单元的...取决于其左边和右边最高。
    //通过dp来寻找 左右两端的最大值
    int trap(vector<int>& height) {
        int n=height.size();
        if(n<3){
            return 0;
        }

        vector<int> leftHigh(n),rightHigh(n);
        for(int i=1;i<n-1;i++){
            leftHigh[i]=max(leftHigh[i-1],height[i-1]);
        }
        for(int i=n-2;i>=0;i--){
            rightHigh[i]=max(rightHigh[i+1],height[i+1]);
        }

        int res=0;        
        for(int i=1;i<n-1;i++){
            //木桶原理，两者选小
            int curHeight=min(leftHigh[i],rightHigh[i]);
            //减去原始高度
            if(curHeight>height[i]){
                res+=(curHeight-height[i]);
            }
        }
        return res;
    }
};

class Solution {
public:
    //双指针，找每一单元的存水量再相加。每一单元的...取决于其左边和右边最高。
    int trap(vector<int>& height) {
        int n=height.size();
        if(n<3){
            return 0;
        }
        //遍历指针
        int left=1;
        int right=n-2;
        //记录左右区间的最大高度
        int leftHigh=height[0];
        int rightHigh=height[n-1];

        int res=0;
        while(left<=right){
            int minHeight=min(leftHigh,rightHigh);
            //存水体积取决于较小的高度
            if(minHeight==leftHigh){
                //大于才能存水
                if(minHeight>height[left]){
                    res+=(minHeight-height[left]);
                }
                //更新左边最大高度
                leftHigh=max(leftHigh,height[left]);
                left++;
            }else{
                //大于才能存水
                if(minHeight>height[right]){
                    res+=(minHeight-height[right]);
                }
                //更新右边最大高度
                rightHigh=max(rightHigh,height[right]);
                right--;
            }
        }
        return res;
    }
};

class Solution {
public:
    //单调栈 小于栈顶的push进去，高于栈顶的 取出栈顶元素，计算本层体积
    //栈存放的是下标
    int trap(vector<int>& height) {
        int n=height.size();        
        int res=0;
        stack<int> stk;
        for(int i=0;i<n;i++){
            while(!stk.empty() && height[i] > height[stk.top()]){
                int top=stk.top();
                stk.pop();
                //栈为空时退出循环
                if(stk.empty()){
                    break;
                }
                //每一层求长和宽
                int curWidth=i-stk.top()-1;
                int curHeight=min(height[i],height[stk.top()])-height[top];

                res+=curWidth*curHeight;
            }
            stk.push(i);
        }
        return res;
    }
};

3. 221. 最大正方形

class Solution {
public:
     //动态规划
    int maximalSquare(vector<vector<char>>& matrix) {
        if(matrix.size()==0||matrix[0].size()==0){
            return 0;
        }
        int maxSide=0;
        int m=matrix.size(),n=matrix[0].size();
        //定义dp[i][j]为坐标(i,j)的属于正方形的右下角，并且全为1的边长
        vector<vector<int>> dp(m,vector<int>(n));
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j]=='1'){
                   if(i==0||j==0){
                        dp[i][j]=1;
                    }else{
                        dp[i][j]=min(min(dp[i-1][j],dp[i-1][j-1]),dp[i][j-1])+1;
                    } 
                    maxSide=max(maxSide,dp[i][j]);
                }

            }
        }
        return maxSide*maxSide;
    }
};

class Solution {
public:
    //暴力破解：以当前方格为左上角，计算可能的正方形最大面积。超时
    int maximalSquare(vector<vector<char>>& matrix) {
        if(matrix.size()==0||matrix[0].size()==0){
            return 0;
        }
        int maxSide=0;
        int m=matrix.size(),n=matrix[0].size();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j]=='1'){
                   maxSide=max(maxSide,1);
                   int currentMaxSide=min(m-i,n-j);
                   for(int k=1;k<currentMaxSide;k++){
                       bool flag=true;
                       if(matrix[i+k][j+k]=='0') break;
                       for(int l=0;l<k;l++){
                           if(matrix[i+l][j+k]=='0'||matrix[i+k][j+l]=='0'){
                               flag=false;
                               break;
                           }
                       }
                       if(flag){
                           maxSide=max(maxSide,k+1);
                       }else{
                           break;
                       }
                   }
                }

            }
        }
        return maxSide*maxSide;
    }
};

4. 10. 正则表达式匹配

class Solution {
public:
    //递归法
    bool isMatch(string s, string p) {
        if(p.empty()) return s.empty();
        //相同或.跳过，一定匹配
        bool firstMatch=!s.empty()&&(s[0]==p[0]||p[0]=='.');
        //有*的匹配或不匹配，可以跳过，也可以匹配到下一个
        if(p.length()>1 && p[1]=='*'){
            return isMatch(s,p.substr(2))||(firstMatch && isMatch(s.substr(1),p));
        }else{
            return firstMatch && isMatch(s.substr(1),p.substr(1));
        }
    }
};

class Solution {
public:
    //递归法+memo
    map<pair<string,string>,bool> memo;
    bool isMatch(string s, string p) {
        if(p.empty()) return s.empty();

        auto key=make_pair(s,p);
        if(memo.count(key)){
            return memo[key];
        }
        //相同或.跳过，一定匹配
        bool firstMatch=!s.empty()&&(s[0]==p[0]||p[0]=='.');
        //有*的匹配或不匹配，可以跳过，也可以匹配到下一个
        if(p.length()>1 && p[1]=='*'){
            memo[key]=isMatch(s,p.substr(2))||(firstMatch && isMatch(s.substr(1),p));
        }else{
             memo[key]=firstMatch && isMatch(s.substr(1),p.substr(1));
        }
        return memo[key];
    }
};

class Solution {
public:
    //动态规划
    bool isMatch(string s, string p) {
        int m=s.length(),n=p.length();
        vector<vector<bool>> dp(m+1,vector<bool>(n+1,false));
        //两个空字符串匹配
        dp[0][0]=true;
        //s空时,遇到*取两个前匹配的结果
        for(int j=0;j<n;j++){
            if(p[j]=='*'){
                dp[0][j+1]=dp[0][j-1];
            }
        }
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(s[i]==p[j]||p[j]=='.'){
                    dp[i+1][j+1]=dp[i][j];
                }else if(p[j]=='*'){
                    if(s[i]==p[j-1]||p[j-1]=='.'){
                        dp[i+1][j+1]=dp[i+1][j-1]||dp[i][j-1]||dp[i][j+1];
                    }else{
                        dp[i+1][j+1]=dp[i+1][j-1];
                    }
                }
            }
        }
        return dp[m][n];
    }
};

5. 312. 戳气球

class Solution {
public:
    //记忆式搜索
    vector<vector<int>> res;
    vector<int> val;
    int maxCoins(vector<int>& nums) {
        int n=nums.size();
        val.resize(n+2);
        res.resize(n+2,vector<int>(n+2,-1));
        for(int i=1;i<=n;i++){
            val[i]=nums[i-1];
        }
        val[0]=val[n+1]=1;
        return solve(0,n+1);

    }
    int solve(int left,int right){
        if(left>=right-1){
            return 0;
        }
        if(res[left][right]!=-1){
            return res[left][right];
        }
        for(int i=left+1;i<right;i++){
            int sum=val[left]*val[i]*val[right];
            sum+=solve(left,i)+solve(i,right);
            res[left][right]=max(res[left][right],sum);
        }
        return res[left][right];
    }
};

class Solution {
public:
    //dp 
    int maxCoins(vector<int>& nums) {
        int n=nums.size();
        vector<int> val(n+2);
        vector<vector<int>> res(n+2,vector<int>(n+2));
        for(int i=1;i<=n;i++){
            val[i]=nums[i-1];
        }
        val[0]=val[n+1]=1;

        for(int i=n-1;i>=0;i--){
            for(int j=i+2;j<=n+1;j++){
                for(int k=i+1;k<j;k++){
                    int sum=val[i]*val[k]*val[j];
                    sum+=res[i][k]+res[k][j];
                    res[i][j]=max(res[i][j],sum);
                }
            }
        }
        return res[0][n+1];
    }
};

深度优先遍历

1. 22. 括号生成

class Solution {
public:
    vector<string> res;
    vector<string> generateParenthesis(int n) {
        dfs(n,0,0,"");
        return res;
    }   
    // 添加左括号，左括号数量要足够，添加右括号，右括号数量要足够，且左括号数要大于右括号数
    void dfs(int n,int lc,int rc,string str){
        if(lc==n&&rc==n) res.push_back(str);
        if(lc<n){
            dfs(n,lc+1,rc,str+"(");
        }
        if(rc<n&&lc>rc){
            dfs(n,lc,rc+1,str+")");
        }
    }
};

回溯法

1. 494. 目标和

class Solution {
public:
    //回溯法
    int count=0;
    int findTargetSumWays(vector<int>& nums, int target) {
        backtrack(nums,target,0,0);
        return count;
    }
    //sum记录当前经过元素的和，index记录已经过的元素下标
    void backtrack(vector<int>& nums,int target,int sum,int index){
        //加够五个数，和为target，是一种
        if(index==nums.size()){
            if(sum==target){
                count+=1;
            }
        }else{
            //+nums[index]或-nums[index]
            backtrack(nums,target,sum-nums[index],index+1);
            backtrack(nums,target,sum+nums[index],index+1);
        }
    }
};

class Solution {
public:
    //动态规划，正数sum-neg,负数neg,相加为target，经过推算 neg=(sum-target)/2
    //寻找这n个数中哪几个数相加能为(sum-target)/2
    //dp[i][j] 在数组前i个数选择元素，其和为j
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum=0;
        int n=nums.size();
        for(int i=0;i<n;i++){
            sum+=nums[i];
        }
        int diff=sum-target;
        if(diff<0||diff%2!=0){
            return 0;
        }

        int neg=diff/2;
        vector<vector<int>> dp(n+1,vector<int>(neg+1));
        dp[0][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=neg;j++){
                //这个元素小于j，可加可不加
                int num=nums[i-1];
                if(num<=j){
                    dp[i][j]=dp[i-1][j-num]+dp[i-1][j];
                }
                //这个元素大于j，不可加
                else{
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        return dp[n][neg];
    }
};

2. 301. 删除无效的括号

class Solution {
public:
     //回溯+剪枝
    vector<string> res;
    vector<string> removeInvalidParentheses(string s) {
        int lremove=0,rremove=0;
        for(char c:s){
            if(c=='(')
                lremove++;
            else if(c==')'){
                if(lremove==0) rremove++;
                else lremove--;
            }
        }
        helper(s,0,0,0,lremove,rremove);
        return res;
    }

    void helper(string s,int start,int lcount,int rcount,int lremove,int rremove){
        if(lremove==0 && rremove==0){
            if(isValid(s)){
                res.push_back(s);
            }
            return;
        }
        for(int i=start;i<s.length();i++){
            char cur=s[i];
            if(i==start||cur!=s[i-1]){
                //如果剩下的字符不能满足字数要求，直接返回，剪枝
                if(lremove+rremove>s.length()-i) return;
                //尝试去掉一个左括号
                if(lremove>0 && s[i]=='('){
                    helper(s.substr(0,i)+s.substr(i+1),i,lcount,rcount,lremove-1,rremove);
                }
                if(rremove>0 && s[i]==')'){
                    helper(s.substr(0,i)+s.substr(i+1),i,lcount,rcount,lremove,rremove-1);
                }
            }
            if(cur=='(') lcount++;
            else if(cur==')') rcount++;
            else if(lcount<rcount) break;  
        }      
    }
    bool isValid(const string& s){
        int cnt=0;
        for(int i=0;i<s.length();i++){
            if(s[i]=='(') cnt++;
            else if(s[i]==')'){
                cnt--;
                if(cnt<0){
                    return false;
                }
            }
        }
        return cnt==0;
    }
};

class Solution {
public:
    //bfs:每一轮删除字符串中的 11 个括号，直到出现合法匹配的字符串为止
    vector<string> removeInvalidParentheses(string s) {
        vector<string> res;
        unordered_set<string> currSet;

        currSet.insert(s);
        while(true){
            for(auto &str:currSet){
                if(isValid(str)){
                    res.emplace_back(str);
                }
            }

            if(res.size()>0){
                return res;
            }
            //接下来要遍历的set
            unordered_set<string> nextSet;
            for(auto &str:currSet){
                for(int i=0;i<str.size();i++){
                    if(i>0 && str[i]==str[i-1]) continue;
                    if(str[i]==')'||str[i]=='('){
                        nextSet.insert(str.substr(0,i)+str.substr(i+1));
                    }
                }
            }
            currSet=nextSet;
        }
    }

    bool isValid(string s){
        int cnt=0;
        for(int i=0;i<s.length();i++){
            if(s[i]=='('){
                cnt++;
            }else if(s[i]==')'){
                cnt--;
                if(cnt<0){
                    return false;
                }
            }
        }
        return cnt==0;
    }
};

二分法

1. 33. 搜索旋转排序数组

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n=nums.size();
        if(n<1) return -1;
        if(n==1) return target==nums[0]?0:-1;

        int l=0,r=n-1;
        while(l<=r){
            int mid=l+(r-l)/2;
            if(nums[mid]==target) return mid;
            if(nums[mid]>=nums[0]){  //左边有序
                if(nums[0]<=target&&target<=nums[mid]){
                    r=mid-1;
                }else{
                    l=mid+1;
                }
            }else{  //右边有序
                if(nums[mid]<=target&&nums[r]>=target){
                    l=mid+1;
                }else{
                    r=mid-1;
                }
            }
        }
        return -1;
    }
};

2. 287. 寻找重复数

class Solution {
public:
    //二分查找法：找中间那个数，看小于他的有多少个 
    int findDuplicate(vector<int>& nums) {
        int left=1;
        int right=nums.size()-1;
        while(left<right){
            int mid=left+(right-left)/2;
            int cnt=0;
            for(int &num:nums){
                if(num<=mid){
                    cnt++;
                }
            }
            if(cnt>mid){
                right=mid;
            }else{
                left=mid+1;
            }
        }
        return left;       

    }
};

class Solution {
public:
    //快慢指针
    int findDuplicate(vector<int>& nums) {
        int slow=0;
        int fast=0;
        //找到环
        do{
            slow=nums[slow];
            fast=nums[nums[fast]];
        }while(slow!=fast);
        //找入口
        slow=0;
        while(slow!=fast){
            slow=nums[slow];
            fast=nums[fast];
        }
        return slow;
    }
};

双指针

1. 88. 合并两个有序数组

class Solution {
public:
    //合并后排序
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for(int i=0;i<n;i++){
            nums1[m+i]=nums2[i];
        }
        sort(nums1.begin(),nums1.end());
    }
};

class Solution {
public:
    //尾部排序,逆向双指针，比较大小，大的放后边
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i=nums1.size()-1;
        m--;
        n--;
        while(n>=0){
            while( m>=0 && nums1[m] > nums2[n]){
                swap(nums1[i--],nums1[m--]);
            }            
            swap(nums1[i--],nums2[n--]);
        }
    }
};

class Solution {
public:
    //正向双指针
    //新建一个数组，比较、移动
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
       vector<int> temp(m+n,0);
       int p1=0,p2=0,p3=0;
       int cur=0;
       while(p1<m||p2<n){
           if(p1==m){
                temp[p3++]=nums2[p2++];
           }else if(p2==n){
                temp[p3++]=nums1[p1++];
           }else if(nums1[p1]<nums2[p2]){
                temp[p3++]=nums1[p1++];
           }else{
                temp[p3++]=nums2[p2++];
           }
       }
       for(int i=0;i!=m+n;i++){
           nums1[i]=temp[i];
       }  
    }
};

2. 4. 寻找两个正序数组的中位数

class Solution {
public:
    //先合并，在排序，然后找中位数
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        for(int &num:nums2){
            nums1.push_back(num);
        }
        sort(nums1.begin(),nums1.end());
        int n=nums1.size();
        if(n%2==1){
            return nums1[n/2];
        }else{
            //除以2.0
            return (nums1[n/2-1]+nums1[n/2])/2.0;
        }
    }
};

class Solution {
public:
    //双指针，找count为中间的
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        //定义两个指针指向两个数组,pre记录前一数，cur记录现在访问的数
        int i=0,j=0,pre=-1,cur=-1;
        //index记录访问的总个数,当为一半时返回，注意分奇偶
        int index=0;

        int n1=nums1.size(),n2=nums2.size();
        int n=n1+n2;
        while(index<((n>>1)+1)){
            pre=cur; 
            if(i<n1&&j<n2){
                if(nums1[i]<nums2[j]){
                    cur=nums1[i++];
                }else{
                    cur=nums2[j++];
                }
            }else if(i>=n1&&j<n2){
                cur=nums2[j++];
            }else if(i<n1){
                cur=nums1[i++];
            }           
            index++;
        }
        if(n%2==0){
            return (cur+pre)*0.5;
        }
        return cur;
    }
};

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if(nums1.size()>nums2.size()){
            vector<int> tmp=nums1;
            nums1=nums2;
            nums2=tmp;
        }

        int m=nums1.size(),n=nums2.size();
        // 分割线左边的所有元素需要满足的个数 m + (n - m + 1) / 2;

        int totalLeft=(m+n+1)/2;
        // 在 nums1 的区间 [0, m] 里查找恰当的分割线，
        // 使得 nums1[i - 1] <= nums2[j] && nums2[j - 1] <= nums1[i]
        int left=0,right=m;

        while(left<right){
            int i=left+(right-left+1)/2;
            int j=totalLeft-i;

            if(nums1[i-1]>nums2[j]){
                // 下一轮搜索的区间 [left, i - 1]
                right=i-1;
            }else{
                // 下一轮搜索的区间 [i, right]
                left=i;
            }
        }

        int i=left;
        int j=totalLeft-i;

        int nums1LeftMax=i==0?INT_MIN:nums1[i-1];
        int nums1RightMin=i==m?INT_MAX:nums1[i];
        int nums2LeftMax=j==0?INT_MIN:nums2[j-1];
        int nums2RightMin=j==n?INT_MAX:nums2[j];

        if((m+n)%2==1){
            return max(nums1LeftMax,nums2LeftMax);
        }else{
            return (double)(max(nums1LeftMax,nums2LeftMax)+min(nums1RightMin,nums2RightMin))/2.0;
        }
    }
};

3. 15. 三数之和

class Solution {
public:
    //排序+双指针
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        int n=nums.size();
        if(n<3){
            return res;
        }

        sort(nums.begin(),nums.end());
        for(int i=0;i<n;i++){
            //第一个元素就大于0，后边比不可能小于0
            if(nums[i]>0){
                return res;
            }
            //去重
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            int l=i+1,r=n-1;
            while(l<r){
                int sum=nums[i]+nums[l]+nums[r];
                if(sum==0){
                    //是一种情况，push到结果中
                    res.push_back({nums[i],nums[l],nums[r]});
                    // l和r往后走
                    while(l<r&&nums[l]==nums[l+1]) l++;
                    while(l<r&&nums[r]==nums[r-1]) r--;
                    l++;r--;
                }
                //和小了，增大最大值
                else if(sum<0){
                    l++;
                }
                //和大了，减小最大值
                else if(sum>0){
                    r--;
                }
            }
        }
        return res;
    }
};

4. 75. 颜色分类

class Solution {
public:
    //双指针 p0指向0，p2指向2，从后往前将2放回，在从前往后
    void sortColors(vector<int>& nums) {
        int n=nums.size();
        int p0=0,p2=n-1;
        for(int i=0;i<=p2;i++){
            while(i<=p2&&nums[i]==2){
                swap(nums[i],nums[p2]);
                p2--;
            }
            if(nums[i]==0){
                swap(nums[i],nums[p0]);
                p0++;
            }
        }
    }
};

class Solution {
public:
    //单指针，先放正0，在接着后边放1
    void sortColors(vector<int>& nums) {
        int ptr=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]==0){
                swap(nums[i],nums[ptr]);
                ptr++;
            }
        }
        for(int i=0;i<nums.size();i++){
            if(nums[i]==1){
                swap(nums[i],nums[ptr]);
                ptr++;
            }
        }

    }
};

5. 581. 最短无序连续子数组

class Solution {
public:
    // 先排序，然后数组左右两端开始扫描
    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> tmp(nums);
        sort(nums.begin(),nums.end());

        int res=0;
        int left=0,right=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]!=tmp[i]){
                left=i;
                break;
            }
        }
        for(int i=nums.size()-1;i>=0;i--){
            if(nums[i]!=tmp[i]){
                right=i;
                break;
            }
        }
        // 如果都为0，说明有序，返回0
        return right==left?0:right-left+1;
    }
};

public:
    // A B C序列 B无序，但B中值要大于C中最小值，B中值要大于A中最大值
    int findUnsortedSubarray(vector<int>& nums) {
        int n=nums.size();

        //记录A最大值，C最小值
        int m_max=INT_MIN,m_min=INT_MAX,l=-1,r=-1;

        for(int i=0;i<n;i++){
            //找最后一个小于m_max的元素下标
            if(nums[i]<m_max) r=i;  
            else m_max=nums[i];  

            //找最后一个大于m_min的元素下标
            if(nums[n-1-i]>m_min) l=n-1-i;
            else m_min=nums[n-1-i]; //正常的，更新右边最小值
        }
        return r==-1?0:(r-l+1);
    }
};

链表

1. 146. LRU 缓存

//hash表+双向链表
struct DLinkNode{
    int key;
    int value;
    DLinkNode* prev;
    DLinkNode* next;
    DLinkNode():key(0),value(0),prev(nullptr),next(nullptr){}
    DLinkNode(int _key,int _value):key(_key),value(_value),prev(nullptr),next(nullptr){}
};
class LRUCache {
private:
    unordered_map<int,DLinkNode*> cache;
    DLinkNode* head;
    DLinkNode* tail;
    int capacity;
    int size;
public:
    LRUCache(int _capacity):capacity(_capacity),size(0) {
        //虚拟头节点和尾部节点
        head=new DLinkNode();
        tail=new DLinkNode();
        head->next=tail;
        tail->prev=head;
    }

    int get(int key) {
        //先通过hash表找位置，然后移动到最后边
        if(!cache.count(key)){
            return -1;
        }
        DLinkNode* node=cache[key];
        movToHead(node);
        return node->value;
    }

    void put(int key, int value) {
        //hash表没有这个元素，添加
        if(!cache.count(key)){
            DLinkNode* node=new DLinkNode(key,value);
            cache[key]=node;
            //添加至头部
            addToHead(node);
            size++;
            //超出容量，删除tail元素,并从hash表中删除
            if(size>capacity){  
                DLinkNode* removeNode=removeTail();
                cache.erase(removeNode->key);
                size--;
            }
        }
        //有这个元素，更改value
        DLinkNode* node=cache[key];
        node->value=value;
        movToHead(node);
    }
    //把节点从双向链表中摘出来
    void moveNode(DLinkNode* node){
        node->prev->next=node->next;
        node->next->prev=node->prev;
    }
    //把节点添加到head
    void addToHead(DLinkNode* node){
        node->prev=head;
        node->next=head->next;
        head->next->prev=node;
        head->next=node;
    }
    void movToHead(DLinkNode* node){
        //先把节点摘出来
        moveNode(node);
        //在添加到头部
        addToHead(node);
    }

    DLinkNode* removeTail(){
        DLinkNode* node=tail->prev;
        moveNode(node);
        return node;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

哈希表

1. 448. 找到所有数组中消失的数字

class Solution {
public:
    //哈希表,存入hash中进行查找
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        unordered_set<int> num_set;
        vector<int> res;
        for(int &num:nums){
            num_set.insert(num);
        }
        for(int i=1;i<=nums.size();i++){
            if(!num_set.count(i)){
                res.push_back(i);
            }
        }
        return res;
    }
};

class Solution {
public:
    //哈希表,存入hash中进行查找，将nums作为hash表，不额外申请空间
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> res;
        int n=nums.size();
        for(int &num:nums){
            //先把这个数放到正确位置上,找到这个数应该放在哪里
            int x=(num-1)%n;
            //对应位置的元素+n
            nums[x]+=n;
        }
        //只要操作过的元素，必然已经+n了，找出小于等于n的即可
        for(int i=0;i<n;i++){
            if(nums[i]<=n){
                res.push_back(i+1);
            }
        }
        return res;
    }
};

2. 169. 多数元素

class Solution {
public:
    //hash 添加到hash表中，并比较其出现次数
    int majorityElement(vector<int>& nums) {
        unordered_map<int,int> num_map;
        for(int num:nums){
            num_map[num]++;
            if(num_map[num]>nums.size()/2){
                return num;
            }
        }
        return -1;
    }
};

class Solution {
public:
    //排序找中位数，一定是这个众数
    int majorityElement(vector<int>& nums) {
       sort(nums.begin(),nums.end());
       return nums[nums.size()/2];
    }
};

class Solution {
public:
    //随机法，随机选择一个数，有较大概率是众数，验证一下,不是继续随机
    int majorityElement(vector<int>& nums) {
       while(1){
           int can=nums[rand()%nums.size()];
           int count=0;
           for(int num:nums){
               if(num==can){
                   count++;
               }
           }
           if(count>nums.size()/2){
               return can;
           }
       }
       return -1;
    }
};

class Solution {
public:
    //Boyer Moore算法 有待研究。同归于尽法
    //先来的小兵占据阵营，后来的是同一个阵营++，不是--，当兵力全无，新士兵成为领主，最终剩下的必然是众数
    int majorityElement(vector<int>& nums) {
       int can=-1;
       int count=0;
       for(int num:nums){
           if(num==can){
               count++;
           }else{
               count--;
               if(count<0){
                   can=num;
                   count=1;
               }
           }
       }
       return can;
    }
};

3. 49. 字母异位词分组

class Solution {
public:
     //map 排序
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        //map第一个key放排序结果，value放排序前的词，可能有多个
        unordered_map<string,vector<string>> mp;
        for(string& str:strs){
            string key=str;
            sort(key.begin(),key.end());
            mp[key].emplace_back(str);//直接在尾部创建，而非push_back那样 创建-复制
        }

        vector<vector<string>> res;
        for(auto it=mp.begin();it!=mp.end();it++){
            res.emplace_back(it->second);
        }
        return res;
    }
};

贪心算法

1. 56. 合并区间

class Solution {
public:
    //贪心算法，找局部最优
    static bool cmp(vector<int>& a,vector<int>& b){
        return a[0]<b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        //按区间左端点进行排序
        vector<vector<int>> res;
        sort(intervals.begin(),intervals.end(),cmp);

        res.push_back(intervals[0]);
        for(int i=1;i<intervals.size();i++){
            //比较结果集中的结束端点和 本区间的开始端点，看是否能合并
            if(intervals[i][0]<=res.back()[1]){
                res.back()[1]=max(res.back()[1],intervals[i][1]);
            }else{
                res.push_back(intervals[i]);
            }
        }
        return res;
    }
};

栈

1. 84. 柱状图中最大的矩形

class Solution {
public:
    //暴力破解，超时
    //以每个单元为高度，向左向右找最长宽度
    int largestRectangleArea(vector<int>& heights) {
        int n=heights.size();
        if(n==0){
            return 0;
        }

        int res=0;
        for(int i=0;i<n;i++){
            //找到左边最后一个大于等于height[i]的下标
            int left=i;
            int curHeight=heights[i];
            while(left>0&&heights[left-1]>=curHeight){
                left--;
            }
            //找到右边...
            int right=i;
            while(right<n-1&&heights[right+1]>=curHeight){
                right++;
            }

            int width=right-left+1;
            res=max(res,width*curHeight);

        }
        return res;
    }
};

class Solution {
public:
    //单调栈
    //以每个单元为高度，向左向右找最长宽度，左右边找高度最小边界
    int largestRectangleArea(vector<int>& heights) {
        int res=0;
        stack<int> stk;
        heights.insert(heights.begin(),0);
        heights.push_back(0);
        for(int i=0;i<heights.size();i++){
            while(!stk.empty() && heights[stk.top()] > heights[i] ){
                int cur=stk.top();
                stk.pop();
                int left=stk.top()+1;
                int right=i-1;
                res=max(res,(right-left+1)*heights[cur]);
            }
            stk.push(i);
        }
        return res;
    }
};

2. 85. 最大矩形

class Solution {
public:
    //暴力破解，先找行最大，在往上扩展列
    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.size()==0) return 0;
        int row=matrix.size(),col=matrix[0].size();

        int res=0;
        //记录以当前数字结尾的连续1的个数
        vector<vector<int>> width(row,vector<int>(col,0));
        //遍历每一行
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(matrix[i][j]=='1'){
                    if(j==0){
                        width[i][j]=1;
                    }else{
                        width[i][j]=width[i][j-1]+1;
                    }
                }else{
                    width[i][j]=0;
                }
                //记录最短行
                int minWidth=width[i][j];
                //向上扩展
                for(int up_row=i;up_row>=0;up_row--){
                    int height=i-up_row+1;
                    minWidth=min(minWidth,width[up_row][j]);
                    res=max(res,minWidth*height);
                }
            }
        }
        return res;
    }
};

class Solution {
public:
    //先找柱状图中的最大矩形，然后找每层的
    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.size()==0){
            return 0;
        }
        int area=0;
        vector<int> heights(matrix[0].size(),0);
        for(int row=0;row<matrix.size();row++){
            for(int col=0;col<matrix[0].size();col++){
                //更新单层柱状图
                if(matrix[row][col]=='1'){
                    heights[col]+=1;
                }else{
                    heights[col]=0;
                }
            }
            area=max(area,largestRectangleArea(heights));
        }
        return area;
    }
    //找柱状图中的最大矩形,值传递
    int largestRectangleArea(vector<int> heights) {
        int res=0;
        stack<int> stk;
        heights.insert(heights.begin(),0);
        heights.push_back(0);
        for(int i=0;i<heights.size();i++){
            while(!stk.empty() && heights[stk.top()] > heights[i] ){
                int cur=stk.top();
                stk.pop();
                int left=stk.top()+1;
                int right=i-1;
                res=max(res,(right-left+1)*heights[cur]);
            }
            stk.push(i);
        }
        return res;
    }
};

class Solution {
public:
    //先找柱状图中的最大矩形，然后找每层的
    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.size()==0){
            return 0;
        }
        int area=0;
        vector<int> heights(matrix[0].size()+1,0);
        for(int row=0;row<matrix.size();row++){
            stack<int> stk;
            //每求一个高度就进行栈操作，考虑最后一个，多申请一个元素
            for(int col=0;col<=matrix[0].size();col++){
                if(col<matrix[0].size()){
                    //更新单层柱状图
                    if(matrix[row][col]=='1'){
                        heights[col]+=1;
                    }else{
                        heights[col]=0;
                    }     
                }                

                while(!stk.empty() && heights[col]<heights[stk.top()]){
                    int cur=stk.top();
                    stk.pop();
                    int left=(stk.empty()?-1:stk.top())+1;
                    int right=col-1;
                    area=max(area,(right-left+1)*heights[cur]);
                }
                stk.push(col);   
            }         
        }
        return area;
    }

};

3. 394. 字符串解码

class Solution {
public:
    //栈
    string decodeString(string s) {
        string res="";
        stack<string> strs;
        stack<int> nums; 

        int num=0;
        for(int i=0;i<s.length();i++){
            if(s[i]>='0'&&s[i]<='9'){
                num=num*10+s[i]-'0';
            }else if((s[i]>='a'&&s[i]<='z')||(s[i]>='A'&&s[i]<='Z')){
                res+=s[i];
            }else if(s[i]=='['){//将‘[’前的数字压入nums栈内， 字母字符串压入strs栈内
                nums.push(num);
                num=0;
                strs.push(res);
                res="";
            }else if(s[i]==']'){//遇到‘]’时，操作与之相配的‘[’之间的字符，使用分配律
                int cnt=nums.top();    
                nums.pop(); 
                while(cnt--){
                    strs.top()+=res;
                }
                res=strs.top();
                strs.pop();
            }
        }
        return res;
    }
};

class Solution {
public:
    //递归
    string decodeString(string s) {
        int index=0;
        return analysis(s,index);
    }
    //引用
    string analysis(string s,int& index){
        int num=0;
        string res;
        string temp;
        while(index<s.length()){
            if(s[index]>='0'&&s[index]<='9'){ //数字
                num=num*10+s[index]-'0';
            }else if(s[index]=='['){ //进入递归
                temp=analysis(s,++index);
                while(num-->0){
                    res+=temp;
                }
                num=0;
            }else if(s[index]==']') break; //跳出
            else{
                res+=s[index];  //字母
            }
            index++;
        }
        return res;
    }
};

4. 155. 最小栈

class MinStack {
public:
    stack<int> st;
    stack<int> minSt;
    MinStack() {
        while(!st.empty()){
            st.pop();
        }
        while(!minSt.empty()){
            minSt.pop();
        }
        minSt.push(INT_MAX);
    }

    void push(int val) {
        st.push(val);
        minSt.push(min(minSt.top(),val));//比较一下，把较小值push进去
    }

    void pop() {
        st.pop();
        minSt.pop();
    }

    int top() {
        return st.top();
    }

    int getMin() {
        return minSt.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

class MinStack {
public:
    stack<pair<int,int>> st;
    MinStack() {
        while(!st.empty()){
            st.pop();
        }
    }

    void push(int val) {
        if(st.empty()) st.push(make_pair(val,val));
        else st.push(make_pair(val,min(val,st.top().second)));
    }

    void pop() {
        st.pop();
    }

    int top() {
        return st.top().first;
    }

    int getMin() {
        return st.top().second;
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

排序

1. 215. 数组中的第K个最大元素

class Solution {
public:
    //内置排序
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        return nums[nums.size()-k];
    }
};

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        quickSort(nums,0,nums.size()-1);
        return nums[nums.size()-k];
    }
    //快排
    void quickSort(vector<int>& nums,int left,int right){
        if(left<right){
            int mid=partition(nums,left,right);
            quickSort(nums,left,mid-1);
            quickSort(nums,mid+1,right);
        }
    }
    int partition(vector<int>& nums,int left,int right){
        int priot=nums[left];
        int i=left+1,j=right;
        while(1){
            while(i<=j && nums[i]<=priot) i++;
            while(i<=j && nums[j]>=priot) j--;
            if(i>=j) break;
            swap(nums[i],nums[j]);
        }
        nums[left]=nums[j];
        nums[j]=priot;
        return j;
    }
};

class Solution {
public:
    //快速排序，随机选择中轴元素
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(0));
        quickSort(nums,0,nums.size()-1);
        return nums[nums.size()-k];
    }
    //快排
    void quickSort(vector<int>& nums,int left,int right){
        if(left<right){
            int mid=partition(nums,left,right);
            quickSort(nums,left,mid-1);
            quickSort(nums,mid+1,right);
        }
    }
    int partition(vector<int>& nums,int left,int right){
        //随机选择中轴元素
        int a=rand()%(right-left+1)+left;
        swap(nums[left],nums[a]);

        int priot=nums[left];
        int i=left+1,j=right;
        while(1){
            while(i<=j && nums[i]<=priot) i++;
            while(i<=j && nums[j]>=priot) j--;
            if(i>=j) break;
            swap(nums[i],nums[j]);
        }
        nums[left]=nums[j];
        nums[j]=priot;
        return j;
    }
};

class Solution {
public:
    //堆排序
    int findKthLargest(vector<int>& nums, int k) {
        //建立大根堆
        int　n=nums.size();
        for(int i=n/2-1;i>=0;i--){
            downAdjust(nums,i,n-1);
        }
        //pop k-1个元素
        for(int i=n-1;i>=n-k+1;i--){
            swap(nums[0],nums[i]);
            downAdjust(nums,0,i-1);
        }
        return nums[0];

    }
    void downAdjust(vector<int>& nums,int parent,int length){
        int child=2*parent+1;
        int temp=nums[parent];
        while(child<=length){
            //左右子节点中较大的一个与其交换
            if(child+1<=length && nums[child+1]>nums[child]){
                child++;
            }
            if(temp>=nums[child]) break;
            nums[parent]=nums[child];
            parent=child;
            child=2*parent+1;
        }
        nums[parent]=temp;//完成下沉 赋值
    }
};

并查集

1. 399. 除法求值

class Solution {
public:
    //并查集
    class UF{
    private:
        vector<int> parent;
        //指向父节点的权值
        vector<double> weight;
    public:
        UF(int n){
            parent.resize(n);
            weight.resize(n,1.0);
            for(int i=0;i<n;i++){
                parent[i]=i;
            }
        }
        void Union(int x,int y,double value){
            int rootX=find(x);
            int rootY=find(y);
            if(rootX==rootY){
                return;
            }
            parent[rootX]=rootY;
            weight[rootX]=weight[y]*value/weight[x];
        }
        //找x的root，顺便路径压缩
        int find(int x){
            if(x!=parent[x]){
                int old=parent[x];
                parent[x]=find(old);
                weight[x]*=weight[old];
            }
            return parent[x];
        }
        //判断是否相连
        double isConnected(int x,int y){
            int rootX=find(x);
            int rootY=find(y);
            if(rootX==rootY){
                return weight[x]/weight[y];
            }else{
                return -1.0;
            }
        }

    };
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        unordered_map<string,int> hashMap;
        //存放结果
        vector<double> res;
        int id=1;

        //首先把等式放入并查集中
        //给字母赋予id，以便取出,存入hash表
        for(auto& str:equations){
            if(!hashMap.count(str[0])){
                hashMap[str[0]]=id++;
            }
            if(!hashMap.count(str[1])){
                hashMap[str[1]]=id++;
            }
        }
        UF uf(id);
        for(int i=0;i<values.size();i++){
            uf.Union(hashMap[equations[i][0]],hashMap[equations[i][1]],values[i]);
        }
        //进行查询        
        for(auto& str:queries){
            if(!hashMap.count(str[0])||!hashMap.count(str[1])){
                res.push_back(-1.0);
                continue;
            }
            res.push_back(uf.isConnected(hashMap[str[0]],hashMap[str[1]]));
        }
        return res;
    }

};

class Solution {
public:
    //dfs
    vector<double> res;
    bool Nofind;
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        ////string - string(double)  a连接b(b带上权值)
        unordered_map<string,vector<pair<string,double>>> g;
        unordered_map<string,int> visit;

        for(int i=0;i<equations.size();i++){
            g[equations[i][0]].push_back(make_pair(equations[i][1],values[i]));
            g[equations[i][1]].push_back(make_pair(equations[i][0],1.0/values[i]));
        }

        //遍历queries，对每一组进行dfs计算结果。
        //如果相连接，就把 路径上的权值相乘就是结果
        for(int i=0;i<queries.size();i++){
            if(!g.count(queries[i][0])){
                res.push_back(-1.0);
                continue;
            }
            //设置一个全局变量，如果进行dfs后，queries[0]到不了queries[1]，Nofind = true;
            Nofind=true;

            visit[queries[i][0]]=1;
            dfs(g,visit,queries[i][0],queries[i][1],1);
            visit[queries[i][0]]=0;

            if(Nofind){
                res.push_back(-1.0);
            }          
        }
        return res;
    }

    void dfs(unordered_map<string,vector<pair<string,double>>> &g,unordered_map<string,int>& visit,string val,const string& target,const double& path){
        //如果节点已经相连接，那没 必要再dfs搜索了，直接返回
        if(Nofind==false) return;
        if(val==target){
            Nofind=false;
            res.push_back(path);
            return;
        }
        for(int j=0;j<g[val].size();j++){
            if(visit[g[val][j].first]==0){
                visit[g[val][j].first]=1;
                dfs(g,visit,g[val][j].first,target,path*g[val][j].second);
                visit[g[val][j].first]=0;
            }
        }
    }
};