21 合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

21.1 思路

经典的二路归并算法【也是归并算法的核心】
每次看剩余的链表的第一个元素。把比较小的拿到结果上去就行了。

思想：每次找到剩余的数的最小值。为了方便，开一个虚拟头结点。所有需要特判头结点，或者头结点会改变的都可以开~。

21.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* mergeTwoLists(ListNode* l1, ListNode* l2) {
        auto dummy = new ListNode(-1), tail = dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                tail = tail->next = l1;
                l1 = l1->next;
            } else {
                tail = tail->next = l2;
                l2 = l2->next;
            }
        }
        if (l1) tail->next = l1;
        if (l2) tail->next = l2;
        return dummy->next;
    }
};

22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3 输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]

22.1 思路

括号都是完美匹配的，并列嵌套都是可以的。、
之前判断括号序列合法不合法已经判断过了。栈，
只有小括号，所有不存在匹配的问题。

只要碰到右括号的情况下，栈非空就行。

合法的判定。（只适用于一类括号）

任意前缀中，“(” 数量 >= “)”数量
左右括号数量相等。【这里一定满足】

如果只求数量：卡特兰数~

输出方案用dfs就行了。递归搜索树考虑~，可以一位一位考虑。

只要左括号有就可以填左括号。
右括号只要有并且左括号数量严格大于右括号数量，就可以填右括号。

时间的复杂度：方案的数量：卡特兰数 * 每个方案的时间复杂度（2n）

22.2 代码

class Solution {
public:

    vector<string> ans;

    vector<string> generateParenthesis(int n) {
        dfs(n, 0, 0, "");
        return ans;
    }
    // lc 左括号的数量，rc：右括号的数量，seq当前的序列。
    void dfs(int n, int lc, int rc, string seq) {
        if (lc == n && rc == n) ans.push_back(seq);
        else {
            // 有左括号，就能加。
            if (lc < n) dfs(n, lc + 1, rc, seq + '(');
            // 左括号的数量大于右括号的数量，就可以加右括号。
            if (rc < n && lc > rc) dfs(n, lc, rc + 1, seq + ')');
        }
    }
};

23. 合并k个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5-6

23. 1 思路

k路归并。

一个直观的想法就是分治法，
可以用堆来找最小值【存k个指针】，时间复杂度nlogk。

23.2 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:

    struct Cmp {
        // 小根堆。
        bool operator() (ListNode* a, ListNode* b) {
            return a->val > b->val;
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, Cmp> heap;
        auto dummy = new ListNode(-1), tail = dummy;
        for (auto l : lists) //必须要判空一下。
            if (l) heap.push(l);

        while (heap.size()) {
            auto t = heap.top();
            heap.pop();

            tail = tail->next = t;
            if (t->next) heap.push(t->next);
        }

        return dummy->next;
    }
};

24.两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

24.1 思路

新链表原链表的头结点会变，所以开一个虚拟头结点。
每次枚举两个节点，交换这两个节点。

前面那个指针放在要交换的两个节点的前面。

还是要画图~~~

24.2 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        // 建立虚拟头结点。
        auto dummy = new ListNode(-1);
        dummy->next = head;
        // p 是交换节点的前一个节点。要交换的两个节点都要不为null
        for (auto p = dummy; p->next && p->next->next;) {
            auto a = p->next, b = a->next;
            p->next = b;
            a->next = b->next;
            b->next = a;
            p = a;
        }

        return dummy->next;
    }
};

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/347847/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

25. k个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

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

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

25.1 思路

头结点会变-> 虚拟头结点。

每次指向要交换的元素的前一个节点，先判断一下后面是否足够k个。

k个节点内部的边反向
前面连接的指针变一下。
后面连接的指针变一下。

每个点都会遍历常数次，所以时间复杂度是线性的

25.2 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        // 虚拟头结点
        auto dummy = new ListNode(-1);
        dummy->next = head;

        for (auto p = dummy;;) {
            auto q = p;
            // 先遍历一下有无k各元素。
            for (int i = 0; i < k && q; i ++ ) q = q->next;
            if (!q) break;

            // a指向每组的第一个元素，b指向每组的第二个元素。
            auto a = p->next, b = a->next;
            // 交换k-1条边。内部边反转。
            for (int i = 0; i < k - 1; i ++ ) {
                auto c = b->next;
                b->next = a;
                a = b, b = c;
            }

            // c是反转的一组的链表的最后一个节点
            auto c = p->next;
            p->next = a, c->next = b;
            p = c;
        }
        return dummy->next;
    }
};

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/347863/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

26. 删除有序数组中的重复项。

给你一个升序排列的数组 nums ，请你原地（不能开数组，不能写递归）删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = […]; // 输入数组
int[] expectedNums = […]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
如果所有断言都通过，那么您的题解将被通过。

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

26.1 思路

找到所有第一次出现的数，也就是说如果碰到一个数和他前面的数相同，就不要。

算法

Week2 21~30

21 合并两个有序链表

21.1 思路

21.2 代码

22. 括号生成

22.1 思路

22.2 代码

23. 合并k个升序链表

23. 1 思路

23.2 代码

24.两两交换链表中的节点

24.1 思路

24.2 代码

25. k个一组翻转链表

25.1 思路

25.2 代码

26. 删除有序数组中的重复项。

26.1 思路

26.2 代码