CodeTop每日刷题

从今天开始，我将每天坚持按CodeTop面试出现频度从高到低排序从第一题开始刷起，暂定每日刷两题。将会持续更新题解……

Day1(2.26)

Leetcode 3. 无重复字符的最长子串(Medium)

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

示例 1:

1
2
3
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

1
2
3
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

1
2
3
4
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
  请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

  • 0 <= s.length <= 5 * 104
  • s 由英文字母、数字、符号和空格组成

这道题我看了提示第一句：“Generate all possible substrings”被误导了（好吧是我理解的问题），我第一反应是从长到短遍历所有substrings，直到找到第一个不含重复字符的字符串，然后返回其长度：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            for (size_t len = s.length(); len > 0; len--) {
                for (size_t i = 0; i < s.length() - len + 1; i++) {
                    string substring = s.substr(i, len);
                    if (isUnique(substring)) {
                        return substring.length();
                    }
                }
            }
            return 0;
        }

    private:
        bool isUnique(string s) {
            unordered_set<char> set;
            for (char ch : s) {
                if (set.find(ch) != set.end()) {
                    return false;
                }
                set.insert(ch);
            }
            return true;
        }
};

然而这个算法时间复杂度是糟糕的O(n3)O(n^3)，连test都要超时，要更换思路。

我想到可以从左到右扫描字符串，用哈希表存储扫描到的字符和字符的最后出现位置(index)，用一个Sliding Window表示当前扫描到的无重复字符的substring。当遇到重复的字符且该字符在Sliding Window里面，那就需要更新Sliding Window的起始位置；否则的话检查当前的substring的长度是否超过了之前记录的最大长度maxlen，如果是那就更新maxlen。同时每扫描一个字符，都在哈希表中重新更新当前字符的最后出现位置。

这样的话只需要扫描一遍字符串，而在哈希表中通过key寻找值的时间复杂度是O(1)O(1)，因此总体的时间复杂度就是O(n)O(n)! 这就很快了！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution
{
    public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> charLastIndex;
        size_t start_pos = 0;   // Sliding window的起始位置
        size_t max_len = 0;
        for (size_t i = 0; i < s.size(); i++) {
            if (charLastIndex.find(s[i]) != charLastIndex.end() && charLastIndex[s[i]] >= start_pos) {
                // 如果当前字符在窗口内出现过，更新窗口的起始位置
                start_pos = charLastIndex[s[i]] + 1;
            } else {
                // 如果当前字符在窗口内没有出现过，检查当前窗口的长度是否是最大的
                max_len = max(max_len, i - start_pos + 1);
            }
            // 更新当前字符最后出现的位置
            charLastIndex[s[i]] = i;
        }
        return max_len;
    }
};

Leetcode 146. LRU缓存机制(Medium)

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1
  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

  • 1 <= capacity <= 3000
  • 0 <= key <= 10000
  • 0 <= value <= 105
  • 最多调用 2 * 105 次 get 和 put

这道题核心关键点在函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

get根据key要在常数项时间内得到value，唯一方法就是用哈希表unordered_map存储key-value，但是要evict的时候，单靠哈希表没办法获得LRU key。因此还需要一个数据结构能够在常数项时间内找到LRU key并删除他，同时也需要在访问key之后在常数项时间内重新排序key。要重新排序key，那就肯定要先删除这个key，再将其移动到别的位置。

也就是说，这个数据结构需要能够在常数项时间内删除任意位置的元素，那基本就锁定了，就是链表list!

但是list要在常数项时间内删除任意位置的元素，前提是你要给他指向这个元素的迭代器。 不然的话你通过key遍历链表找到要删除的元素那时间复杂度就是O(N)了。那有什么办法能够给定key，马上得到其在list中的迭代器呢？

那就只能在将key插入链表后，将指向key的迭代器也放入哈希表中。这样你就能通过key在哈希表中得知这个key在list中的位置，然后就能以常数项时间在list中删除key，并将其插入头/尾部了。

确定好数据结构后，实现起来就简单了。我的方法是将新访问/插入的key加到链表的末尾，同时如果key本身在链表中，还要先从当前位置删除，再加到链表末尾。而evict LRU就从链表的头部evict，你也可以将两者反过来，反正list是双端链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class LRUCache {
    public:
    LRUCache(int capacity) { capacity_ = capacity; }

    int get(int key) {
        auto it = lru_cache_.find(key);
        if (it == lru_cache_.end()) {
            return -1;
        }
        lru_list_.erase(it->second.first);
        lru_list_.push_back(key);
        it->second.first = --lru_list_.end();
        return it->second.second;
    }

    void put(int key, int value) {
        auto it = lru_cache_.find(key);
        if (it != lru_cache_.end()) {
            lru_list_.erase(it->second.first);
            lru_list_.push_back(key);
            it->second.first = --lru_list_.end();
            it->second.second = value;
        } else {
            if (cache_full()) {
                evict_lru();
            }
            lru_list_.push_back(key);
            lru_cache_[key] = {--lru_list_.end(), value};
        }
    }

    private:
    int capacity_;
    std::unordered_map<int, std::pair<std::list<int>::iterator, int>> lru_cache_;
    std::list<int> lru_list_;

    bool cache_full() { return lru_cache_.size() == capacity_; }

    void evict_lru() {
        int lru_key = lru_list_.front();
        lru_list_.pop_front();
        lru_cache_.erase(lru_key);
    }
};

Day2(2.27)

Leetcode 206. 反转链表(Easy)

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

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

示例 2：

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

示例 3：

1
2
输入：head = []
输出：[]

提示：

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

目标：分别用迭代和递归的方式解决这道题

迭代法

我的第一想法是一个个遍历head->next，重新创建一个新结点指向原来的头结点作为新的头结点，然后就将head->next删掉，删法就是让head->next指向head->next->next。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Iterative solution 1.
class Solution
{
    public:
    ListNode *reverseList(ListNode *head)
    {
        ListNode *new_head = head;

        while (head != NULL && head->next != NULL)
        {
            new_head = new ListNode(head->next->val, new_head);
            head->next = head->next->next;
        }

        return new_head;
    }
};

但是这样每遍历一个元素，就要多创建一个ListNode非常占用空间，怎么才能仅通过修改指针的方式就翻转整个链表？

答案是每遍历过去一个结点，用pre指针记录下这个结点。这样当遍历到下一个结点的时候，就可以将他的next指针指向pre。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Iterative solution 2 (better).
class Solution
{
    public:
    ListNode *reverseList(ListNode *head)
    {
        ListNode *pre = NULL;

        ListNode *p = head;
        while (p) {
            ListNode* next = p->next;
            p->next = pre;
            pre = p;
            p = next;
        }

        return pre;
    }
};

这样内存消耗就是O(1)复杂度。pre和p指针只要创建一个，随着遍历向后移动。

递归法

迭代法往往思路上更简洁优雅，这题也不例外。反转链表，本质上就是重新排序链表中的所有元素。迭代法的想法就是：

  1. 先翻转（排序）好头结点之后的所有元素，返回新的头结点
  2. 再将原本的头结点加到链表末尾
  3. 最后返回新的头结点

迭代结束的条件就是当前要排序的链表为空或元素个数为1，直接返回当前头结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Recursive solution.
class Solution
{
public:
    ListNode *reverseList(ListNode *head) {
        // 递归结束条件，返回新的头结点
        if (head == NULL || head->next == NULL) {
            return head;
        }

        ListNode *new_head = reverseList(head->next);

        head->next->next = head;
        head->next = NULL;

        return new_head;
    }
};

Leetcode 215. 数组中的第K个最大元素(Medium)

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

1
2
输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

1
2
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

  • 1 <= k <= nums.length <= 105
  • -104 <= nums[i] <= 104

这题非常好！可以复习快速排序和堆排序，尤其是快速排序的各种变型！

这道题核心是要求时间复杂度为 O(n)

快速选择

第一种选择：使用快速选择算法。快速选择与快速排序是同样的核心思想，但是快速选择不需要完全排序整个数组，只要在partition的过程中正好找到那个正确位置的pivot就可以了。

快速选择其实有现成的STL算法提供：

1
2
3
4
5
// 基本语法
nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);

// 带比较器的语法
nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);

nth_element能够将在正常排序后会位于指定位置nth的元素放在这个指定位置nth（默认的排序方式是从小到大，也可以自定义比较器。

那这题就秒掉了：

1
2
3
4
5
6
7
8
9
class Solution
{
public:
    int findKthLargest(vector<int> &nums, int k)
    {
        nth_element(nums.begin(), nums.begin() + nums.size() - k, nums.end());
        return nums[nums.size() - k];
    }
};

但是我头铁想要手撕快速选择：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// 手撕快速选择算法
// 随机选择pivot
class Solution {
    public:
    int findKthLargest(vector<int>& nums, int k) {
        return quickSelect(nums, 0, nums.size() - 1, k);
    }

    private:
    int quickSelect(vector<int>& nums, int left, int right, int K) {
        if (left == right) {
            return nums[left];
        }
        
        int pivotIndex = left + rand() % (right - left + 1);
        swap(nums[pivotIndex], nums[right]);

        int pivot_index = partition(nums, left, right);

        if (pivot_index == nums.size() - K) {
            return nums[pivot_index];
        }
        else if (pivot_index < nums.size() - K) {
            return quickSelect(nums, pivot_index + 1, right, K);
        }
        else {
            return quickSelect(nums, left, pivot_index - 1, K);
        }
    }

    int partition(vector<int>& nums, int left, int right) {
        int pivot = nums[right];
        int i = left;

        for (int j = left; j < right; ++j) {
            if (nums[j] <= pivot) {
                swap(nums[i], nums[j]);
                ++i;
            }
        }

        swap(nums[i], nums[right]);
        return i;
    }
};

这样随机选择pivot在大部分case（随机数据）情况下都是O(N)的时间复杂度，除了leetcode上最后一个test case：

这个test case包含有大量的重复数字，常规的随机选择pivot拼尽全力也无法战胜。leetcode官方题解为了应对这个精心构造的数据，用了双指针的方法用来在partition的时候快速向中间收敛。

修改后用随机选择pivot + 双指针的快速选择算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// 手撕快速选择算法
// 随机选择pivot + 双指针
class Solution {
    public:
    int findKthLargest(vector<int>& nums, int k) {
        return quickSelect(nums, 0, nums.size() - 1, k);
    }

    private:
    int quickSelect(vector<int>& nums, int left, int right, int K) {
        if (left == right) {
            return nums[left];
        }

        int pivotIndex = left + rand() % (right - left + 1);
        swap(nums[pivotIndex], nums[right]);

        int pivot_index = partition(nums, left, right);

        if (pivot_index == nums.size() - K) {
            return nums[pivot_index];
        }
        else if (pivot_index < nums.size() - K) {
            return quickSelect(nums, pivot_index + 1, right, K);
        }
        else {
            return quickSelect(nums, left, pivot_index - 1, K);
        }
    }

