LeetCode 刷题笔记（七）

写完了CPP版tinyhttpd，过来刷会儿题

这次的主题是回溯和链表

ID:46

思路历程：

今天看了代码随想录的视频，介绍了回溯算法的基本思路

就是递归中，判断边界

然后遍历元素，处理数据，调用递归，撤销处理（回溯）

值得注意的是，回溯算法一般会用到set，如果不用set用vector的话，记得加一个状态数组

如下：

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

    void bkt(vector<int>& nums, vector<bool>& used) {
        if (sub_res.size() == nums.size()) {
            res.push_back(sub_res);
            return;
        }

        for (int i = 0; i < nums.size(); ++i) {
            if (!used[i]) {
                used[i] = true;
                sub_res.push_back(nums[i]);

                bkt(nums, used); // 递归调用

                // 回溯
                used[i] = false;
                sub_res.pop_back();
            }
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> used(nums.size(), false); // 初始化为未使用
        bkt(nums, used);
        return res;
    }
};

answer:(unordered_set)

class Solution {
public:
    vector<vector<int>>res;    
    vector<int>sub_res;
    void bkt(unordered_set<int> all_nums){
        if(all_nums.empty()){
            res.push_back(sub_res);
            return ;
        }
        for(auto iter=all_nums.begin();iter!=all_nums.end();++iter){
            int c=*iter;
            sub_res.push_back(c);
            unordered_set<int>temp=all_nums;
            temp.erase(c);
            bkt(temp);
            sub_res.pop_back();
        }
    }
    
    vector<vector<int>> permute(vector<int>& nums) {
        unordered_set<int>all_nums;
        for(auto c:nums)all_nums.insert(c);
        bkt(all_nums);
        return res;
    }
};

ID:78

思路历程：

感觉所谓的模板不能以偏概全

不一定会有遍历，返回和处理数据是必要的

子集可以是这样，我从数组头出发，选择要当前的或者不要，然后往后走（重新调用）

answer:

class Solution {
public:
    vector<vector<int>>res;
    vector<int>sub_res;
    void bkt(int now,vector<int>&nums,int n){
        if(now==n){
            res.push_back(sub_res);
            return;
        }
        sub_res.push_back(nums[now]);
        bkt(now+1,nums,n);
        sub_res.pop_back();
        bkt(now+1,nums,n);
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        int n=nums.size();
        bkt(0,nums,n);
        return res;
    }
};

ID:21

思路历程：

非常的简单，不要想复杂，拿出一格头节点和队列一样，一个个收进来就行

answer：

