1.dfs

在这里插入图片描述

class Solution {
public:
    vector<string> ans;

    string a[10]={
        "","","abc","def",
        "ghi","jkl","mno",
        "pqrs","tuv","wxyz"
    };

    vector<string> letterCombinations(string digits) {
        if(digits=="") return ans;
        dfs(digits,0,"");
        return ans;
    }

    void dfs(string& digits,int idx,string tmp){
        if(idx==digits.size()) ans.push_back(tmp);
        else{
            for(auto c:a[digits[idx]-'0']){//查表爆搜
                dfs(digits,idx+1,tmp+c);
            }
        }
    }
};

2.双指针

在这里插入图片描述

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> res;
        int N=nums.size();
        for(int i=0;i<N;i++){//一个数就直接双指针，两个就先枚举一个再双指针，
        //三个就先枚举两个再双指针，。。。，n个就dp
            if(i&&nums[i]==nums[i-1]) continue;
            for(int j=i+1;j<N;j++){
                if(j>i+1&&nums[j]==nums[j-1]) continue;
                for(int a=j+1,b=N-1;a<b;a++){
                    if(a>j+1&&nums[a]==nums[a-1]) continue;
                    while(b-1>a&&(long long)nums[i]+nums[j]+nums[a]+nums[b-1]>=target) b--;
                    if(((long long)nums[i]+nums[j]+nums[a]+nums[b])==target){
                        res.push_back({nums[i],nums[j],nums[a],nums[b]});
                    }
                }
            }
        }
        return res;
    }
};

3.双指针

在这里插入图片描述

/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy=NULL;
        int l=1;
        for(ListNode* i=head;i;i=i->next){
            if(dummy!=NULL) dummy=dummy->next;//找到了之后才跟着尾部一起走
            if(l==n+1){//先找到和尾节点间隔为n的节点
                dummy=head;
            }
            l++;
        }
        if(dummy) dummy->next=dummy->next->next;//此时它在要删节点的前面，
        //dummy为空说明要删的是头节点，因为头节点前面没有节点，所以dummy是空
        else return head->next;//假如是删头节点直接返回
        return head;
    }
};

4.dfs

在这里插入图片描述

class Solution {
public:
    vector<string>  res;
    vector<string> generateParenthesis(int n) {
        dfs("",0,0,n);
        return res;
    }
    void dfs(string tmp,int cnt1,int cnt2,int n){
        if(cnt1==n&&cnt2==n){
            //知识点二：“（”“）”总数量相等；题目已保证了
            res.push_back(tmp);
        }
        else{
            if(cnt1<n) dfs(tmp+'(',cnt1+1,cnt2,n);
            if(cnt1>cnt2&&cnt2<n) dfs(tmp+')',cnt1,cnt2+1,n);
            //知识点一：任意前缀“（”数量大于“）”数量；
        } 
    }
};

5.dfs

在这里插入图片描述

class Solution {
public:
    vector<string>  res;
    vector<string> generateParenthesis(int n) {
        dfs("",0,0,n);
        return res;
    }
    void dfs(string tmp,int cnt1,int cnt2,int n){
        if(cnt1==n&&cnt2==n){
            //知识点二：“（”“）”总数量相等；题目已保证了
            res.push_back(tmp);
        }
        else{
            if(cnt1<n) dfs(tmp+'(',cnt1+1,cnt2,n);
            if(cnt1>cnt2&&cnt2<n) dfs(tmp+')',cnt1,cnt2+1,n);
            //知识点一：任意前缀“（”数量大于“）”数量；
        } 
    }
};

6.双指针

在这里插入图片描述

/**
 * 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* swapPairs(ListNode* head) {
        ListNode* dummy=new ListNode(-1);
        dummy->next=head;
        for(auto p=dummy;p->next&&p->next->next;){
            ListNode* a=p->next,* b=p->next->next;//画图就明白了
            p->next=b;
            a->next=b->next;
            b->next=a;
            p=a;
        }
        return dummy->next;
    }
};

7.位运算（快速幂）

在这里插入图片描述

class Solution {
public:
    int divide(int dividend, int divisor) {
        typedef long long LL;
        vector<LL> exp;
        bool is_minus=false;
        if(dividend<0&&divisor>0||divisor<0&&dividend>0) is_minus=true;
        LL a=abs(LL(dividend)),b=abs(LL(divisor));//符号
        for(LL i=b;i<=a;i+=i){
            exp.push_back(i);//可能要用的二进制统一打包好  
        }

        LL res=0;
        for(int i=exp.size()-1;i>=0;i--){
            if(a>=exp[i]){//先看大包的能不能用，能就用
                res+=1ll<<i;//1移位后可能溢出
                a-=exp[i];
            }
        }
        if(is_minus) res=-res;
        if(res<INT_MIN||res>INT_MAX) return INT_MAX;
        return res;
    }
};

8.找规律

在这里插入图片描述

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int k = nums.size() - 1;
        while (k > 0 && nums[k] <= nums[k-1]) {//先找第一个顺序的，找到后顺便确保了k之后的都是递减
            k--;
        }
        if (k > 0) {
            int t = k;
            while (t<nums.size() && nums[t] > nums[k-1]) {//找第一个比k-1大的，
            //找到后t之后的元素都比k-1小，同时t之前的元素又比i大，交换t-1和k-1就是用最小的增大了k-1位置
            //同时k-1之后全都是逆序的了，所以接下来直接倒序将k-1之后的序列变最小就行了
                t++;
            }
            swap(nums[t-1], nums[k-1]);
            reverse(nums.begin() + k, nums.end());
        }else{
            reverse(nums.begin(), nums.end());
        }
        
    }
};

10.二分

在这里插入图片描述

class Solution {
public:
    int search(vector<int>& nums, int target) {//画图可知图分为两段
        if(nums.size()==0) return -1;
        int l=0,r=nums.size()-1;
        while(l<r){
            int mid=l+r+1>>1;
            if(nums[0]<=nums[mid]) l=mid;//先找第一段的最后一个位置
            else r=mid-1;
        }
        if(target>=nums[0]){//看目标值在第一段还是第二段
            l=0;
        }else{
            l=l+1,r=nums.size()-1;
        }
        while(l<r){//二分找目标值
            int mid=l+r>>1;
            if(nums[mid]>=target) r=mid;
            else l=mid+1;
        }
        if(target==nums[r]) return r;//找到
        return -1;
    }
};