    int partition(vector<int>& nums, int left, int right) {
        int pivot = nums[right];
        int i = left - 1;
        int j = right;

        while (i < j) {
            // 从左向右找到第一个大于等于pivot的元素
            while (++i < right && nums[i] < pivot);
            // 从右向左找到第一个小于等于pivot的元素
            while (--j >= left && nums[j] > pivot);

            if (i < j) swap(nums[i], nums[j]);
        }

        swap(nums[i], nums[right]);
        return i;
    }
};

堆排序

也可以用堆排序算法。同样可以用STL中的priority_queue秒掉：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// STL priority_queue 堆排序算法
class Solution
{
public:
    int findKthLargest(vector<int> &nums, int k)
    {
        priority_queue<int> max_heap(nums.begin(), nums.end());

        for (int i = 0; i < k - 1; i++)
        {
            max_heap.pop();
        }

        return max_heap.top();
    }
};

建堆的时间复杂度是O(N), pop的时间复杂度是O(K * logN)，所以总复杂度还是O(N)符合要求。

但是一样，还是头铁，我要自己建堆！

建堆的过程就是从原先的vector对应的二叉树的最后一个非叶子节点作为根节点的子树开始调整，调整为大根堆，然后依次向上继续调整。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// 手撕堆排序算法
class Solution
{
public:
    int findKthLargest(vector<int> &nums, int k)
    {
        buildMaxHeap(nums);

        int heapSize = nums.size();
        for (int i = 0; i < k - 1; ++i) {
            nums[0] = nums[heapSize - 1];
            heapSize--;
            maxHeapify(nums, 0, heapSize);
        }

        return nums[0];
    }

private:
    void buildMaxHeap(vector<int> &nums) {
        int heapSize = nums.size();
        // 从最后一个非叶子节点为根节点的子树开始，将其调整为大根堆
        for (int i = heapSize / 2 - 1; i >= 0; --i) {
            maxHeapify(nums, i, heapSize);
        }
    }

    void maxHeapify(vector<int> &nums, int i, int heapSize) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;

        if (left < heapSize && nums[left] > nums[largest]) {
            largest = left;
        }
        if (right < heapSize && nums[right] > nums[largest]) {
            largest = right;
        }
        if (largest != i) {
            swap(nums[i], nums[largest]);
            maxHeapify(nums, largest, heapSize);
        }
    }
};

Day3(2.28)

Leetcode 25. K 个一组翻转链表(Hard)

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

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

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

示例 1：

img

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

示例 2：

img

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

提示：

  • 链表中的节点数目为 n
  • 1 <= k <= n <= 5000
  • 0 <= Node.val <= 1000

**进阶：**你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

递归

我第一个想到的办法是复用之前Leetcode 206. 反转链表(Easy)的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Recursive solution.
class Solution
{
public:
    ListNode *reverseList(ListNode *head) {
        // 递归结束条件，返回新的头结点
        if (head == NULL || head->next == NULL) {
            return head;
        }

        ListNode *new_head = reverseList(head->next);

        head->next->next = head;
        head->next = NULL;

        return new_head;
    }
};

我之前用递归的方法翻转一个链表。这题K个结点一组翻转链表无非就是翻转N/K个子链表。需要变化的点就是原先翻转后的链表末尾指向NULL，而这题中翻转后的子链表的末尾应该指向下一个子链表的头结点。并且递归条件从原本的head->next == NULL改成k == 1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 翻转一个从head开始K个结点的子链表，翻转后的链表末尾指向tail
// 返回翻转后的子链表的头结点
ListNode *reverseKList(ListNode *head, int k, ListNode *tail)
{
    // 递归结束条件，返回新的头结点
    if (k == 1)
    {
        return head;
    }

    ListNode *new_head = reverseKList(head->next, k - 1, tail);

    head->next->next = head;
    head->next = tail;

    return new_head;
}

有了这个helper function，下一步就是翻转一个个子链表(Group)然后让他们首尾相接就可以了。我还是用递归的方法实现reverseKGroup：

  1. 先翻转第一个Group之后的所有Group让他们首尾相接，返回翻转好的链表的头结点
  2. 再翻转第一个Group，并将翻转好的第一个Group的末尾指向后面翻转好的链表的头结点
  3. 最后返回新的头结点

要特别注意的是reverseKGroup递归的结束条件是当前要翻转的链表中的结点数量小于K（不到一个Group），这种情况就不进行翻转直接返回原先的头结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ListNode *reverseKGroup(ListNode *head, int k)
{
    ListNode *tail = head;
    int count = 0;
    while (tail != NULL && count < k )
    {
        tail = tail->next;
        ++count;
    }
    if (count < k) {
        return head;
    }

    tail = reverseKGroup(tail, k);
    head = reverseKList(head, k, tail);

    return head;
}

这个算法需要递归调用reverseKGroup N/K次，因此空间复杂度是O(N/K)。

那怎么才能实现进阶要求的O(1)空间复杂度呢？那reverseKGroup和reverseKList就不能用递归，得用迭代。

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution
{
public:
    // Iterative solution
    ListNode *reverseKGroup(ListNode *head, int k)
    {
        ListNode *dummy = new ListNode(0, head);

        ListNode* pre = dummy;
        while (head) {
            ListNode *tail = pre;
            for (int i = 0; i < k; ++i) {
                tail = tail->next;
                if (tail == NULL) {
                    return dummy->next;
                }
            }
            // 此时的tail就指向我们当前要翻转的子链表的尾结点
            ListNode *next  = tail->next;
            tie(head, tail) = reverseKList(head, tail);
            // 将翻转后的子链表接回原链表
            tail->next = next;
            pre->next = head;
            // 移动指针到下一个子链表的开头
            pre = tail;
            head = next;
        }

        return dummy->next;
    }

    // 翻转一个头结点为head，尾结点为tail的子链表
    // 返回翻转后的子链表的头结点和尾结点
    pair<ListNode*, ListNode*> reverseKList(ListNode *head, ListNode *tail)
    {
        ListNode *pre = tail->next;

        ListNode *p = head;
        while (pre != tail) {
            ListNode* next = p->next;
            p->next = pre;
            pre = p;
            p = next;
        }

        return {pre, head};
    }
};

我们每翻转完一个Group的子链表，将子链表的尾结点作为pre记录下来，这样当翻转完下一个子链表的时候就可以将翻转后的子链表接回去。

那第一个Group的子链表没有pre怎么办呢？难道要特殊处理吗？

我们这里用到了一个tricky的方法，在整个链表的头结点前加一个dummy node指向头结点，这的pre的初始值就是dummy，不需要特殊处理。这个dummy node还有一个好处就是当最后返回整个翻转后的链表的头结点的时候，dummy->next就正好是我们要找的头结点！一举两得！

这样实现我们只需要构造常数个变量，pre,head,tail指针都会跟着链表的遍历向后变化。

总结

从实现的思路上来看，我觉得递归法比迭代法更简洁直观，也更容易写对（不用dummy node这种trick）。但是从内存消耗上来说，迭代法只需要创建常量个变量，而递归法需要消耗栈空间。

Leetcode 15. 三数之和(Medium)

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

**注意：**答案中不可以包含重复的三元组。

示例 1：

1
2
3
4
5
6
7
8
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

1
2
3
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

1
2
3
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

  • 3 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

两数之和

这题是两数之和问题的扩展，因此我先做了两数之和问题：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

1
2
3
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

1
2
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

1
2
输入：nums = [3,3], target = 6
输出：[0,1]

提示：

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • 只会存在一个有效答案

**进阶：**你可以想出一个时间复杂度小于 O(n2) 的算法吗？

这题就很简单，因为题目前提是只会存在一个有效答案，因此不需要担心重复问题。只需要用一个哈希表存储每个元素值和其对应的index。这样就可以以O(1)的时间复杂度找到对应值的index。因此总体的时间复杂度就是遍历一遍nums的O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution
{
    public:
    vector<int> twoSum(vector<int> &nums, int target)
    {
        unordered_multimap<int, int> hashmap;
        for (int i = 0; i < nums.size(); i++)
        {
            hashmap.insert({nums[i], i});
        }

        vector<int> index;
        for (int i = 0; i < nums.size(); i++)
        {
            auto range = hashmap.equal_range(target - nums[i]);
            for (auto it = range.first; it != range.second; it++)
                // 找到第一个不是当前i的index
                if (it->second != i)
                {
                    index.push_back(i);
                    index.push_back(it->second);
                    return index;
                }
        }

        return index;
    }
};

然而此题三数之和问题如果沿用哈希表，先解决两数之和问题，再加上第三个数，就会得到大量的重复的三元组，还要用哈希表做去重操作，非常消耗时间和空间。因此需要更换思路。

三数之和：排序+双指针

三数之和这道题可以用双指针精妙地将原本三层遍历O(N3)O(N^3)的时间复杂度降到O(N2)O(N^2)​，具体的证明过程非常建议去看一下leetcode官方题解，讲得非常好！在这里我尝试简单说明一下：

首先我们要解决的是重复性问题，怎么才能保证不会得到重复的三元组？

我们仍需要使用三重循环，第一重大循环获取第一个数，第二、三重循环获取第二、三个数，我们只需要规定好每重循环枚举到的元素大小顺序就可以了。

具体来说，我们规定三重遍历中第二重循环枚举到的元素比第一重循环枚举到的元素大，第三重循环枚举到的元素比第二重循环枚举到的元素大，这样我们获得的三元组(a,b,c)(a, b, c)的大小顺序一定是a<=b<=ca <= b <= c。要实现这一点，我们就需要先对数组从小到大排序。同时，对数组从小到大排序后，我们每层循环时，就可以跳过相邻的重复元素。

解决了重复性问题，接下来就是怎么才能将原本的三重循环降到只需要遍历两次数组呢？

可以这样思考，一旦固定了第二个数，那么第三个数就唯一确定了。并且由于我们是从左到右（从小到大）遍历第二个数，那么我们可以同时从右到左遍历第三个数。一旦第三个数找到了，他右边的数就再也不会用到了（因为我们接下来遍历到的第二个数只会更大，所以以后只需要继续遍历这第三个数左边的数）。