/**
 * 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* res=nullptr;
        ListNode* fin_res=nullptr;
        if(list1&&list2){
            fin_res=list1->val<=list2->val?list1:list2;
        }else{
            if(list1)fin_res=list1;
            if(list2)fin_res=list2;
            return fin_res;
        }
        ListNode*tmp;
        while(list1&&list2){
            if(list1->val<=list2->val){
                if(!res){
                    res=list1;
                }else{
                    res->next=list1;
                    res=res->next;
                }
                list1=list1->next;
            }else{
                if(!res){
                    res=list2;
                }else{
                    res->next=list2;
                    res=res->next;
                }
                list2=list2->next;
            }
        }
        if(list1)res->next=list1;
        if(list2)res->next=list2;
        return fin_res;
    }
};

ID:2

思路历程：

一开始我还是想的比较简单，一环环往后就行，遇到进位就记录，但到后面真有点恶心到了

上一轮的进位会影响到这一轮，应该先存节点，再考虑进位，不然会相互干扰

同时如果遇到有长短链表，建议先增长至一直，不要和我一样偷懒，加完一条后，再处理剩下那条

新思路中有一点要注意的是，补0节点时，最好从尾节点开始，而不是尾节点->next

answer:

/**
 * 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* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode*res=nullptr;
        ListNode*fin_res=nullptr;
        int flag=0;
        ListNode*head1=l1;ListNode*head2=l2;
        int length1=0,length2=0;
        while(head1->next){
            length1++;head1=head1->next;
        }
        while(head2->next){
            length2++;head2=head2->next;
        }
        if(l1->val==0&&length1==1)return l2;
        if(l2->val==0&&length2==1)return l1;
        while(length1<length2){
            head1->next=new ListNode(0);
            head1=head1->next;
            length1++;
        }
        while(length2<length1){
            head2->next=new ListNode(0);
            head2=head2->next;
            length2++;
        }
        if((l1->val+l2->val)/10)flag=1;
        res=new ListNode((l1->val+l2->val)%10);
        l1=l1->next;l2=l2->next;fin_res=res;
        while(l1&&l2){
            int sum=l1->val+l2->val+flag;//上个flag
            res->next=new ListNode(sum%10);
            if(flag)flag=0;
            l1=l1->next;l2=l2->next;res=res->next;
            if(sum>=10)flag=1;
        }
        if(flag)res->next=new ListNode(1);
        return fin_res;
    }
};

ID:19

思路历程：

思考起来会比较简单，遍历链表记录长度，然后获取要删除节点的下标，然后再次遍历处理即可

注意的点是如果要删除的是第一个节点，直接返回head->next即可

answer:

/**
 * 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) {
        int length=0;
        ListNode*tmp=head;
        while(tmp){
            length++;tmp=tmp->next;
        }
        tmp=head;ListNode* res;
        int idx=length-n;
        if(!idx){
            return head->next;
        }else{
            int i=0;
            while(i<idx-1){
                tmp=tmp->next;
                i++;
            }
            tmp->next=tmp->next->next;
        }
        return head;
    }
};

ID:24

思路历程：

有一说一，做完还是有点蒙，

总体思路是，每次遇到下标为奇数，就去交换位置，

换的时候，pre->next=back;now->next=back->next;back->next=now;

不换的时候 pre=now;now=now->next;back=now->next;

注意考虑第一个pre为nullptr的时候

answer:

/**
 * 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*pre=nullptr;
        ListNode*now;ListNode*back;ListNode*tmp=head;
        int length=0;
        while(tmp){
            length++;tmp=tmp->next;
        }
        if(length<=1)return head;
        std::cout<<length<<std::endl;
        tmp=head;now=head;back=head->next;
        int i=1;
        ListNode* res;
        while(i<length){
            i++;
            if(i%2==0){
                if(pre){
                    pre->next=back;
                    now->next=back->next;
                    back->next=now;
                }else{
                    now->next=back->next;
                    back->next=now;
                    pre=back;
                    back=now->next;
                }
                if(i==2)res=pre;
                continue;
            }
            pre=now;
            now=now->next;
            back=now->next;
        }
        return res;
    }
};

ID:138

思路历程：

next指针拷贝非常简单，主要问题在于random怎么实现深拷贝

我一开始想的是，存下标，自定义一个计数器，然后用map存两边的下标，就能实现再次遍历的时候深拷贝random

但问题在于，我拷贝下标是不够的，因为我random指向的是指针而不是下标，所以优化一下

我们选择存两边对应的地址（指针）那么我只要再次遍历时，取出原节点的random，然后放入map，就可以拿到本节点的random地址

answer:

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head)return NULL;
        Node*tmp=head;tmp=tmp->next;
        Node*res=new Node(head->val);
        Node*node=res;
        map<Node*,Node*> ptr_hash;//存下标和映射下标
        ptr_hash.insert({head,res});
        while(tmp){
            node->next=new Node(tmp->val);
            node=node->next;
            ptr_hash.insert({tmp,node});
            tmp=tmp->next;
        }
        tmp=head;node=res;
        while(tmp){
            node->random=ptr_hash[tmp->random];
            node=node->next;
            tmp=tmp->next;
        }
        return res;
    }
};

ID:148

思路历程:

如果不考虑空间和时间复杂度会很简单，但如果考虑的话，就比较麻烦了

比如说用到归并排序的思想，就能实现O(nlogn)时间复杂度和O(logn)空间复杂度

answer（暴力）:

/**
 * 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* sortList(ListNode* head) {
        if(!head)return nullptr;
        ListNode*node =head;
        vector<int> nums;
        while(node){
            nums.push_back(node->val);
            node=node->next;
        }
        sort(nums.begin(),nums.end());
        ListNode*res=nullptr;
        ListNode*fin;
        for(auto c:nums){
            if(!res){
                res=new ListNode(c);
                fin=res;
            }else{
                res->next=new ListNode(c);
                res=res->next;
            }
        }
        return fin;
    }
};

继续加油，许愿快速OC