数据结构学习笔记

学习来源：Leetcode，CSDN等

1 数组

Leetcode例题

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:

1
2
3
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

1
2
3
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

  1. 你可以假设 nums 中的所有元素是不重复的。
  2. n 将在 [1, 10000]之间。
  3. nums 的每个元素都将在 [-9999, 9999]之间。
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
/*
 * @lc app=leetcode.cn id=704 lang=cpp
 *
 * [704] 二分查找
 */

// @lc code=start
#include <vector>
using namespace std;
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int mid;
        while(left <= right) {
            // 防止整型溢出
            mid = (right - left) / 2 + left;
            if(nums[mid] > target) {
                right = mid - 1;
            } else if(nums[mid] < target){
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
};
// @lc code=end

螺旋矩阵②

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

img

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

示例 2：

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

提示：

  • 1 <= n <= 20
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/*
 * @lc app=leetcode.cn id=59 lang=cpp
 *
 * [59] 螺旋矩阵 II
 */

// @lc code=start
#include <vector>
using namespace std;
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res;
        vector<int> temp;
        for(int i = 0; i < n; i++) {
            vector<int> temp(n, 0);
            res.push_back(temp);
        }
        int cur = 1;
        int x = 0, y = 0;
        int _x, _y;
        res[0][0] = cur;
        cur++;
        int limit = n * n - 1; // 控制循环次数
        int flag = 1; // 控制转向
        while(limit > 0) {
            if(flag == 1) {
                // 向右走
                _x = x;
                _y = y + 1;
                if(_y < n && res[_x][_y] == 0) {
                    res[_x][_y] = cur;
                    x = _x;
                    y = _y;
                    cur++;
                    limit--;
                    continue;
                }
                flag = 2;
            }
            if(flag == 2) {
                // 向下走
                _x = x + 1;
                _y = y;
                if(_x < n && res[_x][_y] == 0) {
                    res[_x][_y] = cur;
                    x = _x;
                    y = _y;
                    cur++;
                    limit--;
                    continue;
                }
                flag = 3;
            }
            if(flag == 3) {
                // 向左走
                _x = x;
                _y = y - 1;
                if(_y >= 0 && res[_x][_y] == 0) {
                    res[_x][_y] = cur;
                    x = _x;
                    y = _y;
                    cur++;
                    limit--;
                    continue;
                }
                flag = 4;
            }
            if(flag == 4) {
                // 向上走
                _x = x - 1;
                _y = y;
                if(_x >= 0 && res[_x][_y] == 0) {
                    res[_x][_y] = cur;
                    x = _x;
                    y = _y;
                    cur++;
                    limit--;
                    continue;
                }
                flag = 1;
            }
        }
        return res;
    }
};
// @lc code=end

长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

1
2
3
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

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

示例 3：

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

提示：

  • 1 <= target <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

滑动窗口（双指针）

image-20230320203455329

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
/*
 * @lc app=leetcode.cn id=209 lang=cpp
 *
 * [209] 长度最小的子数组
 */

// @lc code=start
#include <vector>
using namespace std;
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left, right, sum ,res;
        left = 0;
        right = 0;
        sum = 0;
        res = INT_MAX;
        while(right < nums.size()) {
            sum += nums[right];
            while(sum >= target) {
                res = min(res, right - left + 1);
                sum -= nums[left];
                left++; // 左指针移动
            }
            right++; // 右指针移动
        }
        // 可能会有不存在的情况
        return res == INT_MAX ? 0 : res;
    }
};
// @lc code=end

有多少小于当前数字的数字*

给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。

换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。

以数组形式返回答案。

示例 1：

1
2
3
4
5
6
7
8
输入：nums = [8,1,2,2,3]
输出：[4,0,1,1,3]
解释： 
对于 nums[0]=8 存在四个比它小的数字：（1，2，2 和 3）。 
对于 nums[1]=1 不存在比它小的数字。
对于 nums[2]=2 存在一个比它小的数字：（1）。 
对于 nums[3]=2 存在一个比它小的数字：（1）。 
对于 nums[4]=3 存在三个比它小的数字：（1，2 和 2）。

示例 2：

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

示例 3：

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

提示：

  • 2 <= nums.length <= 500
  • 0 <= nums[i] <= 100

题解

缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

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

示例 2：

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

示例 3：

1
2
输入：nums = [7,8,9,11,12]
输出：1

提示：

  • 1 <= nums.length <= 5 * 105
  • -231 <= nums[i] <= 231 - 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
/*
 * @lc app=leetcode.cn id=41 lang=cpp
 *
 * [41] 缺失的第一个正数
 */

// @lc code=start
#include <vector>
#include <map>
using namespace std;
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        map<int, int> hashmap;
        int i = 0;
        for(i = 0; i < nums.size(); i++) {
            if(nums[i] <= 0) {
                continue;
            }
            hashmap[nums[i]] = nums[i];
        }
        for(i = 1; i < hashmap.size() + 1; i++) {
            if(hashmap.find(i) == hashmap.end()) {
                return i;
            }
        }
        return i;
    }
};

2 链表

2.1 链表定义

1
2
3
4
5
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

2.2 Leetcode例题

设计链表

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

  • MyLinkedList() 初始化 MyLinkedList 对象。
  • int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
  • void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
  • void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
  • void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
  • void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]

解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
myLinkedList.get(1);              // 返回 2
myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
myLinkedList.get(1);              // 返回 3

提示：

  • 0 <= index, val <= 1000
  • 请不要使用内置的 LinkedList 库。
  • 调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
/*
 * @lc app=leetcode.cn id=707 lang=cpp
 *
 * [707] 设计链表
 */

// @lc code=start
#include <stdlib.h>
class MyLinkedList {
    typedef struct ListNode { // 链表节点
        int val;
        struct ListNode *next;
    }ListNode;

    typedef struct List { // 链表
        ListNode* head;
        ListNode* tail;
        int len;
    }List;

    List *list;

public:
    MyLinkedList() {
        list = (List *)malloc(sizeof(List));
        list->head = nullptr;
        list->tail = nullptr;
        list->len = 0;
    }
    
    int get(int index) {
        if(index >= list->len) {
            return -1;
        }
        ListNode *node = list->head;
        for(int i = 0; i < index; i++) {
            node = node->next;
        }
        return node->val;
    }
    
    void addAtHead(int val) {
        if(list->head == nullptr) {
            ListNode *node = (ListNode *)malloc(sizeof(ListNode));
            node->val = val;
            list->head = node;
            list->tail = node;
        } else {
            ListNode *node = (ListNode *)malloc(sizeof(ListNode));
            node->val = val;
            node->next = list->head;
            list->head = node;
        }
        list->len += 1;
    }
    
    void addAtTail(int val) {
        if(list->tail == nullptr) {
            ListNode *node = (ListNode *)malloc(sizeof(ListNode));
            node->val = val;
            list->head = node;
            list->tail = node;
        } else {
            ListNode *node = (ListNode *)malloc(sizeof(ListNode));
            node->val = val;
            list->tail->next = node;
            list->tail = node;
        }
        list->len += 1;
    }
    