到这里解法就很清晰了，要用左右双指针分别指向遍历到的第二个数和第三个数。左指针只需要向右遍历，右指针只需要向左遍历，因此第二、三重循环加起来只需要遍历一次数组。再加上第一层大循环，总的时间复杂度就变成了O(N2)O(N^2)！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution
{
    public:
    vector<vector<int>> threeSum(vector<int> &nums) {
        vector<vector<int> result;
        // 将nums数组从小到大排序
        nums.sort(nums.begin(), nums.end());

        for (int i = 0; i < nums.size(); ++i) {
            if (i != 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            // 定义双指针
            int l = i + 1;
            int r = num.size() - 1;
            int target = -nums[i];
            while (l < r) {
                // 如果
                // 1. 当前左指针指向的数与前一个数相同；
                // 2. 或者左右指针指向的数相加小于target(说明再向左移动右指针也不可能找到等于target的和了)；
                // 则向右移动左指针，右指针不动
                if ((l != i + 1 && nums[l] == nums[l - 1]) || nums[l] + nums[r] < target) {
                    l++;
                    continue;
                }
                if (nums[l] + nums[r] == target) {
                    result.push_back({nums[i], nums[l], nums[r]});
                    l++;
                    r--;
                    continue;
                }
                // 到这一步，说明nums[l] + nums[r] > target，那就要向左移动右指针, 左指针不动
                r--;
            }
        }

        return result;
    }
};

Day4(3.1)

Leetcode 53. 最大子数组和(Medium)

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：

1
2
3
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

1
2
输入：nums = [1]
输出：1

示例 3：

1
2
输入：nums = [5,4,-1,7,8]
输出：23

提示：

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

**进阶：**如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

动态规划

这题是非常经典可以用动态规划算法来解决的。求解一个数组的最大子数组问题，可以分解为求解以每个位置结尾的最大子数组和，然后取最大值。

用数学语言表述就是：我们用f(i)代表以第 i 个数结尾的「连续子数组的最大和」，我们要求解的最大子数组就是max0≤i≤n−1f(i)max_{0≤i≤n−1}{f(i)}

那么我们如何求解每个位置的f(i)f(i)呢？这里就是动态规划的核心解决的问题：子问题重叠。每个位置的f(i)f(i)，都与前一个位置f(i−1)f(i-1)有关。当我们在寻找以nums[i]为结尾的最大子数组时，可以比较f(i - 1) + nums[i]大，还是nums[i]大，来决定是将nums[i]加入到前一个元素为结尾的最大子数组中，还是单独新成立一个子数组。即，

f(i) = max(f(i-1) + nums[i], nums[i])

这就是本题动态规划的状态转移方程建立的递推关系。

在空间利用上，我们只需要一个max_fi存储全局的最大子数组之和，一个pre_fi来存储前一个位置的状态（最大子数组之和）。因为计算当前位置的状态只需要用到前一个位置的状态。因此空间复杂度是O(1)。同时因为只需要遍历一遍数组，时间复杂度是O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public:
    // 动态规划
    int maxSubArray(vector<int>& nums) {
        int max_fi = nums[0];

        int pre_fi = 0;
        for (int i = 0; i < nums.size(); ++i) {
            int fi = max(nums[i], pre_fi + nums[i])
                if (fi > max_fi) {
                    max_fi = fi;
                }
            pre_fi = fi;
        }

        return max_fi;
    }
};

Leetcode 补充题4. 手撕快速排序(Medium)

给你一个整数数组 nums，请你将该数组升序排列。

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

示例 1：

1
2
输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：

1
2
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

提示：

  • 1 <= nums.length <= 5 * 104
  • -5 * 104 <= nums[i] <= 5 * 104

时间复杂度为 O(nlog(n))的排序数组方式有很多种，但CodeTop这题指定我们手撕快速排序。快速排序是非常重要经常考察的一种排序方式。在Day2中我刚刚手撕过快速排序的变型快速选择，今天借着这道题就来熟练一下手撕快速排序！

第一版：随机快排+递归

这基本就是常规的快排写法，唯一的优化就是随机选取pivot。这题的测试集有一个顺序排序好的数组，如果不随机选pivot时间复杂度会变成O(N2)O(N^2)，过不了test

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// 随机快排 + 递归
class Solution
{
public:
    vector<int> sortArray(vector<int> &nums)
    {
        // 初始化随机数种子
        srand(time(nullptr));
        quickSort(nums, 0, nums.size() - 1);
        return nums;
    }

private:
    void quickSort(vector<int> &nums, int begin, int end)
    {
        if (begin >= end)
        {
            return;
        }

        // Randomly select the pivot
        int pivot_index = begin + rand() % (end - begin + 1);
        swap(nums[pivot_index], nums[end]);

        pivot_index = partition(nums, begin, end);

        quickSort(nums, begin, pivot_index - 1);
        quickSort(nums, pivot_index + 1, end);

        return;
    }

    // Return the index of the pivot after partitioning
    int partition(vector<int> &nums, int begin, int end)
    {
        int pivot = nums[end];
        // i指向小于pivot的区域的最后一个元素
        int i = begin - 1;

        for (int j = begin; j < end; j++)
        {
            if (nums[j] < pivot)
            {
                swap(nums[++i], nums[j]);
            }
        }

        swap(nums[i + 1], nums[end]);
        return i + 1;
    }
};

这也是leetcode官方题解的写法。然而实测速度非常感人。原因是测试集里那个全是相同数的数组。二路分区（分为小于pivot的部分和大于pivot的部分）的策略也会导致相同的数都归到pivot同一侧，时间复杂度变成O(N2)O(N^2)。

那么这题就不能用快排来写吗？不！我还要优化！

第二版：三路随机快排+尾递归优化

为了能handle那个逆天的全是相同数字的数组，我决定采用三路分区来完成partition。也就是说，将数组分为小于pivot，等于pivot，和大于pivot三个部分。这样partition过后只需要对小于pivot的部分和大于pivot的部分进行快排就行了。

第二个优化的点就是我将quickSort中连续的两个递归转化成了先递归pivot一侧的元素，然后迭代进行第二次递归pivot另一侧的元素，应该能够减少一点栈空间的消耗。虽然实测效果不明显。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// 三路随机快排+尾递归优化
class Solution
{
public:
    vector<int> sortArray(vector<int> &nums)
    {
        // 初始化随机数种子
        srand(time(nullptr));
        quickSort(nums, 0, nums.size() - 1);
        return nums;
    }

private:
    void quickSort(vector<int> &nums, int begin, int end)
    {
        while (begin < end)
        {
            // Randomly select the pivot
            int pivot_index = begin + rand() % (end - begin + 1);
            swap(nums[pivot_index], nums[end]);

            pair<int, int> pivot_range = threeWayPartition(nums, begin, end);

            // 先处理较小的分区，迭代处理较大的分区
            if (pivot_range.first - begin < end - pivot_range.second)
            {
                quickSort(nums, begin, pivot_range.first - 1);
                begin = pivot_range.second + 1;
            }
            else
            {
                quickSort(nums, pivot_range.second + 1, end);
                end = pivot_range.first - 1;
            }
        }
    }

    // 三路分区
    pair<int, int> threeWayPartition(vector<int> &nums, int begin, int end)
    {
        int pivot = nums[end];
        int lt = begin;
        int gt = end;
        int i = begin;

        while (i <= gt)
        {
            if (nums[i] < pivot)
                swap(nums[i++], nums[lt++]);
            else if (nums[i] > pivot)
                swap(nums[i], nums[gt--]);
            else
                i++;
        }

        return {lt, gt};
    }
};

不多说，效果见图，神中神！ 谁说这题不能用快排写？

Day5(3.3)

Leetcode 21. 合并两个有序链表(Easy)

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

img

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

示例 2：

1
2
输入：l1 = [], l2 = []
输出：[]

示例 3：

1
2
输入：l1 = [], l2 = [0]
输出：[0]

提示：

  • 两个链表的节点数目范围是 [0, 50]
  • -100 <= Node.val <= 100
  • l1 和 l2 均按 非递减顺序 排列

迭代

这题我想到的解法是用迭代法，用一个指针p来指向合并的链表末尾，用两个指针p1和p2分别指向当前需要比较的两个list的元素。我还在合并的链表的头结点前面加了一个dummy node，方便最后返回合并链表的头结点dummy->next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 迭代法
class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *list1, ListNode *list2)
    {
        ListNode* dummy = new ListNode(0);
        ListNode* p1 = list1;
        ListNode* p2 = list2;
        ListNode* p = dummy;

        while (p1 != NULL && p2 != NULL) {
            if (p1->val < p2->val) {
                p->next = p1;
                p1 = p1->next;
            } else {
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
        }
        
        if (!p2) p->next = p1;
        if (!p1) p->next = p2;

        return dummy->next;
    }
};

递归

递归法其实感觉才是yyds，因为思路很简洁清晰，很容易写对。

两个链表的merge操作用递归定义其实就是：

摘自Leetcode官方题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 递归法
class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *list1, ListNode *list2)
    {
        if (!list1) return list2;
        if (!list2) return list1;

        if (list1->val < list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
        
        list2->next = mergeTwoLists(list1, list2->next);
        return list2;
    }
};

复杂度分析

迭代和递归法时间复杂度都是O(N + M)。

迭代法空间复杂度是O(1)，只需要维护常数个变量；递归法空间复杂度是O(N+M)，因为递归调用需要消耗栈空间，递归调用深度是O(N + M)。

Leetcode 5. 最长回文子串(Medium)

给你一个字符串 s，找到 s 中最长的 回文 子串。

示例 1：

1
2
3
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

1
2
输入：s = "cbbd"
输出："bb"

提示：

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成

中心扩展 + 双指针

这题我自己的解法是运用双指针来完成中心扩展。可以这样想：回文字符串，是从最中心的1个字符或2个（相等）字符向外扩展的。因此当我们每遍历1个字符，或2个相邻的相同字符，就分别向左向右扩展1个字符（用左右双指针），查看这两个字符是否相等，如果相等那我们就得到了新的更长的字符串（接下来就记录下来当前的子串，然后继续向左向右扩展），否则就可以返回我们上次记录下来的子串。这个返回的子串就是以我们遍历到的那1个字符或2个（相等）字符为回文中心的最长子串。

这个算法的时间复杂度是多少呢？最外层是遍历(N次)字符寻找回文中心，第二层是根据回文中心向外扩展。要注意的是回文中心有长度为1和长度为2两种情况，因此第二层实际上是两次循环。总时间复杂度是O(N2)O(N^2)

空间复杂度是O(1)，只需要一个全局的longest来记录当前遍历过得回文中心里最长的子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public:
        string longestPalindrome(string s) {
            pair<int, int> longest;
            for (int i = 0; i < s.size(); ++i) {
                for (int j = i; j <= i + 1; ++j) {
                    int l = i;
                    int r = j;
                    if (r >= s.size() || s[l] != s[j]) break;
                    pair<int, int> pre = {l, r};
                    while (l >= 0 && r <= s.size() - 1) {
                        if (s[l] != s[r]) break;
                        pre = {l, r};
                        l--;
                        r++;
                    }
                    if (pre.second - pre.first > longest.second - longest.first) {
                        longest = pre;
                    }
                }
            }

            return s.substr(longest.first, longest.second - longest.first + 1);
        }
    };

动态规划

上面中心扩展的方法效果已经够好了，为什么还要用动态规划写一遍呢？因为动态规划的解法具有更强的普适性。

为什么这题可以用动态规划求解？可以这样思考：我们要判定一个子串是否是回文子串，与这个子串去掉最左右两个字符的子串是否是回文数列有关。P(i, j)为true表示以下标i为开头，j为结尾的子串是回文子串。可以写出动态规划的状态转移方程：

$ P(i,j)=P(i+1,j−1)∧(S_i==S_j) $

因此可以用一个二维数组表示dp，其中数组的两个下标分别代表i, j，数组的值就是bool值表示当前子串是否是回文子串。数组的初始值先都设置为false，除了i = j的数组元素设置为true。

