【力扣打卡--day6】

1.链表2.链表3.栈4.dfs5.dp6.链表7.dfs8.dfs9.dp10.dp

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* dummy=new ListNode(-1);//哨兵节点
        dummy->next=head;
        auto p=dummy;
        while(p->next){
            auto q=p->next->next;//负责找不重复的节点
            while(q&&q->val==p->next->val) q=q->next;//重复就跳
            if(q==p->next->next) p=p->next;//没有重复的
            else{
                p->next=q;//有重复的就删
            }
        }
        return dummy->next;
    }
};

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* head0=head;
        ListNode* s=new ListNode(-1);//小于x的链表的尾
        ListNode* b=new ListNode(-1);//大的尾
        ListNode* sH=s;//记录头
        ListNode* bH=b;
        for(ListNode* i=head;i!=NULL;i=i->next){
            if(i->valnext=i;
                s=s->next;
            }else{
                b->next=i;
                b=b->next;
            }
        }
        s->next=bH->next;
        b->next=NULL;
        return sH->next;
    }
};

class Solution {
public:
    vector grayCode(int n) {
        vector res(1,0);//只有一个数，不用对称
        while(n--){
            for(int i=res.size()-1;i>=0;i--){//对称开始遍历
                res[i]*=2;//对称轴上方最后位添0
                res.push_back(res[i]+1);//对称轴上方最后位添1
            }
        }
        return res;
    }
};

class Solution {
public:
    unordered_map hash;
    vector path;
    vector> ans;

    vector> subsetsWithDup(vector& nums) {
        for(auto x:nums) hash[x]++;//统计每个数有几个
        dfs(-10);//从-10找到10
        return ans;
    }

    void dfs(int x){
        if(x>10){//结束
            ans.push_back(path);
        }
        else{
            for(int i=0;i 
 
5.dp 

 
 
 
class Solution {
public:
    int numDecodings(string s) {
        int n=s.size();
        s=' '+s;
        vector f(n+1);
        f[0]=1;
        for(int i=1;i<=n;i++){
            if(s[i]>='1'&&s[i]<='9'){
                f[i]=f[i-1];//一个数
            }
            if(i>1){//两个数
                int t=(s[i-1]-'0')*10+s[i]-'0';
                if(t>=10&&t<=26) f[i]+=f[i-2];
            }
        }
        return f[n];
    }
};
 
 
6.链表 

 
 
 
 
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        auto dummy=new ListNode(-1);
        dummy->next=head;
        auto a=dummy;
        for(int i=0;inext;//a到left左边
        auto b=a->next,c=b->next;//画图来看吧，先反转left和right中间的，再把头尾转了
        for(int i=0;inext;
            c->next=b;
            b=c,c=d;
        }
        a->next->next=c;
        a->next=b;
        return dummy->next;
    }
};
 
 
7.dfs 

 
 
class Solution {
public:
    vector res;

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

    void dfs(string& s,int u,int k,string path){//u是遍历到第几位，k是第几个数
        if(u==s.size()){
            if(k==4){
                path.pop_back();
                res.push_back(path);
            }
            return;
        }
        if(k==4) return;//剪枝
        for(int i=u,t=0;iu&&s[u]=='0') break;//前导0
            t=t*10+s[i]-'0';//只要能构成数都一直加
            if(t<=255) dfs(s,i+1,k+1,path+to_string(t)+'.');//看是否构成一个
            else break;
        }
    }
};
 
 
8.dfs 
 
class Solution {
public:
    vector generateTrees(int n) {
        if(n>0) return dfs(1,n);
        else return {};
    }

    vector dfs(int l,int r){
        if(l>r) {
            return {};
        }
        vector ans;
        for(int i=l;i<=r;i++){
            auto leftNodes=dfs(l,i-1);
            auto rightNodes=dfs(i+1,r);
            for(auto a:leftNodes){//遍历左子树的根
                for(auto b:rightNodes){//一个相同的形状会被共用多次，扭转
                    auto t=new TreeNode(i);
                    t->left=a;
                    t->right=b;
                    ans.push_back(t);
                }
            }
        }
        return ans;
    }
};
 
 
9.dp 
 
class Solution {
public:
    int numTrees(int n) {
        vector dp=vector(n+1);
        dp[0]=1;
        for(int i=1;i<=n;i++){//区间
            for(int j=1;j<=i;j++){//根
                dp[i]+=dp[j-1]*dp[i-j];
            }     
        }
        return dp[n];
    }
};
 
 
10.dp 

 
 
 
 
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n=s1.size(),m=s2.size();
        if(s3.size()!=n+m) return false;

        vector> f(n+1,vector(m+1));//表示能不能被s1和s2组
        s1=' '+s1,s2=' '+s2,s3=' '+s3;
        for(int i=0;i<=n;i++)
            for(int j=0;j<=m;j++){
                if(!i&&!j) f[i][j]=true;
                else{
                    if(i&&s1[i]==s3[i+j]) f[i][j]=f[i-1][j];//被s1组
                    if(j&&s2[j]==s3[i+j]) f[i][j]=f[i][j]||f[i][j-1];//被s2组
                }
            }
        return f[n][m];
    }
};