    void addAtIndex(int index, int val) {
        if(index > list->len) {
            return;
        }
        if(index == list->len) {
            addAtTail(val);
        } else if(index == 0) {
            addAtHead(val);
        } else {
            ListNode *pre = list->head;
            for(int i = 0; i < index - 1; i++) {
                pre = pre->next;
            }
            ListNode *node = (ListNode *)malloc(sizeof(ListNode));
            node->val = val;
            node->next = pre->next;
            pre->next = node;
            list->len += 1;
        }
        return;
    }
    
    void deleteAtIndex(int index) {
        if(index >= list->len) {
            return;
        }
        if(list->len == 1) {
            ListNode *node = list->head;
            free(node);
            list->head = nullptr;
            list->tail = nullptr;
        } else {
            if(index == list->len - 1) { // 删除尾结点
                ListNode *pre = list->head;
                for(int i = 0; i < index - 1; i++) {
                    pre = pre->next;
                }
                ListNode *node = list->tail;
                list->tail = pre;
                pre->next = nullptr;
                free(node);
            } else if(index == 0) { // 删除头结点
                ListNode *node = list->head;
                list->head = node->next;
                free(node);
            } else { // 删除中间节点
                ListNode *pre = list->head;
                for(int i = 0; i < index - 1; i++) {
                    pre = pre->next;
                }
                ListNode *node = pre->next;
                pre->next = node->next;
                free(node);
            }
        }
        list->len-=1;
        return;
    }
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */
// @lc code=end

重排链表

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

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

请将其重新排列后变为：

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

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

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

题解

合并k个升序链表

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

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

示例 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

题解

使用优先队列。

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
/*
 * @lc app=leetcode.cn id=23 lang=cpp
 *
 * [23] 合并 K 个升序链表
 */

// @lc code=start
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<int, vector<int>, greater<int>> q;
        int size = lists.size();
        int i;
        ListNode* cur;
        int val;
        ListNode* head;
        ListNode* last;
        
        if(size == 0) {
            return nullptr;
        }
        if(size == 1) {
            return lists[0];
        }

        for(i = 0; i < size; i++) {
            cur = lists[i];
            while(cur != nullptr) {
                val = cur->val;
                q.push(val);
                cur = cur->next;
            }
        }
        size = q.size();
        if(size == 0) {
            return nullptr;
        }
        for(i = 0; i < size; i++) {
            val = q.top();
            q.pop();
            ListNode* tmp = new ListNode(val);
            if(i == 0) {
                head = tmp;
                last = tmp;
            } else {
                last->next = tmp;
                last = tmp;
            }
        }
        return head;
    }
};
// @lc code=end

3 二叉树

3.1 二叉树种类

3.1.1 满二叉树

满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

img

这棵二叉树为满二叉树，也可以说深度为k，有$2^k-1$个节点的二叉树。

3.1.2 完全二叉树

img

3.1.3 二叉搜索树

前面介绍的树，都没有数值的，而二叉搜索树是有数值的了，二叉搜索树是一个有序树。

  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 它的左、右子树也分别为二叉排序树
  • 总结：左小右大

下面这两棵树都是搜索树

img

3.1.4 平衡二叉搜索树

平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

img

C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是$log_n$，注意我这里没有说unordered_map、unordered_set，unordered_map、unordered_set底层实现是哈希表。

3.1.5 B树和B+树

① B树简介

B树（Balanced Tree）是一棵多路平衡查找树。

B树的阶：通常用m表示，指的是所有结点的孩子个数的最大值。

一棵m阶的B树必须满足如下条件：

  • 每个节点最多只有$m$个子节点。
  • 每个非叶子节点（除了根）具有至少$\lceil m/2 \rceil$子节点。
  • 如果根不是叶节点，则根至少有两个子节点。
  • 具有$k$个子节点的非叶节点包含$k-1$个键。
  • 所有叶子都出现在同一水平，没有任何信息（高度一致）。
② B树的插入
③ B树的删除
④ B+树简介
⑤ B树和B+树的区别
  • B+树的非终端节点/分支结点不包含信息，而B树的非终端结点/分支结点是包含信息的
  • B+树的磁盘读写代价更低：B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了；
  • B+树查询效率更加稳定：由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当；
  • B+树便于范围查询（最重要的原因，范围查找是数据库的常态）：

3.2 遍历方式

二叉树主要有两种遍历方式：

  1. 深度优先遍历：先往深走，遇到叶子节点再往回走。
  2. 广度优先遍历：一层一层的去遍历。

那么从深度优先遍历和广度优先遍历进一步拓展，才有如下遍历方式：

  • 深度优先遍历
    • 前序遍历（递归法，迭代法）
    • 中序遍历（递归法，迭代法）
    • 后序遍历（递归法，迭代法）
  • 广度优先遍历
    • 层次遍历（迭代法）

img

最后再说一说二叉树中深度优先和广度优先遍历实现方式，我们做二叉树相关题目，经常会使用递归的方式来实现深度优先遍历，也就是实现前中后序遍历，使用递归是比较方便的。

之前我们讲栈与队列的时候，就说过栈其实就是递归的一种实现结构，也就说前中后序遍历的逻辑其实都是可以借助栈使用非递归的方式来实现的。

而广度优先遍历的实现一般使用队列来实现，这也是队列先进先出的特点所决定的，因为需要先进先出的结构，才能一层一层的来遍历二叉树。

3.3 定义

1
2
3
4
5
6
7
8
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) {}
};

注：C++的struct其实就是class，只是为了兼容c，保留了这个关键字。在C++中，struct和class没啥两样，只是struct默认是public，class默认是private，struct内数据默认是public类型的，class内数据默认是private类型的。

3.4 遍历实现

3.4.1 递归遍历

前序遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result; // 记录遍历节点顺序
        traversal(root, result);
        return result;
    }
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) return;
        vec.push_back(cur->val);    // 中
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
    }
};

中序遍历：

1
2
3
4
5
6
void traversal(TreeNode* cur, vector<int>& vec) {
    if (cur == NULL) return;
    traversal(cur->left, vec);  // 左
    vec.push_back(cur->val);    // 中
    traversal(cur->right, vec); // 右
}

后序遍历：

1
2
3
4
5
6
void traversal(TreeNode* cur, vector<int>& vec) {
    if (cur == NULL) return;
    traversal(cur->left, vec);  // 左
    traversal(cur->right, vec); // 右
    vec.push_back(cur->val);    // 中
}

3.4.2 迭代遍历

前序遍历：根左右

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();                       // 中
            st.pop();
            result.push_back(node->val);
            if (node->right) st.push(node->right);           // 右（空节点不入栈）
            if (node->left) st.push(node->left);             // 左（空节点不入栈）
        }
        return result;
    }
};