注意在状态转移方程中，我们是从长度较短的字符串向长度较长的字符串进行转移的，因此循环的顺序是从短字符到长字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 动态规划 
class Solution {
    public:
        string longestPalindrome(string s) {
            int n = s.size();
            int maxLen = 1;
            int begin = 0;
            vector<vector<bool>> dp(n, vector<bool>(n));
            // 初始化dp数组
            for (int i = 0; i < n; ++i) {
                dp[i][i] = true;
            }

            // 从短字符开始循环更新dp数组，向长字符转移
            for (int L = 2; L <= n; ++L) {
                // 先固定左指针，就能根据长度唯一确定右指针
                for (int l = 0; l < n; ++l) {
                    int r = l + L - 1;
                    if (r >= n) {
                        break;
                    }

                    if (s[l] != s[r]) continue;

                    // 运行到这里，说明s[l] = s[r]，更新dp数组
                    if (r - l < 3) {
                        dp[l][r] = true;
                    } else {
                        dp[l][r] = dp[l+1][r-1];
                    }

                    if (dp[l][r] && L > maxLen) {
                        begin = l;
                        maxLen = L;
                    }
                }
            }

            return s.substr(begin, maxLen);
        }
    };

动态规划的总时间复杂度还是O(N2)O(N^2)，因为判断子串是否是回文子串可以根据转移前的状态来判断，时间复杂度是O(1)

但是空间复杂度是O(N2)O(N^2)，因为需要构建二维dp数组来保存所有子串的状态（是否是回文子串）

这里再总结一下动态规划的解题步骤：

  1. 确定dp数组及下标的含义（有哪些变量？状态是什么？）
  2. 确定状态转移方程/递推公式（如何根据前面已得知的状态推导出当前要求解的状态）
  3. 初始化dp数组（包括边界条件）
  4. 确定遍历顺序（已知的状态->未知的状态）

Day6(3.4)

Leetcode 102. 二叉树的层序遍历(Medium)

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

img

1
2
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

1
2
输入：root = [1]
输出：[[1]]

示例 3：

1
2
输入：root = []
输出：[]

提示：

  • 树中节点数目在范围 [0, 2000] 内
  • -1000 <= Node.val <= 1000

BFS

二叉树的层序遍历，就是经典的BFS(深度优先搜索)算法，用一个queue来完成。每遍历一层，将每个节点的左右孩子push进queue，然后pop当前节点。每层遍历完后，正好这层的所有节点都pop出去了，下一层的所有节点都在queue中，通过queue.size()就可以知道下一层的节点个数，以此确定下层的循环遍历次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public:
        vector<vector<int>> levelOrder(TreeNode* root) {
            vector<vector<int>> result;

            queue<TreeNode *> queue;
            if (root) queue.push(root);

            while(!queue.empty()) {
                vector<int> vec;

                int n = queue.size();
                for (int i = 0; i < n; ++i) {
                    TreeNode* cur = queue.front();
                    vec.push_back(cur->val);
                    if (cur->left) queue.push(cur->left);
                    if (cur->right) queue.push(cur->right);
                    queue.pop();
                }
                
                result.push_back(vec);
            }

            return result;
        }
    };

复杂度分析

每个节点进队出队各一次，时间复杂度是O(N)；

队列中的元素不超过N个，空间复杂度是O(N)。

Leetcode 1. 两数之和(Easy)

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

1
2
3
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

1
2
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

1
2
输入：nums = [3,3], target = 6
输出：[0,1]

提示：

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • 只会存在一个有效答案

**进阶：**你可以想出一个时间复杂度小于 O(n2) 的算法吗？

这题在Day3做三数之和问题的时候已经提前做过了，这里就当再复习一遍吧。

题目前提是只会存在一个有效答案，因此不需要担心重复问题。只需要用一个哈希表存储每个元素值和其对应的index。这样就可以以O(1)的时间复杂度找到对应值的index。因此总体的时间复杂度就是遍历一遍nums的O(N)，空间复杂度也是O(N)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution
{
    public:
    vector<int> twoSum(vector<int> &nums, int target)
    {
        unordered_multimap<int, int> hashmap;
        for (int i = 0; i < nums.size(); i++)
        {
            hashmap.insert({nums[i], i});
        }

        vector<int> index;
        for (int i = 0; i < nums.size(); i++)
        {
            auto range = hashmap.equal_range(target - nums[i]);
            for (auto it = range.first; it != range.second; it++)
                // 找到第一个不是当前i的index
                if (it->second != i)
                {
                    index.push_back(i);
                    index.push_back(it->second);
                    return index;
                }
        }

        return index;
    }
};

Day7(3.5)

Leetcode 33. 搜索旋转排序数组(Medium)

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

1
2
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：

1
2
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：

1
2
输入：nums = [1], target = 0
输出：-1

提示：

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • nums 中的每个值都 独一无二
  • 题目数据保证 nums 在预先未知的某个下标上进行了旋转
  • -104 <= target <= 104

二分查找（变型）

这题就是在一个（类似）排序好的数组里找某个值的位置，显然是用二分法来查找。

但是这个数组并不是完全排序好的，而是由两段排序好的子数组拼接而成，那么我们自然思路就是先找到拼接的分界点，然后根据target的大小选择其中一段子数组来进行二分查找。

我们可以注意到第一段子数组的第一个元素和第二段子个数组的最后一个元素在旋转前的数组中是相邻的两个数。我们可以用类似于二分法的方式找到这两段子数组的拼接点，具体来说就是找到第二段子数组的第一个元素的下标。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 返回数组最小的元素下标
int binary_search(vector<int>& nums, int l, int r) {
    int m = l + (r - l) / 2;

    if (nums[m] >= nums[0] && nums[m + 1] < nums[0]) {
        return m + 1;
    }

    if (nums[m] >= nums[0]) {
        return binary_search(nums, m + 1, r);
    }
    return binary_search(nums, l, m - 1);
}

找到这个拼接点的下标后，就可以根据target的大小选择其中一个子数组进行二分查找了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int search(vector<int>& nums, int target) {
    int n = nums.size();
    int min_index = 0;
    if (nums[0] > nums[n - 1]) {
        // 找到数组中最小值的下标，也就是两个子数组的拼接点
        min_index = binary_search(nums, 0, n - 1);
    }

    if (target <= nums[n - 1]) {
        return binary_search(nums, min_index, n - 1, target);
    } 

    return binary_search(nums, 0, min_index - 1, target);
}

int binary_search(vector<int>& nums, int l, int r, int target) {
    int m = l + (r - l) / 2;

    if (l > r) {
        return -1;
    }

    if (nums[m] == target) {
        return m;
    }

    if (nums[m] < target) {
        return binary_search(nums, m + 1, r, target); 
    }
    return binary_search(nums, l, m - 1, target);
}

复杂度分析

这题就是做两次二分查找，第一次先找到拼接点的下标，第二次在其中一个子数组中做普通的二分查找。因此总时间复杂度是O(logN)

我是用递归的方法做二分查找的，递归深度是logN，因此空间复杂度是O(logN)

Leetcode 200. 岛屿数量(Medium)

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

1
2
3
4
5
6
7
输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1

示例 2：

1
2
3
4
5
6
7
输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] 的值为 '0' 或 '1'

DFS

用DFS解这题的思路很简单，每遍历到一个陆地（‘1’），就用DFS将其连接的陆地（‘1’）都变为‘0’。最后岛屿的数量就是遍历到的陆地数量。

我们先回顾一下dfs的代码框架：

1
2
3
4
5
6
7
8
9
10
11
12
void dfs(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本节点所连接的其他节点) {
        处理节点;
        dfs(图，选择的节点); // 递归
        回溯，撤销处理结果
    }
}

这题处理节点就是将当前节点变为0，然后dfs当前节点相邻的四个节点，dfs终止条件就是当前节点是0。不需要存放任何结果，因此回溯时也不用撤销处理结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// DFS
class Solution
{
public:
    int numIslands(vector<vector<char>> &grid)
    {
        int rows = grid.size();
        int cols = grid[0].size();
        int num_islands = 0;

        for (int row = 0; row < rows; ++row) {
            for (int col = 0; col < cols; ++col) {
                if (grid[row][col] == '0') continue;
                // 新的岛屿，开始进行DFS
                ++num_islands;
                dfs(grid, row, col);
            }
        }

        return num_islands;
    }

private:
    void dfs(vector<vector<char>> &grid, int row, int col) {
        if (grid[row][col] == '0') return;
        grid[row][col] = '0';

        if (row - 1 >= 0 && grid[row - 1][col] == '1') {
            dfs(grid, row - 1, col);
        }
        if (row + 1 < grid.size() && grid[row + 1][col] == '1') {
            dfs(grid, row + 1, col)
        }
        if (col - 1 >= 0 && grid[row][col - 1] == '1') {
            dfs(grid, row, col - 1);
        }
        if (col + 1 < grid[0].size() && grid[row][col + 1] == '1') {
            dfs(grid, row, col + 1);
        }
    }
};

时间复杂度是O(M * N)，空间复杂度由DFS深度决定，深度最多是M * N（网格上全是陆地），因此空间复杂度是O(M * N)

BFS

岛屿问题也可以用BFS来解决，同样也是每遍历到一个岛屿，就用BFS将其连接的陆地（‘1’）都变为‘0’。只不过BFS是将遍历到的岛屿作为中心一圈一圈向外扩展，而DFS是找到一条路径搜到底，然后再回溯。

BFS需要用一个队列来存储当前遍历到的位置，要注意的是每次元素入队后应立即对其进行标记，避免重复访问。

回顾一下BFS的代码框架：（针对四方格地图）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向
// grid是地图，也就是一个二维数组
// visited标记访问过的节点，不要重复访问
// x, y表示开始搜索的节点下标
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
    queue<pair<int, int>> que; // 定义队列
    que.push({x, y}); // 起始节点加入队列
    visited[x][y] = true; //只要加入队列，立刻标记为访问过的节点
    while(!que.empty()) {
        pair<int, int> cur = que.front(); // 从队头取元素
        que.pop();
        int curx = cur.first;
        int cury = cur.second; // 当前节点坐标
        for (int i = 0; i < 4; i++) {
            // 开始向当前节点的四个方向左右上下去遍历
            int nextx = curx + dir[i][0];
            int nexty = cury + dir[i][1];
            if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 坐标越界了，直接跳过
            if (!visited[nextx][nexty]) {
                // 如果节点没被访问过
                que.push({nextx, nexty}); // 队列添加该节点为下一轮要遍历的节点
                visited[nextx][nexty] = true; // 只要加入队列立刻标记，避免重复访问
            }
        }
    }
}

