今天是2023年10月31号，前段时间由于实习、科研、课业的多重压力和时间占用，刷题已经停滞了许久。目前刷题量是 340 道。在此立下flag，从今天起每天整理一道题。无他，唯手熟尔！

147. 链表的插入排序

2023.11.1 晚

题目

给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。

插入排序 算法的步骤:

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。

分析

首先复习一下 插入排序 ，对于一个数组，插入排序就是从左往右遍历数组，把遍历到的新的数插入到他应该在的位置。由于当前数字左边的数组是已经排好序的，所以可以用二分查找优化时间复杂度o(nlogn) 。

而链表的插入排序有所不同，我们需要在排好序的链表中从左往右依次寻找它应该插入的位置。

这里有几个需要注意的点：

首先需要想到一个最简单的点：如果当前元素（cur）大于前面链表的最后一个元素（lastSorted），那么指针全部右移一个，左边的又是排好序的链表。
当前需要处理的元素 cur 被插入后，下个元素应当如何寻找？就是 lastSorted->next ！
我们需要找到最后一个比cur小的节点，所以在写while循环时应该找 p->next->val，即 while(p->next->val <= cur->val)。

代码

/**
 * 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* insertionSortList(ListNode* head) {
        ListNode* preHead = new ListNode(0, head);
        ListNode* lastSorted = head, *cur = head->next;
        while(cur != nullptr) {
            if(lastSorted->val <= cur->val) {
                lastSorted = lastSorted->next; cur = cur->next;
            } else {
                ListNode* p = preHead;
                while(p->next->val <= cur->val) {
                    p = p->next;
                }
                lastSorted->next = cur->next;
                cur->next = p->next;
                p->next = cur;
            }
            cur = lastSorted->next;
        }
        return preHead->next;
    }
};

148. 排序链表

2023.11.2 晚

题目

给你链表的头结点 head ，请将其按升序排列并返回 排序后的链表 。

分析

这道题和链表的插入排序连在一起，肯定不是继续让我们用插入排序。这里有时间复杂度更低的方法，就是归并排序，利用分治思想解题。

今天晚上先实现一个比较好理解的 自顶向下的归并排序。

自顶向下的归并排序

大概想法都无需解释。就是一级级 找到中点 向下拆分，然后化成一个个合并两个有序链表的问题。

这里需要注意一个问题：

首先就是写递归不要忘记开头的特殊情况处理。特别是
1
2
3
4
if(head->next == tail) { head->next = nullptr; return head; }
当head->next == tail的时候，这个时候说明目前需要排序的只有一个节点。（对于前半段的，迭代的head1，head2 前闭后开，head2其实是后一段的头节点；对于尾部的，tail就是nullptr。）此时把这段断开，返回head即可。说白了就是自顶向下的最底下的情况，只需要断开并返回即可。
其他需要注意的问题不多，只要思路清晰把问题拆分成 找中点并截断以及合并两个有序链表两个问题即可。

自底向上的归并排序

这个方法稍微复杂一点，前一种方法使用递归，空间复杂度为o(logn)。如果在原链表上进行修改，可以优化空间复杂度为o(1)。这就要我们自底向上进行分治。

怎么分治呢？还是从1个节点开始，合并有序链表，合并成2个节点的链表后，再合成4个节点的...以此类推...

所以需要一个int来记录现在正在合并链表的长度，从1开始直到超过 链表长度。

首先需要计算链表长度，开始for(sublen = 1; sullen < Len; sublen <<= 1) {}的迭代
对于sublen长度的迭代，需要找到 head1，再找到 head2并断开，记录 pre 以连接mergeList(head1, head2)得到的头节点，以及利用 cur 来记录目前遍历到的位置。

代码

自顶向下的归并排序

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        return sortList(head, nullptr);
    }
    ListNode* sortList(ListNode* head, ListNode* tail) {
      //首先对特殊情况处理
        if(head == nullptr) {
            return head;
        }
        if(head->next == tail) {
            head->next = nullptr;
            return head;
        }
      //快慢指针找中点
        ListNode* slow = head, *fast = head;
        while(fast != tail && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return mergeList(sortList(head, slow), sortList(slow, tail));
    }

    ListNode* mergeList(ListNode* head1, ListNode* head2) {
      //同样注意特殊情况
        if(head2 == nullptr) {
            return head1;
        }
        ListNode* preHead = new ListNode(0);
        ListNode* cur = preHead, *cur1 = head1, *cur2 = head2;
        while(cur1 != nullptr && cur2 != nullptr) {
            if(cur1->val < cur2->val) {
                cur->next = cur1;
                cur1 = cur1->next;
            } else {
                cur->next = cur2;
                cur2 = cur2->next;
            }
            cur = cur->next;
        }
        cur->next = cur1 == nullptr? cur2:cur1;
        return preHead->next;
    }
};

自底而上的归并排序

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        int length = 0;
        ListNode* preHead = new ListNode(0);
        preHead->next = head;
        ListNode* node = head;
        while(node!=nullptr) {
            length++;
            node=node->next;
        }
        for(int sublen = 1; sublen < length; sublen <<= 1) {
            ListNode* pre = preHead, *cur = preHead->next;
            // 开始一轮排序
            while(cur!=nullptr) {
                ListNode* head1 = cur;
                for(int i = 1; i < sublen&&cur->next!=nullptr; ++i) {
                    cur = cur->next;
                }
                //找到head2并断开,此时cur指向尾部节点
                ListNode* head2 = cur->next;
                cur->next = nullptr;
                cur = head2;
                //找到尾部节点
                for(int i = 1; i < sublen && cur!=nullptr; ++i) {
                    cur = cur->next;
                }
                //确定next节点
                ListNode* next = nullptr;
                if(cur != nullptr) {
                    next = cur->next;
                    cur->next = nullptr;
                }

                ListNode* merged = mergeList(head1, head2);
                // 把排序后的与前面的pre相连
                pre->next = merged;
                //找到排序后的尾部节点，即为下一次的pre
                while(pre->next!=nullptr) {
                    pre = pre->next;
                }
                cur = next;
            }
        }
        return preHead->next;
    }

    ListNode* mergeList(ListNode* head1, ListNode* head2) {
        if(head2 == nullptr) {
            return head1;
        }
        ListNode* preHead = new ListNode(0);
        ListNode* cur = preHead, *cur1 = head1, *cur2 = head2;
        while(cur1 != nullptr && cur2 != nullptr) {
            if(cur1->val < cur2->val) {
                cur->next = cur1;
                cur1 = cur1->next;
            } else {
                cur->next = cur2;
                cur2 = cur2->next;
            }
            cur = cur->next;
        }
        cur->next = cur1 == nullptr? cur2:cur1;
        return preHead->next;
    }
};

123.买卖股票的最佳时机III

题目

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

分析

进阶级的动态规划问题。前两个版本都比较简单，第一个简单版本只要记录当前最低价以及最大利润，遍历更新即可。第二个用贪心的思想，根据当前价格与最低价的关系处理即可。

这是第三个版本，限制了交易次数，如何解决呢？

基本思想是每一天的状态有 4 个：第一次买进，第一次卖出，第二次买进，第二次卖出。

代码

实现 LRU。

实现一个 Hash 表。

最大频率栈。

归并排序。

快速排序。

非递归的中序排序。

用两个栈模拟队列。

树的层序 S 形遍历。

合并 K 个有序链表。

开发

#算法 #leetcode

LeetCode刷题整理

http://example.com/2023/10/31/LeetCode刷题整理/

作者

Melrose Wei

发布于

2023年10月31日

许可协议

MIT6.824 lab3 容错kv服务项目记录上一篇

MIT6.824 lab2 raft 项目记录下一篇