中序遍历：左根右

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) { // 指针来访问节点，访问到最底层
                st.push(cur); // 将访问的节点放进栈
                cur = cur->left;                // 左
            } else {
                cur = st.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
                st.pop();
                result.push_back(cur->val);     // 中
                cur = cur->right;               // 右
            }
        }
        return result;
    }
};

后序遍历：左右根

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            result.push_back(node->val);
            if (node->left) st.push(node->left); // 相对于前序遍历，这更改一下入栈顺序 （空节点不入栈）
            if (node->right) st.push(node->right); // 空节点不入栈
        }
        reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了
        return result;
    }
};

3.4.3 统一迭代遍历

暂略

3.4.4 层序遍历

迭代法

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:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};

递归法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 递归法
class Solution {
public:
    void order(TreeNode* cur, vector<vector<int>>& result, int depth) {
        if (cur == nullptr) return;
        if (result.size() == depth) result.push_back(vector<int>());
        result[depth].push_back(cur->val);
        order(cur->left, result, depth + 1);
        order(cur->right, result, depth + 1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        int depth = 0;
        order(root, result, depth);
        return result;
    }
};

3.5 Leetcode例题

leetcode给出的二叉树定义：

1
2
3
4
5
6
7
8
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) {}
};

完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 $1 - 2^h$ 个节点。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 树中节点的数目范围是[0, 5 * 10^4]
  • 0 <= Node.val <= 5 * 104
  • 题目数据保证输入的树是 完全二叉树

题解

直接使用递归（没有利用完全二叉树的信息）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
 * @lc app=leetcode.cn id=222 lang=cpp
 *
 * [222] 完全二叉树的节点个数
 */

// @lc code=start
class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root == nullptr) {
            return 0;
        }
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};
// @lc code=end

二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

示例 1：

image-20230322182728258

1
2
输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

示例 2：

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

提示：

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

题解

利用回溯法（深度优先遍历）

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
/*
 * @lc app=leetcode.cn id=257 lang=cpp
 *
 * [257] 二叉树的所有路径
 */

// @lc code=start
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        if(root == nullptr) {
            return res;
        }
        string path;
        path = to_string(root->val);
        dfs(root, path, res);
        return res;
    }

    void dfs(TreeNode* node, string path, vector<string>& res) {
        string opath = path;
        if(node->left == nullptr && node->right == nullptr) {
            res.push_back(path);
            return;
        }
        if(node->left != nullptr) {
            path = path + "->" + to_string(node->left->val);
            dfs(node->left, path, res);
            path = opath;
        }
        if(node->right != nullptr) {
            path = path + "->" + to_string(node->right->val);
            dfs(node->right, path, res);
            path = opath;
        }
    }
};
// @lc code=end

找树左下角的值

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

示例 1:

img

1
2
输入: root = [2,1,3]
输出: 1

示例 2:

img

1
2
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

提示:

  • 二叉树的节点个数的范围是 [1,104]
  • -231 <= Node.val <= 231 - 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
/*
 * @lc app=leetcode.cn id=513 lang=cpp
 *
 * [513] 找树左下角的值
 */

// @lc code=start
#include <vector>
using namespace std;
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        int res;
        int maxDepth = 0;
        dfs(root, 1, maxDepth, res);
        return res;
    }
    void dfs(TreeNode* node, int depth, int& maxDepth, int& res) {
        if(node->left == nullptr && node->right == nullptr) {
            if(depth > maxDepth) {
                maxDepth = depth;
                res = node->val;
            }
            return;
        }
        if(node->left != nullptr) {
            dfs(node->left, depth+1, maxDepth, res);
        }
        if(node->right != nullptr) {
            dfs(node->right, depth+1, maxDepth, res);
        }
    }
};
// @lc code=end

从中序与后序遍历序列构造二叉树*

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

img

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

示例 2:

1
2
输入：inorder = [-1], postorder = [-1]
输出：[-1]

提示:

  • 1 <= inorder.length <= 3000
  • postorder.length == inorder.length
  • -3000 <= inorder[i], postorder[i] <= 3000
  • inorder 和 postorder 都由 不同 的值组成
  • postorder 中每一个值都在 inorder 中
  • inorder 保证是树的中序遍历
  • postorder 保证是树的后序遍历

题解

我们可以发现后序遍历的数组最后一个元素代表的即为根节点。知道这个性质后，我们可以利用已知的根节点信息在中序遍历的数组中找到根节点所在的下标，然后根据其将中序遍历的数组分成左右两部分，左边部分即左子树，右边部分为右子树，针对每个部分可以用同样的方法继续递归下去构造。

fig1

image-20230322213625583

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
/*
 * @lc app=leetcode.cn id=106 lang=cpp
 *
 * [106] 从中序与后序遍历序列构造二叉树
 */

// @lc code=start
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
    int post_idx;
    unordered_map<int, int> map;
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int len = postorder.size();
        post_idx = len - 1;
        int idx = 0;
        for(int val : inorder) {
            map[val] = idx;
            idx++;
        }
        return construct(0, len-1, inorder, postorder);
    }
    
    TreeNode* construct(int left, int right, vector<int>& inorder, vector<int>& postorder) {
        // 结束条件
        if(left > right) {
            return nullptr;
        }
        // 后序遍历的最后一个值就是子树的根节点
        int val = postorder[post_idx];
        TreeNode* root = new TreeNode(val);
        post_idx--; // 下标减1
        // 得到该值在中序遍历中的坐标，坐标左边是左子树，右边是右子树
        int idx = map[val];
        // 根据后序遍历特点，先构造右子树
        root->right = construct(idx+1, right, inorder, postorder);
        root->left = construct(left, idx-1, inorder, postorder);
        return root;
    }
};
// @lc code=end

最大二叉树

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

  1. 创建一个根节点，其值为 nums 中的最大值。
  2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
  3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树 。

示例 1：

image-20230322220122865

1
2
3
4
5
6
7
8
9
10
11
12
输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
    - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
        - 空数组，无子节点。
        - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
            - 空数组，无子节点。
            - 只有一个元素，所以子节点是一个值为 1 的节点。
    - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
        - 只有一个元素，所以子节点是一个值为 0 的节点。
        - 空数组，无子节点。

示例 2：

image-20230322220147899

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

提示：

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000
  • 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
36
37
38
39
40
41
42
/*
 * @lc app=leetcode.cn id=654 lang=cpp
 *
 * [654] 最大二叉树
 */

// @lc code=start
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
    unordered_map<int, int> map;
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        int idx = 0;
        for(int val : nums) {
            map[val] = idx;
            idx++;
        }
        return constructor(nums, 0, nums.size()-1);
    }

    TreeNode* constructor(vector<int>& nums, int left, int right) {
        if(left > right) {
            return nullptr;
        }
        // 在left和right之间找出最大值和下标
        int m = 0;
        for(int i = left; i <= right; i++) {
            m = max(m, nums[i]);
        }
        TreeNode* root = new TreeNode(m);
        // 最大值下标
        int idx = map[m];
        // 先构造左子树
        root->left = constructor(nums, left, idx-1);
        // 右子树
        root->right = constructor(nums, idx+1, right);
        return root;
    }
};
// @lc code=end