那么这题就很简单了，往模版里套就可以了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// BFS
class Solution
{
public:
    int numIslands(vector<vector<char>> &grid)
    {
        int rows = grid.size();
        int cols = grid[0].size();
        int num_islands = 0;
        int dir[4][2] = {0, -1, 1, 0, 0, 1, -1, 0}; // 4个方向

        for (int row = 0; row < rows; ++row)
        {
            for (int col = 0; col < cols; ++col)
            {
                if (grid[row][col] == '0')
                    continue;
                // 新的岛屿，开始进行BFS
                ++num_islands;
                queue<pair<int, int>> q;
                q.push({row, col});
                grid[row][col] = '0';
                while (!q.empty())
                {
                    pair<int, int> cur = q.front();
                    q.pop();
                    for (int i = 0; i < 4; ++i)
                    {
                        int next_row = cur.first + dir[i][0];
                        int next_col = cur.second + dir[i][1];
                        if (next_row >= 0 && next_row < rows && next_col >= 0 && next_col < cols && grid[next_row][next_col] == '1')
                        {
                            q.push({next_row, next_col});
                            grid[next_row][next_col] = '0';
                        }
                    }
                }
            }
        }

        return num_islands;
    }
};

时间复杂度是O(M * N)；空间复杂度是O(min{M, N})，因为在最坏情况下，也就是网格中全是陆地（‘1’），队列中最多同时存在min{M, N}个元素。

Day8(3.6)

Leetcode 46. 全排列(Medium)

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

1
2
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

1
2
输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

1
2
输入：nums = [1]
输出：[[1]]

提示：

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • nums 中的所有整数 互不相同

递归

我想到的解法是用递归。大循环遍历数组中的每个数作为我们选定的数，然后先获取除了我们选定的这个数以外的所有数的全排列，然后将我们选定的这个数作为所有我们得到的排列的最后一个数。这样我们就获得了以我们选定的数为结尾的全排列。因此当我们的大循环遍历完所有的数后，就得到了整体的全排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution
{
public:
    vector<vector<int>> permute(vector<int> &nums)
    {
        list<int> nums_list(nums.begin(), nums.end());
        return permute(nums_list);
    }

private:
    vector<vector<int>> permute(list<int> &nums_list)
    {
        if (nums_list.size() == 1) {
            return vector<vector<int>>(1, vector<int>(1, nums_list.front()));
        }

        vector<vector<int>> result;

        for (int i = 0; i < nums_list.size(); ++i)
        {
            int front = nums_list.front();
            nums_list.pop_front();

            vector<vector<int>> sub_permute = permute(nums_list);
            for (auto& it : sub_permute) {
                it.push_back(front);
                result.push_back(it);
            }

            nums_list.push_back(front);
        }

        return result;
    }
};

为什么我要用个list来复制nums数组呢？因为我要获取我选定的数以外的数的全排列的时候，需要先将该数拿出去，获取完选下一个数之前再拿回来。用list方便从头尾部插入删除元素。

也可以用原先的vector，将选定的数先swap到vector的末尾，放回去的时候再swap回原来的位置：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution
{
public:
    vector<vector<int>> permute(vector<int> &nums)
    {
        if (nums.size() == 1) {
            return vector<vector<int>>(1, nums);
        }

        vector<vector<int>> result;
        int n = nums.size();

        for (int i = 0; i < n; ++i)
        {
            swap(nums[n - 1], nums[i]);
            int back = nums.back();
            nums.pop_back();

            vector<vector<int>> sub_permute = permute(nums);
            for (auto& it : sub_permute) {
                it.push_back(back);
                result.push_back(it);
            }

            nums.push_back(back);
            swap(nums[n - 1], nums[i]);
        }

        return result;
    }
};

回溯

这题用回溯法的思路会稍微复杂一点，我们可以想象有 n 个排列成一行的空格。我们需要从左往右依此填入题目给定的 n个数，每个数只能使用一次。每次backtracking就是往begin位置填入一个数，[0, begin - 1]的位置已经填好数了，然后在begin + 1位置继续调用backtracking。当最后begin = n的时候说明整个一行都填完了，这就得到了其中一个排列，加入到最后的result里面。

事实上我们不需要单独创建一个数组来作为填入的一行，也不需要标记原数组中哪些元素已填入了这一行中，可以直接在原数组上进行操作。每次调用backtracking往begin位置填入时，将要填入的数与begin位置的数交换，然后再从begin + 1处填下一个数。这样的话，每次调用backtracking往begin位置填入时，原数组的[0, begin - 1]就是已经填入的数，寻找要填入的数时在[begin, n)位置寻找就可以了。

要注意，每次回溯后需要撤销处理结果，也就是将填入的数再与原先begin位置的数交换回来，然后继续寻找下一个要在begin位置填入的数。

回顾一下回溯法的代码框架：

1
2
3
4
5
6
7
8
9
10
11
12
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

本题代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution
{
public:
    vector<vector<int>> permute(vector<int> &nums)
    {
        vector<vector<int>> result;
        backtracking(result, nums, 0, nums.size());
        return result;
    }

private:
    void backtracking(vector<vector<int>>& result, vector<int>& nums, int begin, int len) {
        if (begin == len) {
            result.emplace_back(nums);
            return;
        }

        for (int i = begin; i < len; ++i) {
            swap(nums[begin], nums[i]);
            backtracking(result, nums, begin + 1, len);
            swap(nums[begin], nums[i]);
        }
    }
};

复杂度分析

上面递归和回溯算法的时间复杂度都是O(N * N!)

回溯法的空间复杂度只与递归深度有关，递归深度为N，因此空间复杂度是O(N)；

递归法的递归深度也是N，但是每层递归都需要创建一个临时数组来存储子问题的结果：

1
vector<vector<int>> sub_permute = permute(nums);

这个临时数组有多大呢？当处理长度为n的数组时，sub_permute会存储(n-1)!个排列，每个排列有(n-1)个元素，因此这个临时数组占用空间为O((n-1) × (n-1)!) = O(n × (n-1)!) = O(n!)

因此这个递归法的空间复杂度是O(n!)

Leetcode 121. 买卖股票的最佳时机(Easy)

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

1
2
3
4
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

1
2
3
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 104

Naive Solution

外层大循环遍历股票买入日期，内层循环遍历股票卖出日期，时间复杂度是O(N2)O(N^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// O(N^2)时间复杂度
class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            int result = 0;

            for (int i = 0; i < prices.size(); ++i) {
                int max_profit = 0;
                for (int j = i + 1; j < prices.size(); ++j) {
                    if (prices[j] - prices[i] > max_profit) {
                        max_profit = prices[j] - prices[i];
                    }
                }
                if (max_profit > result) {
                    result = max_profit;
                }
            }

            return result;
        }
    };

动态规划

这题是经典的动态规划例题，能够将Naive算法的O(N2)O(N^2)时间复杂度降到O(N)。

动态规划的思想是当前位置的状态可以由前一个位置的状态通过递归算式推导出。可以这样想，如果我们将股票第i天卖出可以获取到的最大利润定义为f(i)，那么第i + 1天可以获取到的最大利润f(i + 1)就可以这样表示：

f(i+1)=max(f(i)+prices[i]−prices[i−1],0)f(i + 1) = max(f(i) + prices[i] - prices[i - 1], 0)​

上面这就是本题动态规划的状态转移方程（递推公式）

那么最后要求的买卖股票最大利润就是：f(i)∣max  0<=i<nf(i)|_{max} \ \ 0<=i<n

因此我们的实现只需要遍历一次数组，每遍历到一个日期，求以该日期为卖出日期能够获取到的最大利润。我用了一个pre_max_profit变量保存以该日期的前一个日期为卖出日期能获取到的最大利润，这样就能根据上面的递推公式求出当前的状态，并更新pre_max_profit，然后遍历到下一个日期。再用一个全局变量max_profit保存全局的最大利润。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 动态规划
class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            int max_profit = 0; 

            int pre_max_profit = 0;
            for (int i = 1; i < prices.size(); ++i) {
                pre_max_profit = max(prices[i] - prices[i - 1] + pre_max_profit, 0);
                if (pre_max_profit > max_profit) {
                    max_profit = pre_max_profit;
                }
            }

            return max_profit;
        }
    };

如前所述，用动态规划解本题的时间复杂度是O(N)，并且只需要创建常数个变量，空间复杂度是O(1)。

Day9(3.7)

Leetcode 88. 合并两个有序数组(Easy)

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

**注意：**最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

1
2
3
4
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：

1
2
3
4
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3：

1
2
3
4
5
输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

提示：

  • nums1.length == m + n
  • nums2.length == n
  • 0 <= m, n <= 200
  • 1 <= m + n <= 200
  • -109 <= nums1[i], nums2[j] <= 109

**进阶：**你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？

双指针

合并两个有序排列问题，就是用双指针来解决。

本题的特殊点在于需要将合并的数组存在nums1中，而不是单开一个空的数组向里面填。可以注意到nums1中后面n个数都是0，也就是待填入的数。因此我们可以从后往前遍历nums1和nums2，将较大的数从nums1的后面往前面写。

如果退出循环的时候是nums2遍历完了，说明nums2中的数已经都插入到nums1中了，可以直接退出；如果是nums1遍历完了，那说明nums1中的数都放到了正确的位置，接下来只要把nums2中剩余的数平移到nums1中就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution
{
    public:
    void merge(vector<int> &nums1, int m, vector<int> &nums2, int n)
    {
        int p1 = m - 1;
        int p2 = n - 1;

        int p = m + n - 1;
        while (p1 >= 0 && p2 >= 0)
        {
            if (nums1[p1] < nums2[p2]) {
                nums1[p] = nums2[p2];
                p2--;
            } else {
                nums1[p] = nums1[p1];
                p1--;
            }
            p--;
        }

        if (p2 >= 0) {
            for (int i = p2; p2 >= 0; --p2) {
                nums1[p2] = nums2[p2];
            }
        }
    }
};

很显然，时间复杂度是O(M + N)，空间复杂度是O(1)

Leetcode 20. 有效的括号(Easy)

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

**输入：**s = "()"

**输出：**true

示例 2：

**输入：**s = "()[]{}"

**输出：**true

示例 3：

**输入：**s = "(]"

**输出：**false

示例 4：

**输入：**s = "([])"

**输出：**true

提示：

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成

栈

本题的关键点在于**“左括号必须以正确的顺序闭合”**，也就是说"( [ ) ]"的顺序是错误的。

本题是运用栈的经典例题。当我们遇到左括号，就压入栈中；如果遇到右括号，检查当前栈顶是不是相对应的左括号，如果是那么将栈顶元素出栈，如果不是说明出错。

如果遍历到最后还没出错，并且栈最后为空，说明这是一个有效的字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public:
        bool isValid(string s) {
            stack<char> brackets;

            for (char c : s) {
                if (c == '{' || c == '(' || c == '[') {
                    brackets.push(c);
                } else {
                    if (brackets.empty()) return false;
                    if ((c == '}' && brackets.top() == '{') || (c == ')' && brackets.top() == '(') || c == ']' && brackets.top() == '[') {
                        brackets.pop();
                        continue;
                    }
                    return false;
                }
            }

            return (brackets.empty()) ? true : false;
        }
    };

很显然，时间复杂度是O(N)；空间复杂度是O(N)，因为最坏情况下所有元素都是左括号都压入栈中。

Day10(3.8)

Leetcode 103. 二叉树的锯齿形层次遍历(Medium)

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例 1：

1
2
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]

示例 2：

1
2
输入：root = [1]
输出：[[1]]

示例 3：

