nonstop

关注数

粉丝数

阅读量

399

+关注发消息

离线：1天前

递归算法

算法描述：

`ListNode* deleteDuplication(ListNode* head)`

这个函数的作用是将以head为头结点的链表中的重复元素删除，并返回新链表的头结点

那么按照递归的思想：

如果当前传入的head指针本身就是null（空链表），或者head->next是null（只有一个元素的链表），那就不存在重复的问题，直接返回head作为新链表的头指针即可

如果head->next不是null，那么判断一下head->next结点的值是否等于head结点的值。

如果相等，那么说明出现了重复结点，需要进一步操作。下面细说。

首先需要判断head->next->next是否存在。

如果head->next->nex不存在：说明这两个重复结点后面已经没有其他的节点了，删掉它们后整个链表就是空链表，所以直接return nullptr；

如果head->next->next存在：说明这两个重复结点后还不是终点。

那么接下来要判断这两个重复结点之后的结点是否仍然与它们重复。

如果不重复的话，那直接不管这两个重复的结点，递归计算以head->next->next为头结点的符合要求的新链表并返回即可。

如果这俩重复结点后面的结点还和他们是重复的，那后移一位，递归计算以head->next为头结点的符合要求的新链表并返回。

如果不等，那就说明head与head->next不重复，那么head仍然是新链表的头结点。
随后应用递归，将head->next作为下一次接受检查链表的头指针，删除其中的重复元素，并将新得到的链表接在head的后面。
随后返回head即可

C++ 代码

class Solution {
public:
    ListNode* deleteDuplication(ListNode* head) {
        if(head==nullptr||head->next==nullptr)
            return head;
        if(head->val==head->next->val){
            if(head->next->next==nullptr)return nullptr;
            if(head->next->next->val!=head->next->val)
                return deleteDuplication(head->next->next);
            else
                return deleteDuplication(head->next);
        }
        else {
            head->next=deleteDuplication(head->next);
            return head;
        }
    }
};

活动打卡代码 AcWing 66. 两个链表的第一个公共结点

nonstop
1天前

                class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
        int dist;
        ListNode*tag1=shorter(headA,headB,dist),*tag2;
        if(tag1==headA)tag2=headB;
        else tag2=headA;
        ListNode*t=tag2;
        while(t!=nullptr){
            t=tag2;
            for(int i=0;i<dist;i++){
                if(t!=nullptr)t=t->next;
            }
            if(tag1==t)return t;
            else {
                tag1=tag1->next;
                tag2=tag2->next;
            }
        }
    }
    ListNode*shorter(ListNode*headA,ListNode*headB,int &sum){
        int suma=0,sumb=0;
        ListNode*ta=headA,*tb=headB;
        while(headA!=nullptr||headB!=nullptr){
            if(headA!=nullptr){
                headA=headA->next;
                suma++;
            }
            if(headB!=nullptr){
                headB=headB->next;
                sumb++;
            }
        }
        sum=suma>=sumb?suma-sumb:sumb-suma;
        return suma>=sumb?tb:ta;
    }
};
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

            

活动打卡代码 AcWing 35. 反转链表

nonstop
1天前

                class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==nullptr){
            return head;

        }else if(head->next==nullptr||head==nullptr)
            return head;
        ListNode *t=reverseList(head->next);
        head->next->next=head;
        head->next=nullptr;
        return t;
    }
};
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

            

题解 AcWing 87. 把字符串转换成整数

nonstop
2天前

题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    int strToInt(string str) {
        string s2="";
        int len=0;
        bool tag=true;
        int a=0,result;
        for(int i=0;i<str.length();i++){
            if(str[i]!=' '&&str[i]=='-'){tag=false;a=i+1;break;}
            else if(str[i]=='+'){a=i+1;break;}
        }
        //if(a!=0)a+=1;
        for(int i=a;i<str.length();i++){
            if(str[i]>='0'&&str[i]<='9'){
                s2+=str[i];len++;
            }
            else break;
            /*
            if(str[i]>='0'&&str[i]<='9'&&(i+1==str.length()||(str[i+1]<'0'||str[i+1]>'9'))){
                if(len>s2.length()){
                    s2=s1;len=0;
                }
                else;
            }
            */
        }
        if(s2.length()==0)return 0;
        else if(s2.length()>=10){
            if(s2.length()>10)
                if(tag == false) return -2147483648;
                else return 2147483647;
            else{
                if(214748364<conINT(s2.substr(0,9))){
                     if(tag == false) return -2147483648;
                     else return 2147483647;
                }
                else if(214748364>=conINT(s2.substr(0,9))){
                    if(s2[9]<'8'){
                        if(tag == false) return -conINT(s2);
                        else return conINT(s2);
                    }
                    else if(s2[9]=='8'){
                        if(tag==false) return -2147483648;
                        else return 2147483647;
                    }
                    else{
                        if(tag == false) return -2147483648;
                        else return 2147483647;
                    }
                }
            }

        }
        else {
            if(tag == false) return -conINT(s2);
            else return conINT(s2);
        }

    }
    int conINT(string str){
        int result=0;
        for(int i=0;i<str.length();i++){
            result=result*10+((int)str[i]-48);
        }
        return result;
    }

};

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