二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

示例 1:

image-20230322222440033

1
2
输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

示例 2:

image-20230322222454162

1
2
输入：root = [4,2,7,1,3], val = 5
输出：[]

提示：

  • 数中节点数在 [1, 5000] 范围内
  • 1 <= Node.val <= 107
  • root 是二叉搜索树
  • 1 <= val <= 107

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        while(root != nullptr) {
            if(val > root->val) {
                root = root->right;
            } else if(val < root->val) {
                root = root->left;
            } else {
                break;
            }
        }
        return root;
    }
};

二叉搜索树的最小绝对值差

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

示例 1：

image-20230322223213280

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

示例 2：

image-20230322223228372

1
2
输入：root = [1,0,48,null,null,12,49]
输出：1

提示：

  • 树中节点的数目范围是 [2, 10^4]
  • 0 <= Node.val <= 10^5

题解

二叉搜索树中序遍历后得到的是递增序列，最小差值就是递增序列相邻两个元素的差值的最小值。

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
#include <math.h>
#include <vector>
#define INT_MAX 0x7fffffff
using namespace std;
class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        vector<int> v; 
        int res = INT_MAX;
        inorder(root, v);
        for(int i = 1; i < v.size(); i++) {
            res = min(v[i]-v[i-1], res);
        }
        return res;
    }
	// 中序遍历
    void inorder(TreeNode* node, vector<int>& v) {
        if(node == nullptr) {
            return ;
        }
        inorder(node->left, v);
        v.push_back(node->val);
        inorder(node->right, v);
    }
};

二叉搜索树中的众数*

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

  • 结点左子树中所含节点的值 小于等于 当前节点的值
  • 结点右子树中所含节点的值 大于等于 当前节点的值
  • 左子树和右子树都是二叉搜索树

示例 1：

image-20230322230852300

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

示例 2：

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

提示：

  • 树中节点的数目在范围 [1, 104] 内
  • -105 <= Node.val <= 105

进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

题解

暴力统计法：

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
class Solution {
private:

void searchBST(TreeNode* cur, unordered_map<int, int>& map) { // 前序遍历
    if (cur == NULL) return ;
    map[cur->val]++; // 统计元素频率
    searchBST(cur->left, map);
    searchBST(cur->right, map);
    return ;
}
bool static cmp (const pair<int, int>& a, const pair<int, int>& b) {
    return a.second > b.second;
}
public:
    vector<int> findMode(TreeNode* root) {
        unordered_map<int, int> map;
        vector<int> result;
        if (root == NULL) return result;
        searchBST(root, map);
        vector<pair<int, int>> vec(map.begin(), map.end());
        sort(vec.begin(), vec.end(), cmp); // 给频率排个序
        result.push_back(vec[0].first);
        for (int i = 1; i < vec.size(); i++) {
            if (vec[i].second == vec[0].second) result.push_back(vec[i].first);
            else break;
        }
        return result;
    }
};

利用题中搜索二叉树的特点：

搜索树在中序遍历的过程中，就是有序序列，所以此时的问题相当于给出如果给出一个有序数组，求最大频率的元素集合。

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 {
private:
    int count;
    int maxCount;
    TreeNode* pre;
    vector<int> result;
    void searchBST(TreeNode* cur) {
        if (cur == NULL) return ;

        searchBST(cur->left);       // 左
                                    // 中
        if (pre == NULL) { // 第一个节点
            count = 1;
        } else if (pre->val == cur->val) { // 与前一个节点数值相同
            count++;
        } else { // 与前一个节点数值不同
            count = 1;
        }
        pre = cur; // 更新上一个节点

        if (count == maxCount) { // 如果和最大值相同，放进result中
            result.push_back(cur->val);
        }

        if (count > maxCount) { // 如果计数大于最大值
            maxCount = count;
            result.clear();     // 很关键的一步，不要忘记清空result，之前result里的元素都失效了
            result.push_back(cur->val);
        }

        searchBST(cur->right);      // 右
    }

public:
    vector<int> findMode(TreeNode* root) {
        int count = 0; // 记录元素出现次数
        int maxCount = 0; // 最大的出现次数
        TreeNode* pre = NULL; // 记录前一个节点
        result.clear();

        searchBST(root);
        return result;
    }
};

二叉搜索树的最近公共祖先

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

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

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

image-20230323125044252

示例 1:

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

示例 2:

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

说明:

  • 所有节点的值都是唯一的。
  • p、q 为不同节点且均存在于给定的二叉搜索树中。

题解

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
/*
 * @lc app=leetcode.cn id=235 lang=cpp
 *
 * [235] 二叉搜索树的最近公共祖先
 */

// @lc code=start
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* res;
        if(root == nullptr) {
            return nullptr;
        }
        if(p == root || q == root) {
            return root;
        }
        if(p->val < root->val && q->val < root->val) { // pq都在右侧
            TreeNode* res = lowestCommonAncestor(root->left, p, q);
        } else if(p->val > root->val && q->val > root->val) { // pq都在左侧
            TreeNode* res = lowestCommonAncestor(root->right, p, q);
        } else { // pq在两侧，或者有一个为root，则只能是root为最近公共祖先
            return root;
        }
        return res;
    }
};
// @lc code=end

二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

示例 1：

image-20230323131711674

1
2
输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]

解释：另一个满足题目要求可以通过的树是：

image-20230323131731042

示例 2：

1
2
输入：root = [40,20,60,10,30,50,70], val = 25
输出：[40,20,60,10,30,50,70,null,null,25]

示例 3：

1
2
输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
输出：[4,2,7,1,3,5]

提示：

  • 树中的节点数将在 [0, 104]的范围内。
  • -108 <= Node.val <= 108
  • 所有值 Node.val 是 独一无二 的。
  • -108 <= val <= 108
  • 保证 val 在原始BST中不存在。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
 * @lc app=leetcode.cn id=701 lang=cpp
 *
 * [701] 二叉搜索树中的插入操作
 */

// @lc code=start
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root == nullptr) {
            return new TreeNode(val);
        }
        if(val > root->val) { // 向右走
            root->right = insertIntoBST(root->right, val);
        } else {
            root->left = insertIntoBST(root->left, val);
        }
        return root;
    }
};
// @lc code=end

删除二叉搜索树中的节点*

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

  1. 首先找到需要删除的节点；
  2. 如果找到了，删除它。

示例 1:

image-20230323150250146

1
2
3
4
输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。

另一个正确答案是[5,2,6,null,4,null,7]。

image-20230323150313175

示例 2:

1
2
3
输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点

示例 3:

1
2
输入: root = [], key = 0
输出: []

提示:

  • 节点数的范围 [0, 104].
  • -105 <= Node.val <= 105
  • 节点值唯一
  • root 是合法的二叉搜索树
  • -105 <= key <= 105

进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。

题解