1
2
输入：root = []
输出：[]

提示：

  • 树中节点数目在范围 [0, 2000] 内
  • -100 <= Node.val <= 100

栈

都说层次遍历/BFS要用队列写，诶我偏用栈写一次（事实证明确实麻烦了）

如果用栈的话，每次都要为下一层单独开一个stack，遍历当前层的stack的时候，将下一层的元素压入下一层的stack中。然后在遍历完当前层的stack后，将下一层的stack赋值给当前层的stack，开始遍历下一层。

用栈的好处是：我们从栈中遍历的顺序就是锯齿形的顺序。每次从栈顶取到的元素直接放入结果的数组中就可以了，只要交替变换每层之间左右孩子被压入栈中的顺序就行了。而下面用队列的方法其实并不会改变普通层次遍历的遍历顺序，只是放入结果的位置改变了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * 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:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> result;

        bool left_first = true;

        stack<TreeNode*> cur_stack;
        stack<TreeNode*> next_stack;
        if (root) cur_stack.push(root);
        vector<int> cur_level;
        while (!cur_stack.empty() || !next_stack.empty()) {
            TreeNode* cur = cur_stack.top();
            if (left_first) {
                if (cur->left) next_stack.push(cur->left);
                if (cur->right) next_stack.push(cur->right);
            } else {
                if (cur->right) next_stack.push(cur->right);
                if (cur->left) next_stack.push(cur->left);
            }
            cur_stack.pop();
            cur_level.push_back(cur->val);
            if (cur_stack.empty()) {
                cur_stack = next_stack;
                next_stack = std::move(stack<TreeNode*>());
                result.push_back(cur_level);
                cur_level.clear();
                left_first = !left_first;
            }
        }

        return result;
    }
};

队列+双端队列

当然，层次遍历还是用队列最方便。但是此题需要返回锯齿形的遍历顺序，那么我们就不能按每层中遍历到的元素顺序直接返回。具体来说，奇数层需要返回从右到左的元素顺序。但我们从队列中遍历的顺序是从左到右的呀，那怎么办呢？很简单，对奇数层来说，从左到右每从queue中遍历到一个元素，就将其插入到我们选定的容器的开头(front)，这样一层遍历完之后容器开头就是最右侧的元素了。而对于偶数层来说，从左到右每从queue中遍历到一个元素，就将其插入到我们选定的容器的末尾(back)。

那么问题就来了，什么容器可以既方便从开头插入元素，又方便从末尾插入元素？没错，就是双端队列(deque)！将每层的遍历结果都用deque来存储，然后赋值给vector加入结果中就可以了！

这个方法的好处就是我们不需要修改普通二叉树的层次遍历逻辑，只要修改存储遍历结果的方式就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution
{
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode *root)
    {
        vector<vector<int>> result;

        bool left_first = true;

        queue<TreeNode *> que;
        if (root)
            que.push(root);
        while (!que.empty())
        {
            deque<int> deq;

            int size = que.size();
            for (int i = 0; i < size; ++i)
            {
                TreeNode *cur = que.front();
                que.pop();
                if (cur->left)
                    que.push(cur->left);
                if (cur->right)
                    que.push(cur->right);

                if (left_first) {
                    deq.push_back(cur->val);
                } else {
                    deq.push_front(cur->val);
                }
            }

            result.push_back(vector<int>{deq.begin(), deq.end()});
            left_first = !left_first;
        }

        return result;
    }
};

复杂度分析

BFS的时间复杂度就是O(N)，每个元素只需要遍历一次。空间复杂度是O(N)，因为无论是用栈还是队列，最坏情况下都需要存储N个元素，并且还需要一个容器来存储每层的结果。

Leetcode 236. 二叉树的最近公共祖先(Medium)

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

1
2
3
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

1
2
3
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。5

示例 3：

1
2
输入：root = [1,2], p = 1, q = 2
输出：1

提示：

  • 树中节点数目在范围 [2, 105] 内。
  • -109 <= Node.val <= 109
  • 所有 Node.val 互不相同 。
  • p != q
  • p 和 q 均存在于给定的二叉树中。

递归

这题都知道要用递归来写，但是要想清楚思路还是有些难度。只要能够想清楚递归的思路，代码写起来是很简单的！

我们可以这样想，如果我们要找的p和q分别在当前节点的左右子树，那么当前节点就是p和q的最近共同祖先。如果p和q都在其中一个（左或右）子树，那么这棵子树的根节点，（也就是root的左或右节点），就是离p和q更近的共同祖先。接下来就在这棵子树中寻找最近的共同祖先。

因此我们递归的返回条件是什么呢？只要我们找到p或q节点，就直接返回。因为我们每次递归调用的时候，root节点都是p和q的共同祖先。而一旦root节点是p或者q，那么很显然root就一定会是p和q的共同祖先。

那怎么判断当前递归调用时的root节点是否是p和q最近的共同祖先呢？结合递归的返回条件，我们可以分别递归调用左子树和右子树。如果在左子树中找到了p或q节点，又在右子树中找到了p或q节点，那么说明p和q节点分别在root的左右子树，显然root就是p和q的最近祖先。而如果只在其中一侧找到了p或q节点，说明p和q节点都在这棵子树上，那么就返回这一侧的递归结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution
{
public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
        // 只要找到p和q的其中一个，就返回
        if (!root || root == p || root == q) return root;

        TreeNode* l = lowestCommonAncestor(root->left, p, q);
        TreeNode* r = lowestCommonAncestor(root->right, p, q);

        if (l && r) return root;
        if (l) return l;
        return r;
    }
};

复杂度分析

二叉树的每个节点都只会访问一次，时间复杂度是O(N)；

空间复杂度取决于递归调用的深度，而递归调用的深度取决于二叉树的高度。最坏情况下二叉树会退化成链表，高度为N。因此空间复杂度是O(N)

Day11(3.9)

Leetcode 141. 环形链表(Easy)

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

1
2
3
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

1
2
3
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

  • 链表中节点的数目范围是 [0, 104]
  • -105 <= Node.val <= 105
  • pos 为 -1 或者链表中的一个 有效索引 。

**进阶：**你能用 O(1)（即，常量）内存解决此问题吗？

哈希表

最容易想到的是用哈希表存储我们访问过的节点。每遍历到一个节点，先检查该节点是否在哈希表中，如果是说明是环形链表。遍历到最后都没找到重复遍历过的节点，说明不是环形链表。

代码很容易，这里就不写了。这个算法的空间复杂度是O(N)，有没有一种O(1)的空间复杂度的算法解此题呢？

双指针（快慢指针）

这题可以用双指针的一个trick：快慢指针。我们通常使用双指针都是两个指针每次移动一格，速度一样。这题在我们判断环形链表的时候，可以使用一慢一快两个指针：慢指针一次移动一格，快指针一次移动两格。那么如果链表不是环形的，快指针应该会一直在慢指针的前方。而如果是环形链表，那么两个指针走着走着一定会重合。可以想象龟兔赛跑的场景：乌龟和兔子在链表上移动，兔子跑得快，如果链表是环形的，那么就会套圈，与乌龟相遇。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public:
        bool hasCycle(ListNode *head) {
            if (!head) return false;
            TreeNode* one_step = head;
            TreeNode* two_step = head->next;

            while (one_step && two_step) {
                if (one_step == two_step) return true;
                one_step = one_step->next;
                if (!two_step->next) return false;
                two_step = two_step->next->next;
            }

            return false;
        }
    };

Leetcode 92. 反转链表 II(Medium)

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：

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

示例 2：

1
2
输入：head = [5], left = 1, right = 1
输出：[5]

提示：

  • 链表中节点数目为 n
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

进阶： 你可以使用一趟扫描完成反转吗？

此题难度并不大，就是翻转链表的变型。比普通的翻转一整个链表要多做的事情就是将[left, right]的子链表翻转后接回原本的链表，那就需要一个变量pre_last保存子链表的前一个节点，还需要一个cur_first指向翻转后的子链表的最后一个节点（这样就可以在翻转子链表的循环结束后将翻转后的子链表的最后一个节点的next指向原本子链表的后一个节点，也就是接回原链表）。翻转链表就是常规的套路：用一个pre节点保存遍历到的前一个节点，将当前节点指向pre。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public:
        ListNode* reverseBetween(ListNode* head, int left, int right) {
            ListNode* dummy = new ListNode(0, head);
            head = dummy;
            for (int i = 1; i < left; ++i) {
                head = head->next;
            }
            ListNode* pre_last = head; // 将要翻转的第一个节点的前一个节点
            head = head->next;
            ListNode* cur_first = head; // 将要翻转的第一个节点，也是翻转后的子链表的最后一个节点

            ListNode* pre = pre_last;
            for (int i = 0; i <= right - left; ++i) {
                ListNode* next = head->next;
                head->next = pre;
                pre = head;
                head = next;
            }
            // 循环结束后，pre指向翻转后的子链表的第一个节点，head指向翻转的子链表的后面一个节点
            pre_last->next = pre;
            cur_first->next = head;

            return dummy->next;
        }
    };

这样就可以保证只需要扫描一次就完成翻转，时间复杂度是O(N)；并且只需要常数个变量，空间复杂度是O(1)。

Day12(3.10)

Leetcode 23. 合并K个排序链表(Hard)

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

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

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：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

示例 2：

1
2
输入：lists = []
输出：[]

示例 3：

1
2
输入：lists = [[]]
输出：[]

提示：

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] 按 升序 排列
  • lists[i].length 的总和不超过 10^4

优先级队列

这题可以使用优先级队列进行合并。先将每个链表的头节点放入最小堆中，然后每次从堆顶取出一个节点（这个节点就是当前所有链表中的最小值，接入结果链表中），然后将这个节点所在链表的next节点放入堆中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution
{
public:
    ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        ListNode *dummy = new ListNode(0);
        ListNode *tail = dummy;

        // 将每个链表的头节点放入堆中
        for (ListNode* node : lists)
        {
            if (node) minHeap.push(node);
        }

        while (!minHeap.empty())
        {
            ListNode *smallest_node = minHeap.top();
            minHeap.pop();
            if (smallest_node->next) minHeap.push(smallest_node->next);

            tail->next = smallest_node;
            tail = tail->next;
        }

        return dummy->next;
    }

private:
    // 自定义比较器
    struct CompareListNode
    {
        bool operator()(ListNode *a, ListNode *b)
        {
            return a->val > b->val;   // 最小堆中，大的元素放小的元素下方
        }
    };

    // 创建最小堆
    priority_queue<ListNode *, vector<ListNode *>, CompareListNode> minHeap;
};

堆中的元素是每个链表当前需要比较的最小值，因此最多有K个，空间复杂度是O(K)；

堆的插入和删除操作时间复杂度都是O(logK)，K个链表中的每个元素都需要插入和删除各一次，因此总时间复杂度是O(N * K * logK)

分治合并

这题也可以用分治的思想进行合并，可以这样思考递归的思路：合并K个链表，就是先将前K/2个链表合并，再将后K/2个链表合并，然后将合并后的这两个链表合并。递归的结束条件是当前要合并的链表数量只有一个，那么直接返回当前链表。

