美文网首页
刷题记录（链表题为主）

刷题记录（链表题为主）

作者: 锦绣拾年 | 来源:发表于2021-10-14 22:47 被阅读0次

    刷题记录

    LeetCode

    lc22 左右括号

    数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

有效括号组合需满足：左括号必须以正确的顺序闭合。

 

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：

输入：n = 1
输出：["()"]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    常见的递归边界判断题。也是常见的类似于dfs搜索题。

    1. 左括号有，可以抵消，这时可以有抵消掉，也可以不抵消两种情况。
    2. 增加左括号。
    class Solution {
public:

    void getstring(vector<string>& res,int index,string first,int left,int right){
            if(first.size()==index*2){
                res.push_back(first);
                return;
            }
            if(left>0){//未抵消左括号>0
                first = first +')';
                left-=1;
                // right-=1;
                getstring(res,index,first,left,right);
                first = first.substr(0,first.size()-1);
                left+=1;

            }
            
            
            if(right<index){//左括号使用数目<index
                first = first+'(';
                right+=1;
                left+=1;
                getstring(res,index,first,left,right);
            }
            
            //cout<<first<<endl;
            // first = first.substr(0,first.size()-1);
        return;
    }
    vector<string> generateParenthesis(int n) {
        int left=1;
        int right=1;
        string first = "(";
        vector<string> res;
        getstring(res,n,first,left,right);
        return res;


    }
};

    但是我写的不如↓题解干练

    奇妙的知识点string也是容器，可以使用 push_back和pop_back

    class Solution {
    void backtrack(vector<string>& ans, string& cur, int open, int close, int n) {
        if (cur.size() == n * 2) {
            ans.push_back(cur);
            return;
        }
        if (open < n) {
            cur.push_back('(');
            backtrack(ans, cur, open + 1, close, n);
            cur.pop_back();
        }
        if (close < open) {
            cur.push_back(')');
            backtrack(ans, cur, open, close + 1, n);
            cur.pop_back();
        }
    }
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        string current;
        backtrack(result, current, 0, 0, n);
        return result;
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/generate-parentheses/solution/gua-hao-sheng-cheng-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

    另一种思路：

    https://leetcode-cn.com/problems/generate-parentheses/solution/gua-hao-sheng-cheng-by-leetcode-solution/540232
class Solution {
        List<String> res = new ArrayList<>();
        public List<String> generateParenthesis(int n) {
            if(n <= 0){
                return res;
            }
            getParenthesis("",n,n);
            return res;
        }

        private void getParenthesis(String str,int left, int right) {
            if(left == 0 && right == 0 ){
                res.add(str);
                return;
            }
            if(left == right){
                //剩余左右括号数相等，下一个只能用左括号
                getParenthesis(str+"(",left-1,right);
            }else if(left < right){
                //剩余左括号小于右括号，下一个可以用左括号也可以用右括号
                if(left > 0){
                    getParenthesis(str+"(",left-1,right);
                }
                getParenthesis(str+")",left,right-1);
            }
        }
    }

    链表类：

    1）增加头结点。

    2）设置tmpListNode，存放临时

    lc21&lc23 合并（两个&多个）有序链表

    lc24两两交换链表（链表类）

    【链表类】（有些可以用map做）

    给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

    你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

    【我做链表题就会不停地数开头结尾节点，就会搞得很复杂】

    1.用递归的方法，就会很简单

    /**
 * 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) {
        if(!head || !head->next){
            return head;
        }
        ListNode* newnode= head->next;
        head->next=swapPairs(newnode->next);//后面的需要swap
        newnode->next=head;//交换开头的两个节点
        return newnode;

    }
};

    (自己写的很复杂，官方写的就多定义一个)

    class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;
        while (temp.next != null && temp.next.next != null) {
            ListNode node1 = temp.next;
            ListNode node2 = temp.next.next;
            temp.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            temp = node1;
        }
        return dummyHead.next;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs/solution/liang-liang-jiao-huan-lian-biao-zhong-de-jie-di-91/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

    /**
 * 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) {
        if(!head || !head->next){
            return head;
        }
        ListNode* left =head;
        ListNode* right = head->next;
        ListNode* third = head->next->next;
        ListNode* newhead=new ListNode(0,head);
        ListNode* curhead = newhead;
        while(left && right){
            left->next=third;
            right->next=left;
            curhead->next=right;

            if(third&&third->next){
                curhead=left;
                left=third;
                right=third->next;
                third=third->next->next;
                
            }else{
                break;
            }

        }
        return newhead->next;

    }
};

    lc25 k个一组翻转链表（链表）

    一个简单的想法。

    1）先写一个翻转链表的函数。

    2）然后把需要翻转的值送进去。

    class Solution {
public:
    // 翻转一个子链表，并且返回新的头与尾
    pair<ListNode*, ListNode*> myReverse(ListNode* head, ListNode* tail) {
        ListNode* prev = tail->next;
        ListNode* p = head;
        while (prev != tail) {
            ListNode* nex = p->next;
            p->next = prev;
            prev = p;
            p = nex;
        }
        return {tail, head};
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* hair = new ListNode(0);
        hair->next = head;
        ListNode* pre = hair;

        while (head) {
            ListNode* tail = pre;
            // 查看剩余部分长度是否大于等于 k
            for (int i = 0; i < k; ++i) {
                tail = tail->next;
                if (!tail) {
                    return hair->next;
                }
            }
            ListNode* nex = tail->next;
            // 这里是 C++17 的写法，也可以写成
            // pair<ListNode*, ListNode*> result = myReverse(head, tail);
            // head = result.first;
            // tail = result.second;
            tie(head, tail) = myReverse(head, tail);
            // 把子链表重新接回原链表
            pre->next = head;
            tail->next = nex;
            pre = tail;
            head = tail->next;
        }

        return hair->next;
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group/solution/k-ge-yi-zu-fan-zhuan-lian-biao-by-leetcode-solutio/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

    lc92 &lc 206 反转链表（链表）

    1.迭代

    class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/reverse-linked-list/solution/fan-zhuan-lian-biao-by-leetcode-solution-d1k2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

    2.递归(依然可以用递归)

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

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/reverse-linked-list/solution/fan-zhuan-lian-biao-by-leetcode-solution-d1k2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

    206.设定了左右边界

    需要想清楚，

    不变的位置（左节点，右节点），需要反转的一小段（记录反转）。

    /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode* pre = new ListNode(-1);
        pre->next=head;
        ListNode* pree =pre;
        
        if(m>=n)
            return head;
        if(!head||!head->next)
            return head;
        int index=0;
        while(index<m-1){
            pre=pre->next;
            index+=1;
        }
        
        ListNode* cur=pre->next->next;
        index+=2;
        
        ListNode* pret=pre->next;
        ListNode* fnext=nullptr;

        while(index<=n){
            fnext=cur->next;
            cur->next=pret;
            pret=cur;
            cur=fnext;
            index+=1;
            
        }
        pre->next->next=cur;
        pre->next=pret;

        
        
        return pree->next;
        
        

    }
};

    官方

    class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int left, int right) {
        // 设置 dummyNode 是这一类问题的一般做法
        ListNode *dummyNode = new ListNode(-1);
        dummyNode->next = head;
        ListNode *pre = dummyNode;
        for (int i = 0; i < left - 1; i++) {
            pre = pre->next;
        }
        ListNode *cur = pre->next;
        ListNode *next;
        for (int i = 0; i < right - left; i++) {
            next = cur->next;
            cur->next = next->next;
            next->next = pre->next;
            pre->next = next;
        }
        return dummyNode->next;
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/reverse-linked-list-ii/solution/fan-zhuan-lian-biao-ii-by-leetcode-solut-teyq/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

    lc61旋转链表（链表）

    思路：
    1）链表结尾和头部链接。
    2）依据模找到旋转开头的位置

    /**
 * 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* rotateRight(ListNode* head, int k) {
        
        if(!head||!head->next){
            return head;
        }
        ListNode* cur=head;
        int len=1;
        while(cur->next){
            cur=cur->next;
            len+=1;
            
        }
        if(k%len==0){
            return head;
        }
        int rk = len-k%len;
        cur->next=head;
        int index=1;
        ListNode* newcur=head;
        while(index<rk){
            newcur=newcur->next;
            index+=1;
        }
        ListNode*res=newcur->next;
        newcur->next=NULL;
        return res;
    }
};

    lc109 有序链表转成二叉搜索树

    重点：思考到如何递归

    /**
 * 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) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* resort(vector<int>& a,int left,int right){
        TreeNode* tmp;
        if(left>right)
            return NULL;
        if(left==right){
            tmp=new TreeNode(a[left],NULL,NULL);
            return tmp;
        }
        int mid=(left+right)/2;
        tmp=new TreeNode(a[mid]);
        tmp->left=resort(a,left,mid-1);
        tmp->right=resort(a,mid+1,right);
        return tmp;
    }
    
    TreeNode* sortedListToBST(ListNode* head) {
        //想先放在vector中，取数方便
        vector<int> mm;
        while(head){
            mm.push_back(head->val);    
            head=head->next;
        }
        TreeNode* res=resort(mm,0,mm.size()-1);
        return res;
        
        
        
        
    }
};

    lc 143 重排链表。

    1.简单的想法，使用数组结构储存链表（但我在合并时写法有点冗余，其实可以直接用while双指针方式合并）
    2.第二种，先快慢指针找到链表中点，然后反转链表后半部分，然后合并两个链表。

    /**
 * 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:
    
    void trans(int l,vector<ListNode*> & a){
        if(l*2==a.size()-1){
            a[l]->next=NULL;
            return;
        }
        if(l*2+1==a.size()-1){
            a[l+1]->next=NULL;
            return;
        }
        a[l]->next=a[a.size()-l-1];
        if(l+1<a.size()){
            a[a.size()-l-1]->next=a[l+1];
        }
        return;
    }
    void reorderList(ListNode* head) {
        //可以用map，然后改一下
        if(!head)
            return;
        vector<ListNode*> a;
        ListNode* tmp=head;
        while(tmp){
            a.push_back(tmp);
            //index+=1;
            tmp=tmp->next;
        }
        for(int i=0;i<=(a.size()-1)/2;i++){
            trans(i,a);
            
        }
        //return a[0];

    }
};

    lc29两数相除

    位运算
1 位逻辑运算符：

      & （位   “与”）  and
      ^  （位   “异或”）
      |   （位    “或”）   or
      ~  （位   “取反”）
2 移位运算符：
      <<（左移）
      >>（右移）

优先级
位“与”、位“或”和位“异或”运算符都是双目运算符，其结合性都是从左向右的，优先级高于逻辑运算符，低于比较运算符，且从高到低依次为&、^、|

    涉及到位运算的，还有数组题。

    lc31下一个排列

    lc33

    KMP
    DFS
    JSON解析

    相关文章

      网友评论

          本文标题：刷题记录（链表题为主）

          本文链接：https://www.haomeiwen.com/subject/cqlpoltx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|刷题记录（链表题为主）|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！