把二叉搜索树转换为累加树

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

  • 节点的左子树仅包含键 小于 节点键的节点。
  • 节点的右子树仅包含键 大于 节点键的节点。
  • 左右子树也必须是二叉搜索树。

示例 1：

image-20230323155357537

1
2
输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例 2：

1
2
输入：root = [0,null,1]
输出：[1,null,1]

示例 3：

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

示例 4：

1
2
输入：root = [3,2,4,1]
输出：[7,9,4,10]

提示：

  • 树中的节点数介于 0 和 104 之间。
  • 每个节点的值介于 -104 和 104 之间。
  • 树中的所有值 互不相同 。
  • 给定的树为二叉搜索树。

题解

利用逆向中序遍历（右根左）。

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
/*
 * @lc app=leetcode.cn id=538 lang=cpp
 *
 * [538] 把二叉搜索树转换为累加树
 */

// @lc code=start
class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        int sum = 0; // 累加和
        inorderReversed(root, sum);
        return root;
    }

    void inorderReversed(TreeNode* node, int& sum) {
        if(node == nullptr) {
            return;
        }
        inorderReversed(node->right, sum);
        sum += node->val;
        node->val = sum;
        inorderReversed(node->left, sum);
    }
};
// @lc code=end

填充每个节点的下一个右侧节点指针

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

1
2
3
4
5
6
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

示例 1：

image-20230424195730328

1
2
3
输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。

示例 2:

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

提示：

  • 树中节点的数量在 [0, 212 - 1] 范围内
  • -1000 <= node.val <= 1000

进阶：

  • 你只能使用常量级额外空间。
  • 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

题解

使用层次遍历。

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
#include <queue>
using namespace std;
class Solution {
public:
    Node* connect(Node* root) {
        if(root == nullptr) {
            return nullptr;
        }
        queue<Node*> q1;
        queue<Node*> q2;
        q1.push(root);
        while(!q1.empty() || !q2.empty()) {
            while(!q1.empty()) {
                Node* node = q1.front();
                q1.pop();
                if(node->left)
                    q2.push(node->left);
                if(node->right)
                    q2.push(node->right);
                if(!q1.empty()) {
                    node->next = q1.front();
                } else {
                    node->next = nullptr;
                }
            }
            while(!q2.empty()) {
                Node* node = q2.front();
                q2.pop();
                if(node->left)
                    q1.push(node->left);
                if(node->right)
                    q1.push(node->right);
                if(!q2.empty()) {
                    node->next = q2.front();
                } else {
                    node->next = nullptr;
                }
            }
        }
        return root;
    }
};
// @lc code=end

4 哈希表

Leetcode例题

查找共用字符*

给你一个字符串数组 words ，请你找出所有在 words 的每个字符串中都出现的共用字符（ 包括重复字符），并以数组形式返回。你可以按 任意顺序 返回答案。

示例 1：

1
2
输入：words = ["bella","label","roller"]
输出：["e","l","l"]

示例 2：

1
2
输入：words = ["cool","lock","cook"]
输出：["c","o"]

提示：

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 100
  • words[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
/*
 * @lc app=leetcode.cn id=1002 lang=cpp
 *
 * [1002] 查找共用字符
 */

// @lc code=start
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
    vector<string> commonChars(vector<string>& words) {
        vector<string> res;
        vector<int> map(26, INT_MAX);
        vector<int> temp(26);
        for(const string& word : words) {
            fill(temp.begin(), temp.end(), 0);
            for(char ch : word) {  
                ++temp[ch - 'a'];
            }
            // 更新map
            for(int i = 0; i < 26; i++) {
                map[i] = min(map[i], temp[i]);
            }
        }
        for(int i = 0; i < 26; i++) {
            for(int j = 0; j < map[i]; j++) {
                res.emplace_back(1, i + 'a');
            }
        }
        return res;
    }
};
// @lc code=end

两个数组的交集②

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

示例 1：

1
2
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

示例 2:

1
2
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

提示：

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000

题解

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
/*
 * @lc app=leetcode.cn id=350 lang=cpp
 *
 * [350] 两个数组的交集 II
 */

// @lc code=start
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        unordered_map<int, int> map;
        for(int& num : nums1) {
            if(map.find(num) != map.end()) {
                map[num]++;
            } else {
                map[num] = 1;
            }
        }
        for(int& num : nums2) {
            if(map.find(num) != map.end()) {
                res.push_back(num);
                if(map[num] == 1) { // 只重复一次
                    map.erase(num); // 删除键
                } else {
                    map[num]--; // 值减1
                }
            }
        }
        return res;
    }
};
// @lc code=end

四数相加②

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

  • 0 <= i, j, k, l < n
  • nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：

1
2
3
4
5
6
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

示例 2：

1
2
输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1

提示：

  • n == nums1.length
  • n == nums2.length
  • n == nums3.length
  • n == nums4.length
  • 1 <= n <= 200
  • -228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228

题解

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
/*
 * @lc app=leetcode.cn id=454 lang=cpp
 *
 * [454] 四数相加 II
 */

// @lc code=start
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int, int> map1; // 记录nums1+nums2之和 k:和 v:次数
        unordered_map<int, int> map2;
        int res = 0;
        for(int& num1 : nums1) {
            for(int& num2 : nums2) {
                if(map1.find(num1 + num2) != map1.end()) {
                    map1[num1 + num2]++;
                } else {
                    map1[num1 + num2] = 1;
                }
            }
        }

        for(int& num3 : nums3) {
            for(int& num4 : nums4) {
                if(map2.find(num3 + num4) != map2.end()) {
                    map2[num3 + num4]++;
                } else {
                    map2[num3 + num4] = 1;
                }
            }
        }
        for(auto p : map1) {
            if(map2.find(-p.first) != map2.end()) {
                res += p.second * map2[-p.first];
            }
        }
        return res;
    }
};
// @lc code=end

注：第二个map也可以不用。

四数之和*

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

  • 0 <= a, b, c, d < n
  • a、b、c 和 d 互不相同
  • nums[a] + nums[b] + nums[c] + nums[d] == target

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= nums.length <= 200
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109

题解

独一无二的出现次数

给你一个整数数组 arr，请你帮忙统计数组中每个数的出现次数。

如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。

示例 1：

1
2
3
输入：arr = [1,2,2,1,1,3]
输出：true
解释：在该数组中，1 出现了 3 次，2 出现了 2 次，3 只出现了 1 次。没有两个数的出现次数相同。

示例 2：

1
2
输入：arr = [1,2]
输出：false

示例 3：

1
2
输入：arr = [-3,0,1,-3,1,1,1,-3,10,0]
输出：true

提示：

  • 1 <= arr.length <= 1000
  • -1000 <= arr[i] <= 1000

题解

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
/*
 * @lc app=leetcode.cn id=1207 lang=cpp
 *
 * [1207] 独一无二的出现次数
 */