而合并两个链表的实现很简单，在Day5中已经做过了，就是用双指针。

如下图：第一轮两两合并，第二轮再将第一轮合并后的链表两两合并，直到最后两个链表合并得到最终的合并链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// 分治合并
class Solution
{
public:
    ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        if (lists.empty()) return NULL;
        return merge(lists, 0, lists.size() - 1);
    }

private:
    // 将第l个链表到第r个链表合并成一个链表
    ListNode *merge(vector<ListNode *> &lists, int l, int r) {
        if (l == r) return lists[l];

        int mid = l + (r - l) / 2;

        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    ListNode *mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummy = new ListNode(0);
        ListNode* tail = dummy;

        ListNode* p1 = list1;
        ListNode* p2 = list2;
        while (p1 && p2) {
            if (p1->val < p2->val) {
                tail->next = p1;
                p1 = p1->next;
            } else {
                tail->next = p2;
                p2 = p2->next;
            }
            tail = tail->next;
        }

        if (!p1) tail->next = p2;
        if (!p2) tail->next = p1;

        return dummy->next;
    }
};

分治合并的递归深度是log(K)，空间复杂度就是消耗的栈空间O(logK)；

时间复杂度需要好好计算以下，我们考虑递归向上回升的过程。第一轮是两两合并链表，共合并K/2组链表，合并每组的时间复杂度是O(2N)；第二层共合并K/4组链表，合并每组的时间复杂度是O(4N)...，而递归的层数是log(K)，因此总时间复杂度是O(N * K * logK)

Leetcode 54. 螺旋矩阵(Medium)

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

1
2
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

1
2
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100

模拟

本题就是模拟螺旋数组访问的路径，分别用4个变量维护四个方向的boundry：

1
2
3
4
5
6
7
int rows = matrix.size();
int cols = matrix[0].size();

int upper_boundry = 0;
int lower_boundry = rows - 1;
int left_boundry = 0;
int right_boundry = cols - 1;

用一个大循环表示路径访问了一圈，大循环中四个小循环分别表示四个路径访问方向。保证访问的路径始终落在boundry范围里面。每访问完一行或一列，更新boundry。如果更新后的boundry越界，说明整个数组访问结束，退出大循环。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution
{
public:
    vector<int> spiralOrder(vector<vector<int>> &matrix)
    {
        vector<int> result;

        int rows = matrix.size();
        int cols = matrix[0].size();

        int upper_boundry = 0;
        int lower_boundry = rows - 1;
        int left_boundry = 0;
        int right_boundry = cols - 1;

        int i = 0, j = 0;
        while (true)
        {
            for (; j <= right_boundry; ++j)
            {
                result.push_back(matrix[i][j]);
            }
            j = right_boundry;
            i = upper_boundry + 1;
            upper_boundry++;
            if (upper_boundry > lower_boundry) break;

            for (; i <= lower_boundry; ++i)
            {
                result.push_back(matrix[i][j]);
            }
            i = lower_boundry;
            j = right_boundry - 1;
            right_boundry--;
            if (right_boundry < left_boundry) break;

            for (; j >= left_boundry; --j)
            {
                result.push_back(matrix[i][j]);
            }
            j = left_boundry;
            i = lower_boundry - 1;
            lower_boundry--;
            if (upper_boundry > lower_boundry) break;

            for (; i >= upper_boundry; --i)
            {
                result.push_back(matrix[i][j]);
            }
            i = upper_boundry;
            j = left_boundry + 1;
            left_boundry++;
            if (right_boundry < left_boundry) break;
        }

        return result;
    }
};

除了结果数组，只需要创建常数个变量维护boundry，空间复杂度是O(1)；

矩阵中每个元素被访问一次，时间复杂度是O(mn)，其中m和n分别是矩阵的行数和列数。

Day13(3.11)

Leetcode 300. 最长上升子序列(Medium)

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

1
2
3
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

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

示例 3：

1
2
输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

进阶：

  • 你能将算法的时间复杂度降低到 O(n log(n)) 吗?

动态规划

这题的关键难点在于搞清楚dp数组究竟应该存储什么状态。可以这样想：一个数组我们求解出的最长递增子序列一定有一个末尾元素（虽然是废话），因此我们可以求出以每个元素作为末尾元素的最长递增子序列的长度。最后看谁最长，就是整个数组的最长递增子序列长度。

我们用dp数组保存以每个元素作为末尾元素的最长递增子序列的长度，dp[i]表示以数组中第i个元素作为末尾元素的最长递增子序列长度。那怎么求dp[i]呢？根据动态规划的状态转移特性，我们求dp[i]的时候已经求得了dp[0...i−1]的值，因此状态方程可以写为：

dp[i]=max(dp[j])+1，其中0<=j<i且nums[j]<nums[i]dp[i] = max(dp[j]) + 1，其中0 <= j < i且nums[j] < nums[i]​

也就是找在以 当前元素前面的元素 为末尾的最长递增子序列中能接上当前元素的子序列中最大的子序列。

最后的结果就是dp数组中的最大值。

可以看到，本题的动态规划求解当前状态时，不仅仅需要前一个位置的状态，而是要遍历前面所有位置的状态，因此必须要用dp数组来保存所有位置的状态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();

        vector<int> dp(n, 1);

        for (int i = 0; i < n; ++i) {
            int max = 0;
            for (int j = i - 1; j >= 0; --j) {
                if (dp[j] > max && nums[j] < nums[i]) max = dp[j];
            }
            dp[i] = max + 1;
        }

        int max_length = 0;
        for (int i = 0; i < n; ++i) {
            if (dp[i] > max_length) max_length = dp[i];
        }

        return max_length;
    }
};

本题动态规划的空间复杂度是O(N)，因为需要一个一维的dp数组；

时间复杂度是O(N2)O(N^2)，因为求解每个位置的状态时，需要遍历前面所有位置的状态。

Leetcode 415. 字符串相加(Easy)

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

示例 1：

1
2
输入：num1 = "11", num2 = "123"
输出："134"

示例 2：

1
2
输入：num1 = "456", num2 = "77"
输出："533"

示例 3：

1
2
输入：num1 = "0", num2 = "0"
输出："0"

提示：

  • 1 <= num1.length, num2.length <= 104
  • num1 和num2 都只包含数字 0-9
  • num1 和num2 都不包含任何前导零

模拟

本题其实就是模拟竖式加法的过程。从两个字符串的最后一个数（整数的个位数）开始加起，如果进位设置of加到下一位中。这里我用了一个trick：向较短的字符串前面补上0，让两个字符串一样长，方便循环做加法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public:
    string addStrings(string num1, string num2) {
        int length1 = num1.length();
        int length2 = num2.length();
        int length = max(length1, length2);

        int zeros;
        if (length1 > length2) {
            zeros = length1 - length2;
            num2 = string(zeros, '0') + num2;
        } else {
            zeros = length2 - length1;
            num1 = string(zeros, '0') + num1;
        }

        string result;
        int of = 0;  // 是否有overflow
        for (int i = length - 1; i >= 0; --i) {
            int sum = (num1[i] - '0') + (num2[i] - '0') + of;
            if (sum > 9) {
                sum -= 10;
                of = 1;
            } else {
                of = 0;
            }
            result = (char)('0' + sum) + result;
        }

        if (of) result = '1' + result;

        return result;
    }
};

这个算法的时间复杂度是O(max{len1, len2})；

空间复杂度是O(n)，因为我通过向较短的字符串前面添加'0'字符使两个字符串长度相等，这会创建新的string对象，最坏情况下会需要O(n)的额外空间（当一个字符串远长于另一个时）。

Day14(3.12)

Leetcode 160. 相交链表(Easy)

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

  • intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
  • listA - 第一个链表
  • listB - 第二个链表
  • skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
  • skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1：

1
2
3
4
5
6
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例 2：

1
2
3
4
5
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

1
2
3
4
5
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：No intersection
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

  • listA 中节点数目为 m
  • listB 中节点数目为 n
  • 1 <= m, n <= 3 * 104
  • 1 <= Node.val <= 105
  • 0 <= skipA <= m
  • 0 <= skipB <= n
  • 如果 listA 和 listB 没有交点，intersectVal 为 0
  • 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

**进阶：**你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

哈希集合

用哈希集合解这题就很简单，先遍历一遍A链表，将遍历过的节点存在哈希集合里。再遍历B链表，每遍历到一个节点先检查是否在哈希集中，如果是则返回该节点。最后如果遍历完B链表了说明与A链表无相交。代码省略。

该算法的空间复杂度是O(N)，有没有O(1)空间复杂度的算法呢？答案就是双指针！

双指针

这题与其说是双指针的套路题，不如说是一道脑筋急转弯，因为就算告诉你这题用双指针你也不会做。

这题的关键点在于怎么让两个指针pA和pB同时走到第一个相交的节点？要知道A链表和B链表在他们相交前各自的长度是未知的。这里就是核心的trick了：我们让pA和pB以相同的速度先在各自的链表上同步走，然后让pA走完A链表后继续从B链表的开头开始走起，让pB走完B链表后继续从A链表的开头开始走起。

想明白了吗？没想明白的话，建议自己画图模拟一下。这样pA和pB在走完自己的路，又走完对方走过的路后，一定会同时到达两个链表第一次相交的节点。而如果两个链表不相交，那pA和pB在走完自己和对方的路后会同时抵达终点NULL。

蓝色是pA的路线，红色是pB的路线 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution
{
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {
        if (!headA || !headB)
            return NULL;

        ListNode *pA = headA;
        ListNode *pB = headB;

        while (pA || pB)
        {
            if (pA == pB) return pA;
        
            pA = (!pA) ? headB : pA->next;
            pB = (!pB) ? headA : pB->next;
        }

        return NULL;
    }
};

显然这个算法的时间复杂度是O(M + N)，空间复杂度是O(1)

最后放一个leetcode评论区神评：

你悟了吗？

Leetcode 143. 重排链表(Medium)

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

1
L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

1
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

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

示例 1：

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

示例 2：

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

提示：

  • 链表的长度范围为 [1, 5 * 104]
  • 1 <= node.val <= 1000

双端队列

这题一看，先要从链表末尾拿一个元素，再从链表开头拿一个元素，……，而链表本身不支持随机访问。因此很容易想到可以用一个支持随机访问/快速访问和删除首尾元素的容器来装链表。Leetcode官方题解选的是前者，用vector。

我选择的是后者，用一个双端队列。先将链表装到双端队列里面。每次取节点要么取deque的最后一个元素，要么取第一个元素，每次取完将该元素从deque中删除，以上操作都是O(1)的时间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution
{
public:
    void reorderList(ListNode *head)
    {
        if (!head) return;

        deque<ListNode *> list;

        ListNode *p = head->next;
        while (p)
        {
            list.push_back(p);
            p = p->next;
        }

        p = head;
        bool back = true;
        while (!list.empty())
        {
            if (back)
            {
                p->next = list.back();
                list.pop_back();
            } else {
                p->next = list.front();
                list.pop_front();
            }
            p = p->next;
            back = !back;
        }

        p->next = NULL;
    }
};