活动打卡代码 AcWing 87. 把字符串转换成整数

nonstop
2天前

                class Solution {
public:
    int strToInt(string str) {
        string s1="",s2="";
        int len=0;
        bool tag=true;
        int a,result;
        for(int i=0;i<str.length();i++){
            if(str[i]=='-'){tag=false;a=i;break;}
        }
        for(int i=a;i<str.length();i++){
            if(str[i]>='0'&&str[i]<='9'){
                s1+=str[i];len++;
            }
            if(str[i]>='0'&&str[i]<='9'&&(i+1==str.length()||(str[i+1]<'0'||str[i+1]>'9'))){
                if(len>s2.length()){
                    s2=s1;len=0;
                }
                else;
            }
        }
        if(s2.length()==0)return 0;
        else if(s2.length()>=10){
            if(s2.length()>10)
                if(tag == false) return -2147483648;
                else return 2147483647;
            else{
                if(214748364<conINT(s2.substr(0,9))){
                     if(tag == false) return -2147483648;
                     else return 2147483647;
                }
                else if(214748364<conINT(s2.substr(0,9))){
                    if(s2[9]<'8'){
                        if(tag == false) return -conINT(s2);
                        else return conINT(s2);
                    }
                    else if(s2[9]=='8'){
                        if(tag==false) return -2147483648;
                        else return 2147483647;
                    }
                    else{
                        if(tag == false) return -2147483648;
                        else return 2147483647;
                    }
                }
            }

        }
        else {
            if(tag == false) return -conINT(s2);
            else return conINT(s2);
        }

    }
    int conINT(string str){
        int result=0;
        for(int i=0;i<str.length();i++){
            result=result*10+((int)str[i]-48);
        }
        return result;
    }

};
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

            

活动打卡代码 AcWing 78. 左旋转字符串

nonstop
9天前

                class Solution {
public:
    string leftRotateString(string str, int n) {
        string s1="";
        for(int i=n;i<str.length();i++)
            s1+=str[i];
        for(int i=0;i<n;i++)
            s1+=str[i];
        return s1;
    }
};
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

            

活动打卡代码 AcWing 36. 合并两个排序的链表

nonstop
13天前

                /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode*result=nullptr;
        ListNode*ret=nullptr;
        while(l1!=nullptr&&l2!=nullptr){
            if(l1->val<l2->val){
                if(result==nullptr){result=new ListNode(l1->val);ret=result;}
                else{ result->next=new ListNode(l1->val);result=result->next;}
                l1=l1->next;
            }
            else if(l1->val>l2->val){
                if(result==nullptr){result=new ListNode(l2->val);ret=result;}
                else {result->next=new ListNode(l2->val);result=result->next;}
                l2=l2->next;
            }
            else if(l1->val==l2->val){
                if(result==nullptr){result=new ListNode(l1->val);ret=result;result->next=new ListNode(l2->val);result=result->next;}
                else {result->next=new ListNode(l1->val);result=result->next;result->next=new ListNode(l2->val);result=result->next;}
                l1=l1->next;
                l2=l2->next;
            }
        }
        if(l1==nullptr){
            while(l2!=nullptr){
                if(result==nullptr){result=new ListNode(l2->val);ret=result;}
                else{
                result->next=new ListNode(l2->val);
                result=result->next;

                }l2=l2->next;
            }
        }
        else if(l1==nullptr&&l2==nullptr);
        else{
            while(l1!=nullptr){
                if(result==nullptr){result=new ListNode(l1->val);ret=result;}
                else{
                result->next=new ListNode(l1->val);
                result=result->next;

                }l1=l1->next;
            }
        }
        return ret;
    }
};
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

            

活动打卡代码 AcWing 28. 在O(1)时间删除链表结点

nonstop
13天前

                class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val=node->next->val;
        ListNode *trash=node->next;
        node->next=node->next->next;
        delete trash;
    }
};
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

            

活动打卡代码 AcWing 16. 替换空格

nonstop
14天前

                class Solution {
public:
    string replaceSpaces(string &str) {
        int n=str.length();
        string result="";
        string add="%20";
        for(int i=0;i<n;i++){
            if(str[i]==' '){
                result+=add;
                continue;
            }
            else result+=str[i];
        }
        return result;
    }
};
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

            

0 评论

递归算法

算法描述：

C++ 代码

0 评论

0 评论

0 评论

题目描述

样例

算法1

(暴力枚举) $O(n^2)$

时间复杂度

参考文献

C++ 代码

算法2

(暴力枚举) $O(n^2)$

时间复杂度

参考文献

C++ 代码

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论