// @lc code=start
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
    bool uniqueOccurrences(vector<int>& arr) {
        unordered_map<int, int> map1;
        unordered_map<int, int> map2;
        for(int& num : arr) {
            map1[num]++;
        }
        for(unordered_map<int, int>::iterator iter = map1.begin(); iter != map1.end(); iter++) {
            if(map2.find(iter->second) == map2.end()) {
                map2[iter->second] = iter->second;
            } else {
                return false;
            }
        }
        return true;
    }
};
// @lc code=end

有效的数独

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

  • 一个有效的数独（部分已被填充）不一定是可解的。
  • 只需要根据以上规则，验证已经填入的数字是否有效即可。
  • 空白格用 '.' 表示。

示例 1：

image-20230426151857151

1
2
3
4
5
6
7
8
9
10
11
输入：board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true

示例 2：

1
2
3
4
5
6
7
8
9
10
11
12
输入：board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

提示：

  • board.length == 9
  • board[i].length == 9
  • board[i][j] 是一位数字（1-9）或者 '.'

题解

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/*
 * @lc app=leetcode.cn id=36 lang=cpp
 *
 * [36] 有效的数独
 */

// @lc code=start
#include <vector>
#include <unordered_map>
#include <iostream>
using namespace std;
class Solution {
    unordered_map<char, char> map;
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        // 逐行扫描
        for(int i = 0; i < 9; i++) { // 行
            for(int j = 0; j < 9; j++) { // 列
                if(map.find(board[i][j]) == map.end()) {
                    if(board[i][j] == '.') {
                        continue;
                    }
                    map[board[i][j]] = board[i][j];
                } else {
                    return false;
                }
            }
            map.clear();
        }
        // 逐列扫描
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) { 
                if(map.find(board[j][i]) == map.end()) {
                    if(board[j][i] == '.') {
                        continue;
                    }
                    map[board[j][i]] = board[j][i];
                } else {
                    return false;
                }
            }
            map.clear();
        }
        // 3*3九宫格扫描
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 3; j++) {
                if(map.find(board[j][i]) == map.end()) {
                    if(board[j][i] == '.') {
                        continue;
                    }
                    map[board[j][i]] = board[j][i];
                } else {
                    return false;
                }
            }
            if((i + 1) % 3 == 0) {
                map.clear();
            }
        }
        for(int i = 0; i < 9; i++) {
            for(int j = 3; j < 6; j++) {
                if(map.find(board[j][i]) == map.end()) {
                    if(board[j][i] == '.') {
                        continue;
                    }
                    map[board[j][i]] = board[j][i];
                } else {
                    return false;
                }
            }
            if((i + 1) % 3 == 0) {
                map.clear();
            }
        }
        for(int i = 0; i < 9; i++) {
            for(int j = 6; j < 9; j++) {
                if(map.find(board[j][i]) == map.end()) {
                    if(board[j][i] == '.') {
                        continue;
                    }
                    map[board[j][i]] = board[j][i];
                } else {
                    return false;
                }
            }
            if((i + 1) % 3 == 0) {
                map.clear();
            }
        }

        return true;
    }
};
// @lc code=end

同构字符串

给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

示例 1:

1
2
输入：s = "egg", t = "add"
输出：true

示例 2：

1
2
输入：s = "foo", t = "bar"
输出：false

示例 3：

1
2
输入：s = "paper", t = "title"
输出：true

提示：

  • 1 <= s.length <= 5 * 104
  • t.length == s.length
  • s 和 t 由任意有效的 ASCII 字符组成

题解

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
/*
 * @lc app=leetcode.cn id=205 lang=cpp
 *
 * [205] 同构字符串
 */

// @lc code=start
#include <string>
#include <map>
#include <iostream>
using namespace std;
class Solution {
public:
    bool isIsomorphic(string s, string t) {
        map<char, char> mapping1;
        map<char, char> mapping2;
        for(int i = 0; i < s.size(); i++) {
            if(mapping1.find(s[i]) == mapping1.end()) {
                mapping1[s[i]] = t[i];
            } else {
                if(mapping1[s[i]] != t[i]) {
                    return false;
                }
            }
            if(mapping2.find(t[i]) == mapping2.end()) {
                mapping2[t[i]] = s[i];
            } else {
                if(mapping2[t[i]] != s[i]) {
                    return false;
                }
            }
        }
        return true;
    }
};
// @lc code=end

存在重复元素②

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

题解

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
/*
 * @lc app=leetcode.cn id=219 lang=cpp
 *
 * [219] 存在重复元素 II
 */

// @lc code=start
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> map;
        for(int i = 0; i < nums.size(); i++) {
            if(map.find(nums[i]) == map.end()) {
                map[nums[i]] = i;
                continue;
            }
            if(i - map[nums[i]] <= k) {
                return true;
            } else {
                map[nums[i]] = i;
            }
        }
        return false;
    }
};
// @lc code=end

H指数*

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。

h 指数的定义：h 代表“高引用次数”，一名科研人员的 h指数是指他（她）的 （n 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。且其余的 n - h 篇论文每篇被引用次数 不超过 h 次。

如果 h 有多种可能的值，h 指数 是其中最大的那个。

示例 1：

1
2
3
4
输入：citations = [3,0,6,1,5]
输出：3 
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
     由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。

示例 2：

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

提示：

  • n == citations.length
  • 1 <= n <= 5000
  • 0 <= citations[i] <= 1000

题解

image-20230426173828231

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
 * @lc app=leetcode.cn id=274 lang=cpp
 *
 * [274] H 指数
 */

// @lc code=start
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
class Solution {
public:
    int hIndex(vector<int>& citations) {
        int h = 0;
        sort(citations.begin(), citations.end());
        for(int i = citations.size() - 1; i >= 0 && citations[i] > h; i--) {
            h++;
        }
        return h;
    }
};
// @lc code=end

5 单调栈

5.1 简介

单调栈，顾名思义就是栈内元素单调按照递增（递减）顺序排列的栈。

  • 单调递增栈： 从栈顶往栈底看，是单调递增的关系（含相等）
  • 单调递减栈： 从栈顶往栈底看，是单调递减的关系（含相等）

例子：现在有一组数：3，4，2，6，4，5，2，3，如果从左往右依次进单调递增栈，那么是这样操作的：

在这里插入图片描述

伪代码

1
2
3
4
5
6
7
8
9
10
11
stack<int> st;
//此处一般需要给数组最后添加结束标志符
for (遍历这个数组) {
	// 如果栈不为空且栈顶元素比压栈元素小，则栈顶元素出栈并作计算与更新结果，然后继续下一轮比较，直至该元素可以入栈；
    // 否则，（即栈为空，或栈顶元素大于等于压栈元素），直接入栈即可
    while ( !st.empty() && vec[st.top()] < vec[i] ) {
        st.pop();
        // Do something
    }
    st.push(i);  // 数组内的元素都要入栈，但入栈的是其下标
}