有一个容易忽略的点：要设置最后一个元素指向NULL。

显然，这个算法的时间复杂度是O(N)；空间复杂度也是O(N)。

Day15(3.15)

Leetcode 56. 合并区间(Medium)

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

1
2
3
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

1
2
3
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

  • 1 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 104

第一版：排序 + 直接在vector上修改

先将区间按左端点从小到大排序，然后从vector的开头开始合并，如果要跟下一个区间合并，则设置当前区间的右端点，然后将下一个区间删除。如果不合并，则将下一个区间设置为当前区间。

然而在vector的任意位置删除的开销很大，总时间复杂度是O(N2)O(N^2)，因此我想到可以用方便在任意位置删除元素的容器来存储以及合并区间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
private:
    struct Less {
        bool operator()(const vector<int>& a, const vector<int>& b) {
            return a[0] < b[0];
        }
    };

public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), Less());

        int i = 0;
        while (i < intervals.size() - 1) {
            if (intervals[i][1] < intervals[i + 1][0]) {
                ++i;
                continue;
            }
            intervals[i][1] = max(intervals[i][1], intervals[i + 1][1]);
            intervals.erase(intervals.begin() + i + 1);
        }

        return intervals;
    }
};

第二版：排序 + 链表

什么容器方便在任意位置删除元素？链表！因此我决定先将区间放到链表中。然后同理还是先按左端点从小到大排序。从开头开始合并区间，如果要跟下一个区间合并，则设置当前区间的右端点，并删除下一个区间。如果不合并，则将下一个区间设置为当前区间。

注意点：list排序要用容器内部的sort函数，不能用sort(list.begin(), list.end())，因为list的迭代器不支持随机访问。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution
{
private:
    struct Less
    {
        bool operator()(const vector<int> &a, const vector<int> &b)
        {
            return a[0] < b[0];
        }
    };

public:
    vector<vector<int>> merge(vector<vector<int>> &intervals)
    {
        list<vector<int>> list(intervals.begin(), intervals.end());

        list.sort(Less());

        auto it = list.begin();
        auto next_it = next(it);
        while (next_it != list.end())
        {
            if ((*it)[1] < (*next_it)[0])
            {
                ++it;
                ++next_it;
                continue;
            }
            (*it)[1] = max((*it)[1], (*next_it)[1]);
            next_it = list.erase(next_it);
        }

        vector<vector<int>> result(list.begin(), list.end());

        return result;
    }
};

链表的删除操作时间复杂度是O(1)，因此总时间复杂度就是排序链表的复杂度O(NlogN)；空间复杂度是O(N)。

Leetcode 42. 接雨水(Hard)

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

1
2
3
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

1
2
输入：height = [4,2,0,3,2,5]
输出：9

提示：

  • n == height.length
  • 1 <= n <= 2 * 104
  • 0 <= height[i] <= 105

动态规划（推荐）

接雨水的核心点：对于下标i处的位置，水能达到的最大高度等于下标i两边的最大高度的最小值。

搞清楚这一点，那么其实我们要求的东西就变成了：对于每个下标i，其左边的最大高度和其右边的最大高度。这就很明显可以用动态规划求解了。

怎么求下标i的左边（包括下标i）的最大高度leftMax[i]呢？如果我们知道了下标i - 1的左边（包括下标i - 1）的最大高度leftMax[i - 1]，那么就很容易求出leftMax[i]了：

leftMax[i]=max(leftMax[i−1],height[i])，其中leftMax[0]=height[0]leftMax[i] = max(leftMax[i - 1], height[i])，其中leftMax[0] = height[0]

那么同理，

rightMax[i]=max(rightMax[i+1],height[i])，其中rightMax[n−1]=height[n−1]rightMax[i] = max(rightMax[i + 1], height[i])，其中rightMax[n - 1] = height[n - 1]

以上两个递推公式就是此题动态规划的状态转移方程。

因此从左向右遍历一遍height数组就可以求出leftMax数组；从右向左再遍历一遍height数组就可以求出rightMax数组。时间复杂度是O(N)。

最后求每个下标i处能接到的雨水数量就等于min(leftMax(i), rightMax(i)) - height[i]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> leftMax(n);
        vector<int> rightMax(n);
        leftMax[0] = height[0];
        rightMax[n - 1] = height[n - 1];

        for (int i = 1; i < n; ++i) {
            leftMax[i] = max(leftMax[i - 1], height[i]);
        }

        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = max(rightMax[i + 1], height[i]);
        }

        int drip = 0;
        for (int i = 0; i < n; ++i) {
            drip += min(leftMax[i], rightMax[i]) - height[i];
        }

        return drip;
    }
};

显然动态规划的解法时间复杂度是O(N)，空间复杂度也是O(N)。

双指针

还是这个核心思想：对于下标i处的位置，水能达到的最大高度等于下标i两边的最大高度的最小值。

我们还是需要知道对于每个下标i处的位置，到底是其左边的最大高度大，还是其右边的最大高度大。如果是其左边的最大高度大，那我们需要知道其右边的最大高度是多少；反之如果是其右边的最大高度大，那我们需要知道其左边的最大高度是多少。

但我们可以对空间利用进行优化，不需要两个数组分别存储每个下标i处的左边最大高度和右边最大高度。

想象以下这个假设：对于一个下标i，如果我们知道了他的leftMax（左边的最大高度）一定比他的rightMax（右边的最大高度）的最小值还要小，那我们只要取leftMax来计算当前位置雨水的高度就行了，我们不需要知道下标i的rightMax具体是多少。反过来也一样，对于一个下标i，如果我们知道了他的rightMax（右边的最大高度）一定比他的leftMax（左边的最大高度）的最小值还要小，那我们只要取rightMax来计算当前位置雨水的高度就行了，我们不需要知道下标i的leftMax具体是多少。

为了应用以上假设，我们需要双指针l和r分别指向数组的开头和末尾下标，还需要两个变量l_leftMax和r_rightMax。注意！这两个变量与上面我说的下标i的leftMax（左边的最大高度）和rightMax（右边的最大高度）不同！l_leftMax应当理解为当前下标l的leftMax（左边的最大高度），r_rightMax应当理解为当前下标r的rightMax（右边的最大高度）。

然后我们就可以让l和r双指针向中间移动收敛了。最初双指针l和r分别指向数组的开头和末尾下标。当l或r每移动一格，就更新l_leftMax和r_rightMax：

1
2
3
4
// l_leftMax是下标l（包括下标l）的左边最大高度；
l_leftMax = max(l_leftMax, height[l]); 
// r_rightMax是下标r（包括下标r）的右边最大高度；
r_rightMax = max(r_rightMax, height[r]);

这部分很简单，就是上面动态规划的思想。

然后就是关键点了：我们比较当前的l_leftMax和r_rightMax：

  1. 如果l_leftMax < r_rightMax，而显然r_rightMax（下标r的rightMax) <= 下标l的rightMax，因此根据符号的传递性，l_leftMax（下标l的leftMax） < 下标l的rightMax。

    因此对于下标l来说，我们知道了其左边的最大高度更小，而这个值我们刚好知道，就是l_leftMax！这样就可以计算出下标l处的水滴数量 = l_leftMax - height[l]。加入结果中后，将l指针向右移动一格，等待计算下一格的水滴数量。

  2. 同理，如果l_leftMax >= r_rightMax，而显然下标r的leftMax >= l_leftMax（下标l的leftMax），因此根据符号的传递性，下标r的leftMax >= r_rightMax（下标r的rightMax）。

    因此对于下标r来说，我们知道了其右边的最大高度更小，而这个值我们刚好知道，就是r_rightMax！这样就可以计算出下标r处的水滴数量 = r_rightMax - height[r]。加入结果中后，将r指针向左移动一格，等待计算下一格的水滴数量。

思路好像挺复杂，但代码写起来很简单：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 双指针
class Solution
{
public:
    int trap(vector<int> &height)
    {
        int n = height.size();
        int l = 0;
        int r = n - 1;

        int l_leftMax = 0;
        int r_rightMax = 0;
        
        int drip = 0;
        while (l <= r) {
            // l_leftMax是下标l（包括下标l）的左边最大高度；
            l_leftMax = max(l_leftMax, height[l]); 
            // r_rightMax是下标r（包括下标r）的右边最大高度；
            r_rightMax = max(r_rightMax, height[r]);

            if (l_leftMax < r_rightMax) {
                // 下标l的rightMax >= 下标r的rightMax = r_rightMax > l_leftMax = 下标l的leftMax；
                drip += l_leftMax - height[l];
                l++;
            } else {
                // 下标r的rightMax = r_rightMax <= l_leftMax = 下标l的leftMax <= 下标r的leftMax；
                drip += r_rightMax - height[r];
                r--;
            }
        }

        return drip;
    }
};

显然双指针的解法时间复杂度是O(N)，空间复杂度是O(1)。

单调栈

与上面两种方法求每个下标i的左右最大高度不同，这题也可以用到单调递减栈来求解。什么是单调递减栈？就是从栈底到栈顶元素大小单调递减。

从左到右遍历数组height，每遍历到一个下标i，如果height[i] <= height[top]（top是栈顶下标），就将下标入栈；否则的话如果栈中至少有两个下标，我们就找到了一个可以接雨水的区域。该区域的宽度是i - left - 1，高度是min(height[left], height[i]) - height[top]。根据宽度和高度即可计算得到该区域能接到的雨水量。为了得到left，需要先将top出栈，在对top计算能接的雨水量之后，left变成新的top，重复上述操作，直到栈变空，或者height[top]大于等于当前遍历到的height[i]。然后将当前的下标i入栈，继续遍历后面的下标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// 单调栈
class Solution
{
public:
    int trap(vector<int> &height)
    {
        int n = height.size();
        stack<int> st;

        int drip = 0;
        for (int i = 0; i < n; ++i)
        {
            if (st.empty() || height[i] <= height[st.top()])
            {
                st.push(i);
                continue;
            }
            // 当前下标的高度大于栈顶下标的高度，如果栈中只有一个下标，替换他
            if (st.size() == 1)
            {
                st.pop();
                st.push(i);
            }
            // 到这一步，栈中至少有两个下标，并且当前下标的高度大于栈顶的高度；
            // 意味着我们找到了一个可以接雨水的区域
            while (height[i] > height[st.top()])
            {
                int top = st.top();
                st.pop();
                if (st.empty()) break;
                int left = st.top();
                // 计算这个接雨水区域的宽度和高度
                int w = i - left - 1;
                int h = min(height[i], height[left]) - height[top];
                drip += w * h;
            }
            // 到这里，当前下标的高度终于比栈顶高度小了（也可能栈空了）
            st.push(i);
        }

        return drip;
    }
};

显然这个算法的时间复杂度是O(N)，空间复杂度也是O(N)。

Leetcode > CodeTop
#CodeTop #Leetcode #刷题
CodeTop每日刷题
http://oooscar8.github.io/2025/02/26/CodeTop/
作者
Alex Sun
发布于
2025年2月26日
许可协议