刷题记录（链表题为主）

刷题记录

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解析

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 203,456评论 5赞 477
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,370评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,337评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,583评论 1赞 273
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,596评论 5赞 365
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,572评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,936评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,595评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,850评论 1赞 297
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,601评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,685评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,371评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,951评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,934评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,167评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 43,636评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,411评论 2赞 342

推荐阅读更多精彩内容

  • 刷题记录--综合
    * Always remember to check the quality/availability of th...
    Morphiaaa阅读 714评论 0赞 0
  • LeetCode刷题记录
    第1天 Jewels and Stones （771） 题号771 Jewels and Stones 题目描述：...
    F嘉阳阅读 734评论 0赞 0
  • 目录
    字符串 题目内容解法3 Longest Substring Without Repeating Characte...
    jluemmmm阅读 178评论 0赞 0
  • LeetCode-每周刷题记录（2）
    Linked List 237Delete Node in a Linked List 题目：Write a fu...
    hahastrong阅读 206评论 0赞 0
  • 2019-11-28 173
    16宿命：用概率思维提高你的胜算 以前的我是风险厌恶者，不喜欢去冒险，但是人生放弃了冒险，也就放弃了无数的可能。 ...
    yichen大刀阅读 6,030评论 0赞 4