注意事项：

  • 为了保证栈内元素最后都能出栈，需要在数组结尾添加一个特殊的数字：
    • 对单调递增栈，在数组末尾添加一个最大数，如 INT_MAX
    • 对单调递减栈，在数组末尾添加一个最小数，如 INT_MIN
  • 数组中的所有元素都要入栈一次和出栈一次，除了最后一个特殊元素；
  • 当一个元素出栈的时候，做计算，更新答案；
  • 当一个元素即将出栈时，记住整个栈内元素具有单调性，很多时候需要利用这个特性去做计算；
  • 一个元素可能会令栈中若干个元素出栈，但也可能是直接入栈

5.2 Leetcode例题

每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

1
2
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

1
2
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

1
2
输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：

  • 1 <= temperatures.length <= 105
  • 30 <= temperatures[i] <= 100

题解

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
/*
 * @lc app=leetcode.cn id=739 lang=cpp
 *
 * [739] 每日温度
 */

// @lc code=start
#include <vector>
#include <stack>
using namespace std;
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int len = temperatures.size();
        vector<int> res(len, 0);
        stack<int> s; // 单增栈
        for(int i = 0; i < len; i++) {
            // 当入栈元素大于栈顶元素时，逐个出栈
            while(!s.empty() && temperatures[i] > temperatures[s.top()]) { 
                int idx = s.top();
                res[idx] = i - idx; // 下标相减即为结果
                s.pop();
            }
            s.push(i);
        }
        return res;
    }
};
// @lc code=end

下一个更大元素①

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

示例 1：

1
2
3
4
5
6
输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
- 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
- 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。

示例 2：

1
2
3
4
5
输入：nums1 = [2,4], nums2 = [1,2,3,4].
输出：[3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
- 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。

提示：

  • 1 <= nums1.length <= nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 104
  • nums1和nums2中所有整数 互不相同
  • nums1 中的所有整数同样出现在 nums2 中

进阶：你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？

题解

注意到元素不重复，可以使用单调栈和哈希表。

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
/*
 * @lc app=leetcode.cn id=496 lang=cpp
 *
 * [496] 下一个更大元素 I
 */

// @lc code=start
#include <vector>
#include <stack>
#include <unordered_map>
using namespace std;
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        int len1 = nums1.size();
        int len2 = nums2.size();
        stack<int> s; // 单增栈
        unordered_map<int, int> map;
        vector<int> res;
        for(int i = 0; i < len2; i++) {
            while(!s.empty() && nums2[i] > s.top()) {
                map[s.top()] = nums2[i];
                s.pop();
            }
            s.push(nums2[i]);
        }
        // 将剩余元素出栈
        while(!s.empty()) {
            map[s.top()] = -1;
            s.pop();
        }
        for(int i = 0; i < len1; i++) {
            res.push_back(map[nums1[i]]);
        }
        return res;
    }
};
// @lc code=end

下一个更大元素②

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

示例 1:

1
2
3
4
5
输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数； 
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

示例 2:

1
2
输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]

提示:

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

题解

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
/*
 * @lc app=leetcode.cn id=503 lang=cpp
 *
 * [503] 下一个更大元素 II
 */

// @lc code=start
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> res(nums.size(), -1);
        stack<int> s; // 单增栈，存下标
        int lastIdx; // 记录栈底的下标
        for(int i = 0; i < nums.size(); i++) {
            while(!s.empty() && nums[i] > nums[s.top()]) {
                res[s.top()] = nums[i];
                s.pop();
            }
            if(s.empty()) { // 当栈空时，需要更改栈底下标
                lastIdx = i;
            }
            s.push(i);
        }
        // 二次遍历，直到栈底元素的下标
        for(int i = 0; i <= lastIdx; i++) {
            while(nums[i] > nums[s.top()]) {
                res[s.top()] = nums[i];
                s.pop();
            }
        }
        return res;
    }
};
// @lc code=end

接雨水

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

示例 1：

img

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

题解

6 字符串

Leetcode例题

反转字符串②

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

  • 如果剩余字符少于 k 个，则将剩余字符全部反转。
  • 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：

1
2
输入：s = "abcdefg", k = 2
输出："bacdfeg"

示例 2：

1
2
输入：s = "abcd", k = 2
输出："bacd"

提示：

  • 1 <= s.length <= 104
  • s 仅由小写英文组成
  • 1 <= k <= 104

题解

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
/*
 * @lc app=leetcode.cn id=541 lang=cpp
 *
 * [541] 反转字符串 II
 */

// @lc code=start
#include <string>
using namespace std;
class Solution {
public:
    string reverseStr(string s, int k) {
        int count = 0;
        int start = 0;
        for(int i = 0; i < s.size(); i++) {
            // 计数+1
            count++;
            if(count != 2 * k) {
                continue;
            }
            // 从start开始反转前k个字符
            reverseString(s, start, k);
            // 重新计数
            count = 0;
            start = i + 1;
        }
        if(count < k) { // 计数小于k，则反转前count个字符
            reverseString(s, start, count);
        } else if(k <= count < 2 * k) { // 计数大于k，则反转前k个字符
            reverseString(s, start, k);
        }
        return s;
    }
    // reverse函数
    void reverseString(string& s, int start, int k) {
        char c;
        int left = start, right = start + k - 1;
        while(left < right) {
            char c = s[left];
            s[left] = s[right];
            s[right] = c;
            left++;
            right--;
        }
    }
};
// @lc code=end

反转字符串中的单词

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

1
2
输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

1
2
3
输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

1
2
3
输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

提示：

  • 1 <= s.length <= 104
  • s 包含英文大小写字母、数字和空格 ' '
  • s 中 至少存在一个 单词

题解

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
/*
 * @lc app=leetcode.cn id=151 lang=cpp
 *
 * [151] 反转字符串中的单词
 */

// @lc code=start
#include <string>
#include <unordered_map>
using namespace std;
class Solution {
public:
    string reverseWords(string s) {
        int seq = 0;
        string temp;
        string res;
        unordered_map<int, string> map;
        for(int i = 0; i < s.size(); i++) {
            if(s[i] == ' ') {
                if(temp.size() != 0) {
                    map[seq] = temp;
                    temp.clear();
                    seq++;
                }
                continue;
            }
            temp += s[i];
        }
        // 处理最后一个字符串
        if(temp.size() != 0) {
            map[seq] = temp;
        }
        // 反向遍历
        for(int i = map.size() - 1; i >= 0; i--) {
            res += map[i] + " ";
        }
        return res.substr(0, res.size() - 1);
    }
};
// @lc code=end

重复的子字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1:

1
2
3
输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

示例 2:

1
2
输入: s = "aba"
输出: false

示例 3:

1
2
3
输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

提示：

  • 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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/*
 * @lc app=leetcode.cn id=459 lang=cpp
 *
 * [459] 重复的子字符串
 */

// @lc code=start
#include <string>
using namespace std;
class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int len = s.size();
        int i, j, k;
        // 分成几个部分
        for(i = 1; i <= len/2; i++) {
            bool flag = true;
            // 对分割后的第一部分的每一位进行遍历
            for(j = 0; j < i; j++) {
                // 对后面的每个部分对应的位置进行遍历比较
                for(k = j + i; k < len; k = k + i) {
                    if(s[j] != s[k]) {
                        flag = false;
                        break;
                    }
                }
                if(!flag) {
                    flag = false;
                    break;
                }
            }
            if(flag) {
                printf("%d", k);
                if(k == len - 1 + i) {
                    return true;
                }
            }
        }
        return false;
    }
};
// @lc code=end

7 双指针

Leetcode例题

8 栈与队列

Leetcode例题

删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

1
2
3
4
输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

提示：

  1. 1 <= S.length <= 20000
  2. S 仅由小写英文字母组成。

题解

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
/*
 * @lc app=leetcode.cn id=1047 lang=cpp
 *
 * [1047] 删除字符串中的所有相邻重复项
 */

// @lc code=start
#include <string>
#include <deque>
using namespace std;
class Solution {
public:
    string removeDuplicates(string s) {
        deque<char> queue;
        string res;
        bool flag;
        for(int i = 0; i < s.size(); i++) {
            flag = false;
            while(!queue.empty() && queue.back() == s[i]) {
                queue.pop_back();
                flag = true;
            }
            if(!flag) {
                queue.push_back(s[i]);
            }
        }
        while(!queue.empty()) {
            res += queue.front();
            queue.pop_front();
        }
        return res;
    }
};
// @lc code=end

另一种方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    string removeDuplicates(string s) {
        string stk;
        for (char ch : s) {
            if (!stk.empty() && stk.back() == ch) {
                stk.pop_back();
            } else {
                stk.push_back(ch);
            }
        }
        return stk;
    }
};

滑动窗口最大值*

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2：

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

提示：

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

题解

使用优先队列。

image-20230330173620174

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        priority_queue<pair<int, int>> q;
        for (int i = 0; i < k; ++i) {
            q.emplace(nums[i], i);
        }
        vector<int> ans = {q.top().first};
        for (int i = k; i < n; ++i) {
            q.emplace(nums[i], i);
            // 当最大值的下标小于窗口的左边界时，弹出最大值
            while (q.top().second <= i - k) {
                q.pop();
            }
            ans.push_back(q.top().first);
        }
        return ans;
    }
};

前k个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

1
2
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

1
2
输入: nums = [1], k = 1
输出: [1]

提示：

  • 1 <= nums.length <= 105
  • k 的取值范围是 [1, 数组中不相同的元素的个数]
  • 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/*
 * @lc app=leetcode.cn id=347 lang=cpp
 *
 * [347] 前 K 个高频元素
 */

// @lc code=start
#include <vector>
#include <unordered_map>
#include <queue>
#include<utility>
using namespace std;

class Compare {
public:
    bool operator()(pair<int, int>& p1, pair<int, int>&  p2) const {
        return p1.second < p2.second;
    }
};

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> res;
        unordered_map<int ,int> map;
        priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> q;
        for(int i = 0; i < nums.size(); i++) {
            if(map.find(nums[i]) == map.end()) {
                map.insert({nums[i], 1});
            } else {
                map[nums[i]] += 1;
            }
        }
        for(auto it : map){
            q.emplace(it.first, it.second);
        }
        for(int i = 0; i < k; i++) {
            res.push_back(q.top().first);
            q.pop();
        }
        return res;
    }
};
// @lc code=end

LRU缓存

请你设计并实现一个满足 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

题解

双向链表+哈希表

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
59
60
61
/*
 * @lc app=leetcode.cn id=146 lang=cpp
 *
 * [146] LRU 缓存
 */

// @lc code=start
#include <unordered_map>
#include <list>
using namespace std;
class LRUCache {
    unordered_map<int, int> map;
    list<int> queue;
    int capacity;
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
    }
    
    int get(int key) {
        if(map.find(key) == map.end()) {
            return -1;
        }
        // 调整
        update(key);
        return map[key];
    }
    
    void put(int key, int value) {
        if(map.find(key) == map.end()) { // 不存在key，需要插入
            if(queue.size() < capacity) { // 尚有空间
                map[key] = value;
                queue.push_back(key);
            } else {
                map[key] = value;
                int tmp = queue.front();
                map.erase(tmp);
                queue.pop_front();
                queue.push_back(key);
            }
        } else { // 存在key，则更新
            map[key] = value;
            // 调整
            update(key);
        }
        return;
    }

    void update(int key) {
        list<int>::iterator iter;
        for(iter = queue.begin(); iter != queue.end(); iter++) {
            if(*iter != key) { 
                continue;
            }
            queue.erase(iter);
            queue.push_back(key);
            break;
        }
        return;
    }
};

最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示：

  • -231 <= val <= 231 - 1
  • pop、top 和 getMin 操作总是在 非空栈 上调用
  • push, pop, top, and getMin最多被调用 3 * 104 次

题解

栈+双向链表。

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
/*
 * @lc app=leetcode.cn id=155 lang=cpp
 *
 * [155] 最小栈
 */

// @lc code=start
#include <stack>
#include <list>
#include <iostream>
using namespace std;
class MinStack {
    stack<int> myStack;
    list<int> myList;
public:
    MinStack() {

    }
    
    void push(int val) {
        myStack.push(val);
        list<int>::iterator iter;
        for(iter = myList.begin(); iter != myList.end(); iter++) {
            if(*iter <= val) {
                continue;
            }
            myList.insert(iter, val);
            return;
        }
        myList.push_back(val);
        return;
    }
    
    void pop() {
        int val = myStack.top();
        myStack.pop();
        list<int>::iterator iter;
        for(iter = myList.begin(); iter != myList.end(); iter++) {
            if(*iter != val) {
                continue;
            }
            myList.erase(iter);
            break;
        }
        return;
    }
    
    int top() {
        return myStack.top();
    }
    
    int getMin() {
        return myList.front();
    }
};

9 堆

Leetcode例题

数据流的中位数*

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

  • 例如 arr = [2,3,4] 的中位数是 3 。
  • 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

  • MedianFinder()初始化 MedianFinder 对象。
  • void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
  • double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
13
输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]

解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

提示:

  • -105 <= num <= 105
  • 在调用 findMedian 之前，数据结构中至少有一个元素
  • 最多 5 * 104 次调用 addNum 和 findMedian

题解

image-20230424173203323

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
class MedianFinder {
public:
    priority_queue<int, vector<int>, less<int>> queMin;
    priority_queue<int, vector<int>, greater<int>> queMax;

    MedianFinder() {}

    void addNum(int num) {
        if (queMin.empty() || num <= queMin.top()) {
            queMin.push(num);
            if (queMax.size() + 1 < queMin.size()) {
                queMax.push(queMin.top());
                queMin.pop();
            }
        } else {
            queMax.push(num);
            if (queMax.size() > queMin.size()) {
                queMin.push(queMax.top());
                queMax.pop();
            }
        }
    }

    double findMedian() {
        if (queMin.size() > queMax.size()) {
            return queMin.top();
        }
        return (queMin.top() + queMax.top()) / 2.0;
    }
};