算法刷题

这篇主要总结力扣上一些经典的算法题目，参考网站代码随想录 (programmercarl.com)（该博客仅作为自学使用）

文章的分类不是严格按照基本数据结构来分类的，而是按照力扣算法题的共性总结，可能是使用了某种共同的数据结构、解题思想或某种共同的算法；

2023/2/20 8:28 刷题这部分暂时也搁置一段时间，主要是这个东西只需要在短时间内大量刷题就可以，而对于考研来说现阶段刷题的收益太低了，现阶段几乎用不到这些算法相关的知识点；

2023/10/24 20:53 时隔大半年，因为种种原因我又回来刷题了…看了看自己做的这些刷题整理说实话挺佩服这么有毅力能够坚持这么麻烦的事情干这么久…之后的话可能就不会继续这么详细的做笔记（效率太低了，刷题不是这么个刷法），可能遇到的一些比较经典好玩的题型我会补充总结到这里面。因为最开始刷题和之后复习数据结构使用的都是c/c++语言，所以后续刷题也保持用c/c++语言；

一、数组

0.数组概述

  • 数组是存放在连续内存空间上的相同类型的数据的集合；

  • 因为数组在内存空间的地址是连续的，所以针对数组不能删除某元素只能覆盖某元素；

一维数组

二维数组

1.二分查找

题目要求：

解析：

本题可以直接暴力遍历数组，以查找数组中不重复的某个元素（由假设得来）；

但是直接使用暴力遍历会导致时间复杂度极高，题干中出现关键词“有序”“不重复元素”，可以考虑使用二分法；

使用二分法要注意原始区间是双闭还是半闭半开，这将影响判断条件的书写；

解题思路1：

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
        while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
            int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target 在左区间，所以[left, middle - 1]
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，所以[middle + 1, right]
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

解题思路2：

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)
        while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle; // target 在左区间，在[left, middle)中
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，在[middle + 1, right)中
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

2.移除元素

题目要求：

解析：

这道题直接看示例很容易把人搞晕不知道该干什么，实际上就是一个简单的删除数组中所有值等于val的元素并返回最终数组的大小；

因为数组内存空间连续，只能使用后面的元素将前面的元素覆盖，所以我们有两种解题思路；

一种是使用两层for循环，第一个循环遍历数组元素，第二个循环用于更新数组，时间复杂度为O(n^2)；

第二种是使用双指针，通过一个快指针一个慢指针，在一层for循环中完成两层for循环的工作；

思路1实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size();
        for (int i = 0; i < size; i++) {
            if (nums[i] == val) { // 发现需要移除的元素，就将数组中该元素以后的部分集体向前移动一位
                for (int j = i + 1; j < size; j++) {
                    nums[j - 1] = nums[j];
                }
                i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位（这里如果不处理i会导致下一次直接处理i+2忽略i+1）
                size--; // 此时数组的大小-1
            }
        }
        return size;
    }
};

解题思路2：

首先我们需要定义快慢指针的含义（其实这里的指针并不是严格意义上的指针，只能说是一个数组元素位置标记）：

  • 快指针：遍历原数组，寻找新数组的元素 ，新数组就是不含有目标元素的数组
  • 慢指针：更新新数组元素

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 时间复杂度：O(n)
// 空间复杂度：O(1)
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
            if (val != nums[fastIndex]) {
                nums[slowIndex++] = nums[fastIndex];//这里是本题的核心所在，简单来说就是使用slowIndex创建了一个新的数组，该数组只保存fastIndex数组中与val值不同的数值
            }
        }
        return slowIndex;
    }
};

3.有序数组的平方

题目要求：

解析：

这道题有一个很容易忽略的点，假如原数组只有正数则直接遍历并返回平方即可，但是原数组是可以有负数的；

本题同样有两种解法，一种是使用单层for循环返回原数组的平方，接着再对返回的数进行排序（自己写函数或者直接调用sort()函数都可以）；

第二种是使用双指针（注意这里的双指针是头尾指针，与前面使用的快慢指针有一定区别）；

思路1代码如下：

1
2
3
4
5
6
7
8
9
10
11
//时间复杂度是 O(n + nlogn)
class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        for (int i = 0; i < A.size(); i++) {
            A[i] *= A[i];
        }
        sort(A.begin(), A.end()); // 快速排序，默认升序排序
        return A;
    }
};

思路2：

尽管数组中有负数，但是原数组因为是有序的，所以平方后得到的较大值在原数组中要么就是靠左要么靠右；

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//时间复杂度为O(n)
class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int k = A.size() - 1;
        vector<int> result(A.size(), 0);
        for (int i = 0, j = A.size() - 1; i <= j;) { // 注意这里要i <= j，因为最后要处理两个元素
            if (A[i] * A[i] < A[j] * A[j])  {
                result[k--] = A[j] * A[j];
                j--;
            }
            else {
                result[k--] = A[i] * A[i];
                i++;
            }
        }
        return result;
    }
};

4.长度最小的子数组

解析：

这道题同样也是题干就很容易让人混淆，究竟是什么意思？

翻译过来就是给定一个target，我们需要在原数组中寻找元素使其和大于等于target，我们使用的这些元素将会构成一个新的数组，要求该数组的长度最小；

这道题同样有两种解法，一种是使用暴力双循环，外循环用于确定子序列起点i，内循环用于确定子序列的终点j；

第二种解法是使用滑动窗口，本质上也是双指针；

思路1代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//时间复杂度：O(n^2)
//空间复杂度：O(1)
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX; // 最终的结果
        int sum = 0; // 子序列的数值之和
        int subLength = 0; // 子序列的长度
        for (int i = 0; i < nums.size(); i++) { // 设置子序列起点为i
            sum = 0;
            for (int j = i; j < nums.size(); j++) { // 设置子序列终止位置为j
                sum += nums[j];
                if (sum >= s) { // 一旦发现子序列和超过了s，更新result
                    subLength = j - i + 1; // 取子序列的长度
                    result = result < subLength ? result : subLength;
                    break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break，注意break仅是退出当前for循环
                }
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};

思路2：

滑动窗口：不断调整子序列的起始位置和终止位置（其实和上面设置起始位置i和终止位置j相同，但是只用了一个for循环）

使用滑动窗口需要解决下面的几个问题

  • 窗口内是什么？——窗口内是满足其和 ≥s 的长度最小的连续子数组
  • 如何移动窗口的起始位置？——如果当前窗口的值大于s了，窗口就要向后移动了（也就是该缩小了）
  • 如何移动窗口的结束位置？——窗口的结束位置就是遍历数组的指针，也就是for循环里的索引值i

因此使用滑动窗口的关键在于 如何移动窗口的起始位置

代码如下：

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:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX;
        int sum = 0; // 滑动窗口数值之和
        int i = 0; // 滑动窗口起始位置
        int subLength = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件（即窗口内的值是否大于等于s）
            //只要窗口内的值大于等于s,则比较子序列的长度，取长度较小者作为最新的result
            //尽管此处使用了while循环，但是它只是作为一个条件偶尔执行，所以和for循环比起来可以不算复杂度
            while (sum >= s) {
                subLength = (j - i + 1); // 取子序列的长度
                result = result < subLength ? result : subLength;
                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（即子序列的起始位置）
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};

5.螺旋矩阵

解析

首先这道题其实就是考察我们对二维数组/矩阵的掌握程度，

  • 二维数组/矩阵是以数组作为数组元素的数组；
  • 二维数组第一个参数是行，第二个参数是列，先按照行排再按照列排，即数Aij位于矩阵的第i行第j列；

第二个考察点是在画矩阵的时候需要按照顺序，不要想到哪里画哪里

  • 由外向内构建二维矩阵

  • 填充上行从左到右

  • 填充右列从上到下

  • 填充下行从右到左

  • 填充左列从下到上

第三点是每一条边都要遵守某个相同的规则

  • 按照左闭右开构建每一条边

代码如下：

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
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
        int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
        int loop = n / 2; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只循环构造一圈，矩阵中间的值需要单独处理不作为圈构造 
        int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
        int count = 1; // 用来给矩阵中每一个空格赋值
        int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
        int i,j;
        while (loop --) {
            i = startx;
            j = starty; 

            // 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
            for (j = starty; j < n - offset; j++) {
                res[startx][j] = count++;
            }
            // 模拟填充右列从上到下(左闭右开)
            for (i = startx; i < n - offset; i++) {
                res[i][j] = count++;
            }
            // 模拟填充下行从右到左(左闭右开)
            for (; j > starty; j--) {
                res[i][j] = count++;
            }
            // 模拟填充左列从下到上(左闭右开)
            for (; i > startx; i--) {
                res[i][j] = count++;
            }

            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
            startx++;
            starty++;

            // offset 控制每一圈里每一条边遍历的长度
            offset += 1;
        }

        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
        if (n % 2) {
            res[mid][mid] = count;
        }
        return res;
    }
};

二、链表

0.链表概述

链表这一章仔细看看，能够提升对C++指针概念的理解

链表是通过指针串联在一起的节点的线性集合；

每个节点由两部分组成，数据域用于存放数据，指针域用于存放指向下一个节点的指针（最后一个节点的指针域为NULL）

单链表

注意区分头指针和头节点的概念

  • 头指针指向链表的第一个结点，若存在头结点则指向头结点，若不存在头节点则指向第一个结点；
  • 头节点的数据域一般不存数据（也可以存储表长等数据），头节点不一定是链表必须要的元素（引入头节点为了方便单链表的特殊操作,保证在表头插入或者删除第一个结点与其他结点操作相同.保持了单链表操作的统一性）；
  • 常用头指针冠以链表的名字，头指针是链表的必要元素；

双链表（每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点；双链表既可以向前查询也可以向后查询）

循环链表

1.移除链表元素

这道题本质上非常简单，就是考察单链表的删除操作；

需要注意的是，因为力扣直接给出了单链表的定义，但是这个单链表是不包含头节点的，需要我们在处理的时候增加一个头节点；

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点，数据域为0，由dummyHead指针指着（此时dummyHead指针指向虚拟头节点，头指针head指向第一个节点）
        dummyHead->next = head; 			  // 令虚拟头结点的指针域指向head，这样对后面结点的操作都统一
        ListNode* cur = dummyHead;			  // 令寻址指针初始指向虚拟头节点，注意不是头指针，头指针不能移动
        while (cur->next != NULL) {			  
            if(cur->next->val == val) {			// 当寻址指针指向的下一个节点的数据域是需要删除的val值时，进行删除操作
                ListNode* tmp = cur->next;		// 首先使用临时指针tmp指向待删除节点（如果不保存则下一步拆断联系后就找不到这个节点了，也就无法回收）
                cur->next = cur->next->next;	// 拆断原有联系
                delete tmp;					   // 删除无用节点，养成内存回收机制的好习惯
            } else {
                cur = cur->next;
            }
        }
        head = dummyHead->next;				//为了避免第一个节点被删除后head没有指向的问题，最后需要重新给head赋值
        delete dummyHead;					//最后返回结果之前我们还需要手动将增加的虚拟头节点删除
        return head;
    }
};

2.设计链表

可能刚开始看到这个题会很疑惑，不是说leecode不是已经帮我们定义了链表吗？怎么这里又让我们自己去设计？

其实这是leecode刷题这种模式的特点，它不像牛客所有的题都让你从0开始写，很多题目leecode是直接帮你调用了STL或者默认帮你实现了数据结构，只需要额外定义一个solution类来解决题目中的问题即可；

但是这道题的话就有点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
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
class MyLinkedList {
public:
    // 定义链表节点结构体
    struct LinkedNode {
        int val;									//数据域
        LinkedNode* next;							//指针域
        LinkedNode(int val):val(val), next(nullptr){}  //自定义节点构造函数（如果使用默认构造函数在初始化节点时不能直接给节点的数据域赋值）
    };

    // 初始化链表
    MyLinkedList() {
        _dummyHead = new LinkedNode(0); 			// 这里定义的头结点是一个虚拟头结点（数据域存0），而不是真正的链表头结点（习惯上称为第一个节点）
        _size = 0;								  //初始化链表大小为0（虚拟头节点不算size）
    }

    // 获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是第一个节点（而非虚拟节点）
    int get(int index) {
        if (index > (_size - 1) || index < 0) {
            return -1;
        }
        LinkedNode* cur = _dummyHead->next;			//令寻址指针从第一个节点（而非虚拟头节点）开始
        while(index--){ 						   // 如果--index 就会陷入死循环（index为0导致无限循环，因为非0即真while会一直执行下去）
            cur = cur->next;
        }
        return cur->val;
    }

    // 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点
    void addAtHead(int val) {
        LinkedNode* newNode = new LinkedNode(val);	//创建一个新的节点，使用newNode指针指向该新节点
        newNode->next = _dummyHead->next;		   //添加节点的操作，不用太在意顺序，只要不搞丢要添加或者删除的节点就行
        _dummyHead->next = newNode;				  //令虚拟头节点指向新的第一个节点
        _size++;
    }

    // 在链表最后面添加一个节点
    void addAtTail(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(cur->next != nullptr){
            cur = cur->next;
        }
        cur->next = newNode;					//最后一个节点直接在末尾添加就可以，不用考虑它后面再连接哪个节点
        _size++;
    }

    // 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
    // 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点
    // 如果index大于链表的长度，则返回空
    void addAtIndex(int index, int val) {
        if (index > _size) {
            return;
        }
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(index--) {
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
        _size++;
    }

    // 删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的
    void deleteAtIndex(int index) {
        if (index >= _size || index < 0) {
            return;
        }
        LinkedNode* cur = _dummyHead;
        while(index--) {
            cur = cur ->next;
        }
        LinkedNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        _size--;
    }

    // 打印链表
    void printLinkedList() {
        LinkedNode* cur = _dummyHead;
        while (cur->next != nullptr) {
            cout << cur->next->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }
private:
    //私有变量
    int _size;							//size表示链表的大小
    LinkedNode* _dummyHead;				//用头指针冠以链表的名字

};

3.反转链表

解析

反转链表这种题，实际上就是改变了next指针的指向，同时将第一个节点和最后一个节点互换；

解题使用双指针，第一个cur指针用于从前到后遍历链表的每个节点，第二个pre指针用于创建新的链表（本质上并没有使用额外空间，仅仅只是改变了next指针的指向而已）

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp; 		// 保存cur的下一个节点
        ListNode* cur = head;	//cur指针从head指向的结点开始，这里没有虚拟头节点故head指向第一个节点
        ListNode* pre = NULL;	//pre指针开始指向NULL，用于构建新的链表
        while(cur) {
            temp = cur->next;  // 保存一下 cur的下一个节点，因为接下来要改变cur->next
            cur->next = pre;   // 翻转操作，第一轮时pre指向NULL，cur指向第一个节点，cur->next=pre意味着让第一个节点指向NULL
            // 更新pre 和 cur指针，pre移动到第一个节点，cur移动到下一个节点
            pre = cur;
            cur = temp;
        }
        return pre;			//最终当cur==NULL的时候，pre刚好移动到最后一个节点，也就是反转过后的第一个节点，此时返回pre也就返回了反转过后的链表（此处涉及C++特性，和数组类似）
    }
};

4.交换链表节点

leecode的题总是能够让你读的半懵半懵的，实际上就是交换相邻的两个节点（交换过后的节点不再交换）——所以如果节点个数是奇数怎么办？？？假如是单数的话默认最后一个节点没得交换；

注意这个是单向链表，只能操作其next指针，所以需要注意交换的步骤

具体交换过程主要分为三个步骤（这里需要引入虚拟头节点，我们假设涉及交换的节点分别为cur，1，2，3，其中要交换的节点是1，2）

  • cur->next=2
  • 2->next=1
  • 1->next=3

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//时间复杂度O(n)
//空间复杂度O(1)
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头节点，方便统一处理第一个节点
        dummyHead->next = head; 			  // 将虚拟头结点指向head
        ListNode* cur = dummyHead;			  //初始时，遍历指针cur处于虚拟头节点位置
        while(cur->next != nullptr && cur->next->next != nullptr) {
            ListNode* tmp = cur->next; 		  // 记录临时节点，也就是1，因为cur指向2后就只能靠tmp找到1了
            ListNode* tmp1 = cur->next->next->next; // 记录临时节点，也就是3，因为2指向1后就只能靠tmp1找到3了

            cur->next = cur->next->next;    // 步骤一，cur->next=2
            cur->next->next = tmp;          // 步骤二，2->next=1
            cur->next->next->next = tmp1;   // 步骤三，1->next=3

            cur = cur->next->next; // cur指针在交换过后的基础上移动两位，准备下一轮交换（第一轮后cur移动到2），当是单数的时候因为不符合cur->next->next != nullptr条件所以直接结束
        }
        return dummyHead->next;	//返回第一个节点，注意虚拟头节点是手动增加的所以不要返回
    }
};

5.删除链表倒数第n个节点

解析：

这个题感觉很简单啊，直接找到并删除倒数第n个节点即可；

所以这道题是中等难度的原因就在于，找到倒数第n个节点在链表中是一件不容易的事；

这道题使用双指针可以快速解决——如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾NULL，删掉slow所指向的节点就可以了

细节：

  • 定义虚拟头节点且fast和slow初值均指向虚拟头节点；
  • slow指针在fast指针指向NULL的时候，slow指针是指向要删除的节点的前一个节点而非要删除的节点（否则没办法进行删除操作）；
  • 删除的节点是slow指针指向的节点的下一个节点；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(0);  //定义虚拟头节点
        dummyHead->next = head;                 //将虚拟头节点加入链表中
        ListNode* slow = dummyHead;			   //初始slow和fast均指向虚拟头节点
        ListNode* fast = dummyHead;
        while(n-- && fast != NULL) {		   //先移动fast指针，fast != NULL是为了防止用户输入大于链表长度的n导致程序错误
            fast = fast->next;
        }
        fast = fast->next; 					  // fast再提前走一步，因为需要让slow指向删除节点的上一个节点
        while (fast != NULL) {				  //fast和slow同时移动，直到fast指向NULL（这道题细节很多，注意画图理解）
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;		  //直接暴力改指向，回收甚至都不使用，这样做可能导致算法内存比较大；
        return dummyHead->next;
    }
};

6.环形链表1

这道题不是直接根据输入的skip就写出来了吗…还是说是我读题理解有问题？

这道题的举例是有问题的，我们定义的Solution类中的方法仅仅只有两个参数，即传入链表A和链表B，而相交节点的值明显是一个误导信息，因为链表中节点相同实质上是指向节点的指针的地址相同而不是节点存储的值相同，另外，skip这个条件属于是作弊条件，我要是都知道相交节点在距离头节点多远的位置，为什么我不直接跳过去呢？

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
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* curA = headA;	//初始curA指针指向A链表头节点
        ListNode* curB = headB; //初始curB指针指向B链表头节点
        int lenA = 0, lenB = 0;
        while (curA != NULL) { // 求链表A的长度
            lenA++;
            curA = curA->next;
        }
        while (curB != NULL) { // 求链表B的长度
            lenB++;
            curB = curB->next;
        }
        curA = headA;
        curB = headB;		//求完长度之后重新调整curA和curB的指向
        // 让curA指向长链表的头节点，len(长链表)为该链表长度
        if (lenB > lenA) {
            swap (lenA, lenB);
            swap (curA, curB);
        }
        // 求长度差
        int gap = lenA - lenB;
        // 让curA和curB在同一起点上（末尾位置对齐）
        while (gap--) {
            curA = curA->next;
        }
        // 遍历curA 和 curB，遇到相同则直接返回
        while (curA != NULL) {
            if (curA == curB) {
                return curA;//如果指针相同则返回此时的指针即可
            }
            curA = curA->next;
            curB = curB->next;
        }
        return NULL;//如果永远都没有相同的指针则返回NULL
    }
};

7.环形链表2

这道题乍一看挺吓人的，找到环形的入口，这让人如何是好？实际上这道题主要有两个考点：

  • 判断链表是否有环；
  • 若存在环，如何找到这个环的入口；

判断链表是否有环可以使用双指针，fast每次移动2步，slow每次移动1步，如果有环则fast和slow一定会相交并且是在环内相交

如果链表有环，

参考题解：刘翔以老八2倍的速度和老八从头开始跑，直到和老八相遇，很疑惑：哦原来有环啊？

老八也很疑惑，那么什么是哪个点出现的环啊？

刘翔说：忘记了，我只知道我跑的路程是你的两倍，而且我已经比你这个乌龟多跑一圈了，不然怎么可能抓到你。

老八说：杀千刀的，那假设那个点前距离是a好了，我现在跑了a+b了，你比我多一圈那就是2(a+b) 那 2(a+b)==a+c(c是圈的长度)+b 得出a+b=c。

刘翔：哦那简单啊，那你现在距离那个点已经b了，再跑a个点不就到那里了嘛。

老八生气的说： 我他niang的怎么知道a是多少？求的就是a啊大哥！

刘翔邪魅一笑：那简单啊，我现在叫我朋友博尔特从起点和你一个速度跑，你们都差a 就到了，相遇了就是答案了哇。

老八： 呵呵。算你狠。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode root=head;//博尔特
        ListNode left=head;//老八
        ListNode right=head;//刘翔
        while(right!=null && right.next!=null){
           right=right.next.next;//刘翔两倍速
           left=left.next;		//老八一倍速
           if(left==right){
               while(root!=right){//当刘翔和老八相遇，博尔特开始以一倍速跑步
                   root=root.next;
                   right=right.next;
               }
               return root;//要是root==right说明环入口就在第一个节点
           }
       }
       return null;
    }
}

三、哈希表

0.哈希表概述

hash table即哈希表、散列表，一般用来快速判断一个元素是否出现在集合里；

哈希表是根据关键码的值直接进行访问的数据结构；

数组就是一张哈希表，哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素；

哈希表上的映射函数也称为哈希函数，下面展示了一个将学生姓名映射到哈希表上的hash function；

使用哈希函数涉及模运算，这可能导致小王和小张在哈希表的同一个索引下标的位置进而发生冲突，这就叫做哈希碰撞；

一般哈希碰撞有两种解决方法，拉链法和线性探测法；

拉链法是指将发生冲突的元素都存储在链表中；

拉链法就是要选择适当的哈希表的大小，这样既不会因为哈希表空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间；

使用线性探测法，一定要保证哈希表大小tableSize大于数据规模dataSize，我们需要依靠哈希表中的空位来解决碰撞问题；

例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ，要不然哈希表上就没有空置的位置来存放冲突的数据了

上面我们介绍了哈希表的基本概念（这个在数据结构的笔记里没有专门的介绍，感兴趣可以再查资料学习），当我们需要使用哈希算法解决问题通常涉及如下三种数据结构：

  • 数组
  • 集合
  • 映射

STL为集合set提供了以下三种数据结构

红黑树是一种平衡二叉搜索树，所有key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加

STL为映射map提供了以下三种数据结构

虽然std::set、std::multiset 的底层实现是红黑树，不是哈希表，但是std::set、std::multiset 依然使用哈希函数来做映射，只不过底层的符号表使用了红黑树来存储数据，所以使用这些数据结构来解决映射问题的方法，我们依然称之为哈希法。 map也是一样的道理。

当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法；

但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找；

如果在做面试题目的时候遇到需要判断一个元素是否出现过的场景也应该第一时间想到哈希法；

红黑树是一种自平衡二叉查找树，是一种接近平衡的二叉搜索树，它能够保证任意一个节点左右子树的高度差不会超过较低子树的高度；

1.有效字母异位词

解析：

首先要知道什么是字母异位词，实际上就是两个单词包含相同的字母但是字母的次序不同如”anagram” 和 “nagaram”；

暴力解法本质上就是两层for循环并记录出现的字符是否重复，时间复杂度为O(n^2^)；

第二种解法使用数组，数组是一个哈希表，因为这题的本质就是判断元素是否出现在集合中（可以使用两个集合互相比较，也可以使用一个集合加减判断），所以我们考虑哈希表；

因为题目说只需要考虑小写字母，故数组的大小设置为26，字母a映射在数组下标0，字母z映射在数组下标25，数组record用于记录字符串s和t中字符出现的次数，s中出现的字符对应在数组中+1，t中出现的字符对应在数组中-1，最后检查record数组中如果存在元素不为0则reurn false，该方法时间复杂度为O(n)，空间复杂度为O(1)；

代码如下

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 isAnagram(string s, string t) {
        int record[26] = {0};				//初始化record数组
        for (int i = 0; i < s.size(); i++) {
            // 此处非常巧妙的利用了a作为26个小写字母起始字符的特点，因此s[i]或者t[i]如果是'a'则'a'-'a'会得到0也就刚好映射在record数组的第一个位置
            record[s[i] - 'a']++;
        }
        for (int i = 0; i < t.size(); i++) {
            record[t[i] - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (record[i] != 0) {
        // 假如record数组存在元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符
                return false;
            }
        }
        // record数组所有元素都为零0，说明字符串s和t是字母异位词
        return true;
    }
};

2.两个数组的交集

解析：

这道题本质上也就是需要判断某个元素是否出现在集合中，因此我们选择考虑哈希表；

当然这道题可以使用暴力for循环，其时间复杂度为O(n^2^)；

前面使用了数组作为哈希表，但需要注意这样的前提是题目已经限制了数组的大小，而且如果哈希值较少、分散且跨度很大使用数组会造成浪费；

我们这里考虑使用set结构体作为哈希表，关于set，C++提供了三种可用的数据结构：

  • std::set
  • std::multiset
  • std::unordered_set

std::set和std::multiset底层实现都是红黑树，std::unordered_set的底层实现是哈希表，更多关于set容器的介绍可以参考STL初级 - Tintoki_blog (gintoki-jpg.github.io)

set 容器具有以下几个特性：

  • 不再以键值对的方式存储数据，因为 set 容器专门用于存储键和值相等的键值对，因此该容器中真正存储的是各个键值对的值（value）；
  • set 容器在存储数据时，会根据各元素值的大小对存储的元素进行排序（默认做升序排序）；
  • 存储到 set 容器中的元素，虽然其类型没有明确用 const 修饰，但正常情况下它们的值是无法被修改的；
  • set 容器存储的元素必须互不相等；

我们很容易看出set容器恰好符合题干的要求，这里综合考虑最终选择unordered_set

set容器代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set; // 存放最终结果，用set容器是为了给结果集去重
        unordered_set<int> nums_set(nums1.begin(), nums1.end());
        for (int num : nums2) {
            // 假如发现nums2的元素在nums_set中没有出现过，则insert该num
            if (nums_set.find(num) != nums_set.end()) {
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};

数组代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set; // 存放最终结果，之所以用set是为了给结果集去重，注意这里使用的是两个数据结构，所以一个使用set一个使用数组
        int hash[1005] = {0}; // 默认数值为0
        for (int num : nums1) { // nums1中出现的字母在hash数组中做记录，这里直接用字母对应的ASCLL作为数组索引
            hash[num] = 1;
        }
        for (int num : nums2) { // 假如num2中出现相同的字母则将该字母insert进最终结果集中
            if (hash[num] == 1) {
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};

3.快乐数

题目链接202. 快乐数 - 力扣（LeetCode）

快乐数被定义为

  • 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和；

  • 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1；

  • 如果这个过程 结果为 1，那么这个数就是快乐数；

解析：

“需要快速判断一个元素是否出现在集合中，考虑哈希法”，本题采用哈希法快速判断sum平方和是否重复出现，如果sum重复出现代表一定是无限循环，则return false，否则需要一直计算sum直到sum为1；

因为需要判断sum是否重复出现，也就是集合中重复元素的判断，因此这里使用unordered_set而非数组；

代码如下：

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:
    // 1.定义取数值各个位上的单数平方和函数，比如n是101，则n依次赋值为101,10,1,0因此会进行三次循环，对应n是一个三位数
    int getSum(int n) {
        int sum = 0;
        while (n) {
            /*除法运算用作判断数值的位数，取模运算用作判断数值的每一位
            *n依次被赋值为101，10，1，对应取模运算得到的值依次是1,0,1符合数值的每一位
            */
            sum += (n % 10) * (n % 10);
            /*“/=”属于复合赋值运算符中的一种，把左边的变量除以右边变量的值赋予左边的变量，如a/=b等价于a=a/b
            *C++中除法的运算规则是强制类型转换，如果两个操作数中有一个为浮点型，则结果为浮点，如果两个均为整型，则为整除（int a = 5、int b = 2，则a/b的值为2（整除），而用(double)a/b			  *的值则为2.5）
            */
            n /= 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        unordered_set<int> set;
        //只要sum不是循环，就一直求解下去
        while(1) {
            int sum = getSum(n);
            if (sum == 1) {
                return true;
            }
            // 如果这个sum曾经出现过，说明已经陷入了无限循环了，立刻return false，此处调用了set的find方法，如果sum已经在set中出现过则返回的两个迭代器指向的位置不会一致
            if (set.find(sum) != set.end()) {
                return false;
            } else {//如果sum没出现过则直接insert在最后即可
                set.insert(sum);
            }
            n = sum;
        }
    }
};

4.两数之和

解析：

这道题很眼熟…因该是之前在哪里做过？或者其实数组那一节的第四题有点类似；

什么时候使用哈希法 —— 需要查询一个元素是否出现过，或者一个元素是否在集合里的时候

本题题意为使用一个集合存放我们遍历过的元素，然后在遍历数组的时候去访问这个集合（如果觉得绕的话可以看了代码解析再回头理解这句话）

本题采用map的key value结构分别存放元素以及该元素对应的下标，之所以不选择数组和set是因为

  • 数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费；
  • set是一个集合，里面放的元素只能是一个key，而本题不仅要判断y是否存在而且还要记录y的下标位置，所以set 也不能用；

C++提供了三种map的数据类型

基本原理图如下

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map <int,int> map;				//用于存放遍历过的元素的map
        for(int i = 0; i < nums.size(); i++) {			// 遍历当前元素，并在map中寻找是否有匹配的key，至于为什么不是我们以为的value，是因为map.find查找的是key的位置
            auto iter = map.find(target - nums[i]); 
            if(iter != map.end()) {					   //假如在map中找到匹配的value则返回其key和value
                return {iter->second, i};
            }
            map.insert(pair<int, int>(nums[i], i)); 	// 如果没找到匹配对，就把访问过的元素和下标加入到map中
        }
        return {};
    }
};

5.四数相加

这道题目是四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况；（这道题和只给出一个数组并找出四个元素相加等于0相比的难度较小）

解析：（看不懂很正常，结合代码理解）

  1. 首先定义 一个unordered_map，key放a和b两数之和，value 放a和b两数之和出现的次数；
  2. 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中；
  3. 定义int变量count，用来统计 a+b+c+d = 0 出现的次数；
  4. 在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来；
  5. 最后返回统计值 count 就可以了；

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 fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int, int> umap; //key:a+b的数值，value:a+b数值出现的次数
        //之所以不使用三个数相加再和一个数匹配，是因为O(n^2)和O(n^3)是不一样的复杂度
        // 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中
        for (int a : A) {
            for (int b : B) {
                umap[a + b]++; 
            }
        }
        int count = 0; // 统计a+b+c+d = 0 出现的次数
        // 在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就把map中key对应的value也就是出现次数统计出来。
        for (int c : C) {
            for (int d : D) {
                if (umap.find(0 - (c + d)) != umap.end()) {
                    count += umap[0 - (c + d)];
                }
            }
        }
        return count;
    }
};

6.三数之和

解析

之所以把这道题放在这里不是因为它可以使用哈希法解决，而是它恰好不能使用哈希法（因为三元组不能重复所以细节处理很耗费时间）；

这道题使用双指针解法如下，首先我们需要将数组排序（双指针法一定需要排序），借助一层for循环，定义了left和right两个指针，left初始化为i+1，right初始化为数组末尾，将三个数转换为nums[i]、nums[left]以及nums[right]；

移动left指针和right指针的规则如下：

  • 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些；
  • 如果 nums[i] + nums[left] + nums[right] < 0 说明 此时三数之和小了，left 就向右移动，才能让三数之和大一些；
  • 如果找到结果，则将三元组存储后同时收缩left和right指针，转移到下一层for循环；
  • 如果没有找到结果，直到left与right相遇，转移到下一层for循环；

基本思想并不难，需要注意的是题干要求不能有重复的三元组，那么还需要考虑去重，也就是nums[i]、nums[left]以及nums[right] —— 注意是三元组不能相同，但是三元组中的元素可以重复；

很多人可能一来的想法是直接得到所有符合的三元组之后，依次比较每一个三元组的元素进行三元组去重，这种方法就属于是最低效的，我们应该考虑在构造三元组的时候就进行去重；

首先是对nums[i]的去重，因为nums[i]是依次移动的，从数组下标0位置移动到末尾（注意我们的数组是经过排序的），因此只需要比较nums[i]和它前面一个数nums[i-1]是否相同，如果相同则直接跳过（注意千万不能和nums[i]后面的数nums[i+1]比较，比如三元组[-1,-1,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
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        // 找出a + b + c = 0
        // a = nums[i], b = nums[left], c = nums[right]
        for (int i = 0; i < nums.size(); i++) {
            // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
            if (nums[i] > 0) {
                return result;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = nums.size() - 1;
            while (right > left) {
                if (nums[i] + nums[left] + nums[right] > 0) right--;
                else if (nums[i] + nums[left] + nums[right] < 0) left++;
                else {
                    result.push_back(vector<int>{nums[i], nums[left], nums[right]});
                    // 去重逻辑应该放在找到一个三元组之后，对b和c去重，因为数组是经过排序的所以直接移动left和right指针即可，即寻找第一个符合条件的元素
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;//之所以nums[left]和nums[i]的去重逻辑不同，需要仔细体会，举例来说，对于[-1,-1,-1,2]，其中nums[i]是第一个-1，nums[left]是第二个-1，第三个-1会因为left去重直接被pass
                    // 找到答案时，双指针同时收缩
                    right--;
                    left++;
                }
            }

        }
        return result;
    }
};

7.四数之和

解析

这道题同样不能使用哈希表，因为和三数求和一样需要去重，这道题的解法也是使用双指针，只是多套用了一层for循环（为什么不能使用三指针呢？因为三指针不便于管理，还不如for循环）；

需要注意以下细节：

  • 判断第一个数大于target值直接return的逻辑需要严格限制，因为这里的target并不是指定的0，将nums[k] > target变为nums[i] > target && (nums[i] >=0 || target >= 0)；
  • 三数求和的双指针解法是一层for循环num[i]为确定值，然后循环内有left和right下标作为双指针，找到nums[i] + nums[left] + nums[right] == 0；四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值，依然是循环内有left和right下标作为双指针，找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况，三数之和的时间复杂度是O(n^2^)，四数之和的时间复杂度是O(n^3^)；（同理我们可以类推五数求和、六数求和…实际上三数求和就是将暴力O(n^3^)降为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
41
42
43
44
45
46
47
48
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for (int k = 0; k < nums.size(); k++) {
            // 剪枝处理
            if (nums[k] > target && nums[k] >= 0) {
            	break; // 这里使用break，统一通过最后的return返回，其实这里使用return result也没问题，但是尽量和2级剪枝处理保持一致
            }
            // 对nums[k]去重
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            for (int i = k + 1; i < nums.size(); i++) {
                // 2级剪枝处理
                if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
                    break;
                }
                // 对nums[i]去重
                if (i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }
                int left = i + 1;
                int right = nums.size() - 1;
                while (right > left) {
                    // nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
                    if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) {
                        right--;
                    // nums[k] + nums[i] + nums[left] + nums[right] < target 会溢出
                    } else if ((long) nums[k] + nums[i] + nums[left] + nums[right]  < target) {
                        left++;
                    } else {
                        result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
                        // 对nums[left]和nums[right]去重
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;
                        // 找到答案时，双指针同时收缩
                        right--;
                        left++;
                    }
                }

            }
        }
        return result;
    }
};

8.赎金信

解析

杂志字符串中的每个字符只能在赎金信字符串中使用一次，且我们假设两个字符串只有小写字符

这道题使用暴力解法（双层for循环）也是非常容易想到的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 时间复杂度: O(n^2)
// 空间复杂度：O(1)
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        for (int i = 0; i < magazine.length(); i++) {
            for (int j = 0; j < ransomNote.length(); j++) {
                // 在ransomNote中找到和magazine相同的字符
                if (magazine[i] == ransomNote[j]) {
                    ransomNote.erase(ransomNote.begin() + j); // ransomNote删除这个字符
                    break;
                }
            }
        }
        // 如果ransomNote为空，则说明magazine的字符可以组成ransomNote
        if (ransomNote.length() == 0) {
            return true;
        }
        return false;
    }
};

当然也可以使用哈希表，采取空间换取时间的策略，用长度为26的数组记录magazine中字母出现的次数，接着使用ransomNote验证

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
// 时间复杂度: O(n)
// 空间复杂度：O(1)
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int record[26] = {0};
        //假如赎金信中的字符串长度都大于杂志字符串了，那么必然是不可能组成的（其实这个条件也可以加在上面暴力for循环之前）
        if (ransomNote.size() > magazine.size()) {
            return false;
        }
        //其实这个题目给我们最大的启发就是如何记录并匹配数组中的字符，record数组中0表示小写字母a，数组内容就是该小写字母出现的次数
        for (int i = 0; i < magazine.length(); i++) {
            // 通过recode数据记录 magazine里各个字符出现次数
            record[magazine[i]-'a'] ++;
        }
        for (int j = 0; j < ransomNote.length(); j++) {
            // 遍历ransomNote，在record里对应的字符个数做--操作
            record[ransomNote[j]-'a']--;
            // 如果小于零说明ransomNote里出现的字符，magazine没有
            if(record[ransomNote[j]-'a'] < 0) {
                return false;
            }
        }
        return true;
    }
};

9.总结

首先我要说一下，哈希表在整个数据结构课程中其实是没有单独作为一个基本的数据结构介绍的，因为它实际上是作为一种“查找思想”，使得我们不需要挨个比较值是否相等来查找某个数值；

在我们解题的过程中只需要记住可以使用数组、set以及map这三种基本数据结构都可以实现哈希法即可，不要手动去写一个哈希表的数据结构（这当然是可行的，这就需要我们选择散列函数、处理冲突…本末倒置了属于是）；

我们知道有如下常见的三种哈希结构：

  • 数组
  • set
  • map

数组是最简单的哈希表，但是数组的大小是受限的，当题干明显给出暗示如小写字母(仅有26个)则直接选择数组，注意可以选择数组和map的时候一定要选择数组，因为map的消耗在实际数据量很大的时候是远远超过数组的；

当题干没有限制数组大小的时候就不能使用数组作为哈希表，此时就可以选择set(set还可以避免数据重复)；

选择数组和set作为哈希表有如下限制：

  • 数组的大小是受限制的，而且如果元素很少，但哈希值太大会造成内存空间的浪费；
  • set只能存储单个值，当面临需要存储某个元素的两个值的时候set是不能满足的；

四、字符串

在字符串相关的题目中，因为C/C++对字符串的特性，所以有很多针对字符串的库函数，注意选择的原则就是“库函数仅仅是解题过程中的一小部分，并且你已经很清楚这个库函数的内部实现原理的话，可以考虑使用库函数”；（如果不太明白这个库函数就最好不要使用，否则分析时间复杂度的时候真的会一脸懵）

1.反转字符串1

解析

这个题实际上大一的时候做过一次，用的是最简单的for循环以及一个额外的result数组，however，此处要求必须原地修改数组，因此我们选择和反转链表类似的双指针方法；

1
2
3
4
5
6
7
8
class Solution {
public:
    void reverseString(vector<char>& s) {
        for (int i = 0, j = s.size() - 1; i < s.size()/2; i++, j--) {
            swap(s[i],s[j]);
        }
    }
};

2.反转字符串2

解析

与简单的字符串反转不同，这里是花式反转；

这道题乍一看需要分三种情况，实际只需要分两种情况：

  1. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
  2. 剩余字符少于 k 个，则将剩余字符全部反转

还有一点需要注意的是，不要一来就搞个计数器计数2k以及前k个字符，这道题关键点在于“以固定规律分段处理字符串”，这也就意味着我们可以在for循环上考虑优化，每次for循环都在2k的起点即可；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string reverseStr(string s, int k) {
        // 1. 每隔 2k 个字符的前 k 个字符进行反转
        for (int i = 0; i < s.size(); i += (2 * k)) {
            // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
            if (i + k <= s.size()) {
                reverse(s.begin() + i, s.begin() + i + k );
            } else {
            // 3. 剩余字符少于 k 个，则将剩余字符全部反转。
                reverse(s.begin() + i, s.end());
            }
        }
        return s;
    }
};

3.替换空格

解析

这道题最容易想到的思路就是for循环，比较每个字符，如果是空格则替换，乍一看时间复杂度为O(n)可以接受；

However，注意题干是将空格字符替换为”%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
class Solution {
public:
    string replaceSpace(string s) {
        int count = 0; // 统计空格的个数
        int sOldSize = s.size();
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == ' ') {
                count++;
            }
        }
        // 扩充字符串s的大小，也就是每个空格替换成"%20"之后的大小
        s.resize(s.size() + count * 2);
        int sNewSize = s.size();
        // 从后先前将空格替换为"%20"
        for (int i = sNewSize - 1, j = sOldSize - 1; j < i; i--, j--) {
            if (s[j] != ' ') {
                s[i] = s[j];
            } else {//直接替换连续三个元素，并移动指针i向前两个元素位置
                s[i] = '0';
                s[i - 1] = '2';
                s[i - 2] = '%';
                i -= 2;
            }
        }
        return s;
    }
};

4.反转字符串中的单词

解析

这题当然可以直接以空格或字符串尾部分隔每个单词（注意这里默认符号属于前一个单词，但是如果是”hello,world”这种字符串就会被认为是同一个单词…），然后使用新的string字符串或char数组将分隔的单词倒序相加；

假如我们增加限制，要求空间复杂度为O(1)，也就是只能在原有字符串进行反转；

解题主要步骤如下：

  1. 移除多余空格；
  2. 将整个字符串反转；
  3. 分别将每个单词反转；

在移除空格的过程中，如果我们使用简单的earse会导致时间复杂度实际是O(n^2^)（因为数组元素是不能被删除的，earse的底层原理实际仍然是覆盖元素），所以采用双指针的方法来移除空格最后resize整个字符串的大小就可以达到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
//移除空格函数，关于这个函数如何构造的可以参考数组章节的移除元素
void removeExtraSpaces(string& s) {
    int slowIndex = 0, fastIndex = 0; // 定义快指针，慢指针
    // 去掉字符串前面的空格
    while (s.size() > 0 && fastIndex < s.size() && s[fastIndex] == ' ') {
        fastIndex++;
    }
    for (; fastIndex < s.size(); fastIndex++) {
        // 去掉字符串中间部分的冗余空格
        if (fastIndex - 1 > 0 && s[fastIndex - 1] == s[fastIndex] && s[fastIndex] == ' ') {
            continue;
        } 
        else {
            s[slowIndex++] = s[fastIndex];
        }
    }
    if (slowIndex - 1 > 0 && s[slowIndex - 1] == ' ') { // 去掉字符串末尾的空格
        s.resize(slowIndex - 1);
    } 
    else {
        s.resize(slowIndex); // 重新设置字符串大小
    }
}
1
2
3
4
5
6
7
//手动实现reverse函数
// 反转字符串s中左闭右闭的区间[start, end]
void reverse(string& s, int start, int end) {
    for (int i = start, j = end; i < j; i++, j--) {
        swap(s[i], s[j]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
//反转函数
string reverseWords(string s) {
        removeExtraSpaces(s); //去除多余空格，保证单词之间之只有一个空格，且字符串首尾没空格。
        reverse(s, 0, s.size() - 1);
        int start = 0; //removeExtraSpaces后保证第一个单词的开始下标一定是0。
        for (int i = 0; i <= s.size(); ++i) {
            if (i == s.size() || s[i] == ' ') { //到达空格或者串尾，说明一个单词结束。进行翻转。
                reverse(s, start, i - 1); //翻转，注意是左闭右闭 []的翻转。
                start = i + 1; //更新下一个单词的开始下标start
            }
        }
        return s;
    }

5.左旋转字符串

解析

这道题究竟是否涉及数组的扩容？肯定最简单的方式就是截取前n个字符然后移动后面的所有字符，再在末尾加上n个字符，但是这种方法需要的时间成本太高了；

这里我们加限制，不能使用额外的空间，只能在本串上操作；

前面反转字符串中的单词说过，使用整体反转+局部反转可以实现反转单词顺序的目的（这里我们将字符串看作整体，将需要旋转的n个字符看作局部），步骤为：

  1. 反转区间为前n的子串
  2. 反转区间为n到末尾的子串
  3. 反转整个字符串

举例来说，abcdefg，先反转ab得到bacdefg，再反转cdefg得到bagfedc，最后反转整个字符串得到cdefgab

1
2
3
4
5
6
7
8
9
class Solution {
public:
    string reverseLeftWords(string s, int n) {
        reverse(s.begin(), s.begin() + n);
        reverse(s.begin() + n, s.end());
        reverse(s.begin(), s.end());
        return s;
    }
};

6.实现strStr()

这道题是KMP的经典题目，所以需要我们掌握KMP算法；

KMP的经典思想就是:当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配；

strstr(str1,str2) 函数用于判断字符串str2是否是str1的子串

  • 如果是，则该函数返回 str1字符串从 str2第一次出现的位置开始到 str1结尾的字符串；
  • 否则，返回NULL；

具体实现参考代码随想录 (programmercarl.com)

7.重复子串

解析

暴力解法就是一个for循环获取子串的终止位置（之所以只使用一个for循环而不是两个for循环是因为只需要判断以第一个字母开始的子串即可（第一个不匹配那么就不可能重复组成主串），同时根本不需要for循环结束，因为子串结束的位置大于主串中间位置则一定不能重复组成字符串），然后判断子串是否能重复构成字符串，这将嵌套一个for循环，一共是O(n^2^)的时间复杂度；

我们这里主要讲解移动匹配解法；

一个主串如果是由重复子串组成，则将两个主串拼接在一起中间一定还会出现一个主串，比如”abcabcabc”拼接在一起得到”abcabcabcabcabcabc”我们能在中间找到新出现的主串；

因此判断字符串s是否有重复子串组成，只要两个s拼接在一起，里面还出现一个s的话，就说明是由重复子串组成。当然，我们在判断 s + s 拼接的字符串里是否出现一个s的的时候，要刨除 s + s 的首字符和尾字符，这样避免在s+s中搜索出原来的s，我们要搜索的是中间拼接出来的s；

1
2
3
4
5
6
7
8
9
class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string t = s + s;
        t.erase(t.begin()); t.erase(t.end() - 1);        // 掐头去尾
        if (t.find(s) != std::string::npos) return true; // 当然使用库函数的时间复杂度为O(m+n)，相较于暴力解法的O(m*n)
        return false;
    }
};

这里我们衍生一下，前面说到的KMP也可以用于这道题，KMP主要用于在一个串中查找是否出现过另一个串，这里我们主要使用的是KMP算法概念中的前缀表，并不涉及KMP算法查找；

在由重复子串构成的字符串中，最长相等前后缀不包含的子串就是组成字符串的最小重复子串，比如下面的例子，ab就是最小重复单位

假设某字符串s(其长度也是s)是由n个最小重复子串x(其长度也是x)构成，也就是s=n * x；字符串s的最长相同前后缀的长度为(n-1) * x；

我们可以得出如下结论：前缀表的长度（实际就是字符串s的长度）减去最长相同前后缀的长度等于最小重复单位的长度，如果这个长度可以被整除代表该字符串由最小重复单位重复n次组成；

这里举个例子，字符串”asdfasdfasdf”长度为12，其最长相同前后缀为”asdfasdf”长度为8，因此最小重复单位”asdf”的长度为4，4可以被12整除说明字符串由最小重复单位组成；

这个解题方法很新颖，将字符串匹配的问题转换为数学问题，主要利用了KMP算法的前后缀概念；

8.总结

字符串类型的题目往往想法简单但是实现并不容易，其中双指针是常用策略，而KMP算法是字符串查找的最重要的算法；

前面使用过很多次的双指针算法，双指针并不隶属于某种特定的数据结构（当然也并不是严格意义上的指针，可以是数组下标），双指针主要有以下的作用：

  • 通过两个指针在一个for循环下完成两个for循环的工作；

双指针主要有快慢指针、前后指针；

五、栈和队列

0.概述

队列是先进先出，栈是先进后出；

栈和队列是STL中的数据结构，而STL有多个版本，我们这里介绍和使用的STL都是SGI STL中的数据结构；

栈

栈提供push和pop等接口，所有元素必须符合先进后出规则，所以栈不提供走访功能，也不提供迭代器(iterator)，不像是set或者map提供迭代器iterator来遍历所有元素；

栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能），这也意味着STL中栈常常并不被归类为容器，而是被归类为容器适配器；

STL中栈的底层实现可以是vector、list或deque，主要是链表和数组；

队列

队列中先进先出的数据结构，同样不允许有遍历行为，不提供迭代器，与栈相同，SGI STL中队列一样是以deque为缺省情况下的底部结构；

STL中的结构同样不被归类为容器，而被认为是容器适配器；

1.栈实现队列

解析

实际这道题的意思就是利用STL提供的栈来实现一个队列的数据结构和相关操作（模拟队列的行为），只用一个栈是无法实现的，需要一个输入栈，一个数输出栈：

  • 模拟队列的push只需要将数据放入输入栈即可；
  • 模拟队列的pop需要进行判断：
    • 输出栈为空则将输入栈中的元素全部导入，再将栈中的数据全部弹出；
    • 输出栈不为空则直接将栈中的元素弹出；
    • 如果输入栈和输出栈都是空则说明模拟的队列空；

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 MyQueue {
public:
    stack<int> stIn;
    stack<int> stOut;
    /** Initialize your data structure here. */
    MyQueue() {

    }
    /** Push element x to the back of queue. */
    void push(int x) {
        stIn.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        // 只有当stOut为空的时候，再从stIn里导入数据（导入stIn全部数据）
        if (stOut.empty()) {
            // 从stIn导入数据直到stIn为空
            while(!stIn.empty()) {
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        int result = stOut.top();
        stOut.pop();
        return result;
    }

    /** Get the front element. */
    int peek() {
        int res = this->pop(); // 直接使用已有的pop函数
        stOut.push(res); // 因为pop函数弹出了元素res，所以再添加回去
        return res;
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return stIn.empty() && stOut.empty();
    }
};

2.队列实现栈

解析

依旧需要使用两个队列来模拟栈，但注意这两个队列的关系并不是输入和输出，另一个队列用于备份；

两个队列que1和que2实现队列的功能，que2其实就是一个备份的作用：

  • 模拟实现pop操作，把除que1最后的元素都备份到que2，然后弹出最后的元素，再把其他元素从que2导回que1（如此往复，尽管很复杂）；
  • 模拟实现push操作，直接将元素存入que1即可；

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
class MyStack {
public:
    queue<int> que1;
    queue<int> que2; // 辅助队列，用来备份
    /** Initialize your data structure here. */
    MyStack() {

    }

    /** Push element x onto stack. */
    void push(int x) {
        que1.push(x);
    }

    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int size = que1.size();
        size--;
        while (size--) { // 将que1 导入que2，但要留下最后一个元素
            que2.push(que1.front());
            que1.pop();
        }

        int result = que1.front(); // 留下的最后一个元素就是要返回的值
        que1.pop();
        que1 = que2;            // 再将que2赋值给que1
        while (!que2.empty()) { // 清空que2
            que2.pop();
        }
        return result;
    }

    /** Get the top element. */
    int top() {
        return que1.back();
    }

    /** Returns whether the stack is empty. */
    bool empty() {
        return que1.empty();
    }
};

当然这个题使用一个队列也可以实现

一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时在去弹出元素就是栈的顺序；

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 MyStack {
public:
    queue<int> que;
    /** Initialize your data structure here. */
    MyStack() {

    }
    /** Push element x onto stack. */
    void push(int x) {
        que.push(x);
    }
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int size = que.size();
        size--;
        while (size--) { // 将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部
            que.push(que.front());
            que.pop();
        }
        int result = que.front(); // 此时弹出的元素顺序就是栈的顺序了
        que.pop();
        return result;
    }

    /** Get the top element. */
    int top() {
        return que.back();
    }

    /** Returns whether the stack is empty. */
    bool empty() {
        return que.empty();
    }
};

3.有效括号

解析

括号匹配是使用栈解决的经典问题，实际上编译器在词法分析的过程中处理括号、花括号这些符号逻辑的时候使用的也是栈数据结构；

由于栈的特殊性质，非常适合做对称匹配的题目，括号不匹配有如下三种情况：

  • 字符串左边括号多余 —— 对应指针遍历完字符串但栈不为空；
  • 括号不多于但括号类型不匹配 —— 对应指针遍历字符串的过程中指针和栈的字符不匹配；
  • 字符串右边括号多余 —— 对应指针遍历字符串的过程中栈已经空；

匹配成功的情况是指针遍历完字符串且栈为空；

使用栈解决括号匹配问题（小技巧：“左括号入栈改为右括号入栈，则只需要比较当前栈顶符号是否和输入符号一致即可”）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 2 != 0) return false; // 如果s的长度为奇数，一定不符合要求
        stack<char> st;  // 借助STL提供的stack栈结构
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') st.push(')');
            else if (s[i] == '{') st.push('}');
            else if (s[i] == '[') st.push(']');
            // 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false
            // 第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。所以return false
            else if (st.empty() || st.top() != s[i]) return false;
            else st.pop(); // st.top() 与 s[i]相等，栈弹出元素
        }
        // 第一种情况：此时我们已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false，否则就return true
        return st.empty();
    }
};

4.删除字符串相邻重复项

解析

实际解读这道题很容易想到这也需要使用栈来解决，上一题使用栈解决左右括号匹配，本题使用栈匹配相邻元素

使用栈解决相邻字符匹配（最终只需要将栈中的字符弹出并做一个反转即可）

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

5.逆波兰表达式求值

解析

逆波兰表达式相当于二叉树中的后序遍历，当然解题完全没必要从二叉树的角度进行；

逆波兰表达式的每一个子表达式要得出一个结果并用该结果做运算，本质上就是相邻字符串消除过程：指针遍历字符串的时候，遇到数字则入栈，遇到算符则取出栈顶两个数字并将计算结果压入栈中；

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:
    int evalRPN(vector<string>& tokens) {
        for (int i = 0; i < tokens.size(); i++) {
            if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
                long long num1 = st.top();
                st.pop();
                long long num2 = st.top();
                st.pop();
                if (tokens[i] == "+") st.push(num2 + num1);
                if (tokens[i] == "-") st.push(num2 - num1);
                if (tokens[i] == "*") st.push(num2 * num1);
                if (tokens[i] == "/") st.push(num2 / num1);
            } else {
                st.push(stoll(tokens[i]));
            }
        }
        int result = st.top();
        st.pop(); // 把栈里最后一个元素弹出（其实不弹出也没事，此时栈中只剩下这最后一个元素了）
        return result;
    }
};

6.滑动窗口最大值

解析

本题是使用单调队列的经典题目（单调队列是指队列中元素之间的关系具有单调性，单调队列的典型题目是滑动窗口，我们下面会详细介绍什么是单调队列，注意和优先级队列区别）

本题的核心是求解每个区间中的最大值，最简单的暴力法就是遍历的过程中每次都从窗口中找到最大的数值，时间复杂度为O(n*k)；

我们需要这样一个队列：该队列中的元素就是窗口中的元素，随着窗口的移动，队列元素也随之进出，每次移动后队列会返回其中的最大值；

单调队列的定义：

  • 不维护窗口中的所有元素，只维护可能成为窗口中最大值的元素即可；
  • 保证单调队列中的元素数值是从大到小的；
  • 单调队列配合窗口移动：
    • pop(value)：如果窗口滑动导致将要移除的元素value等于单调队列的出口元素，那么队列pop队首元素，否则不用任何操作；
    • push(value)：如果push的元素value大于入口元素的数值，那么就将队首元素pop，直到push元素的数值小于等于队列入口元素的数值，再进行push进队尾；

单调队列配合窗口进行滑动：

  • 第一个窗口(1,3,-1)：

    • 空队列，push 1；

    • 因为3>1，故pop 1再push 3；

    • 因为-1<3，故直接push -1；

  • 第二个窗口(3,-1,-3)：

    • 因为窗口滑动将要移除1，于是不需要做任何操作；
    • 因为-3<3，故直接push -3；

  • 第三个窗口(-3,5,3)；

    • 因为窗口滑动将要移除3，故pop3并滑动窗口，此时队首元素为-1；
    • 因为5>-1，故pop -1；
    • 因为5>-3，故pop -1并push 5；

…

使用deque作为底层容器实现单调队列

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 MyQueue { //单调队列（从大到小）
public:
    deque<int> que; // 使用deque来实现单调队列
    // 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
    // 同时pop之前判断队列当前是否为空。
    void pop(int value) {
        if (!que.empty() && value == que.front()) {
            que.pop_front();
        }
    }
    // 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
    // 这样就保持了队列里的数值是单调从大到小的了。
    void push(int value) {
        while (!que.empty() && value > que.back()) {
            que.pop_back();
        }
        que.push_back(value);

    }
    // 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
    int front() {
        return que.front();
    }
};

使用单调队列实现滑动窗口

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
class Solution {
private:
    class MyQueue { //单调队列（从大到小）
    public:
        deque<int> que; // 使用deque来实现单调队列
        // 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
        // 同时pop之前判断队列当前是否为空。
        void pop(int value) {
            if (!que.empty() && value == que.front()) {
                que.pop_front();
            }
        }
        // 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
        // 这样就保持了队列里的数值是单调从大到小的了。
        void push(int value) {
            while (!que.empty() && value > que.back()) {
                que.pop_back();
            }
            que.push_back(value);

        }
        // 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
        int front() {
            return que.front();
        }
    };
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue que;
        vector<int> result;
        for (int i = 0; i < k; i++) { // 先将前k的元素放进队列
            que.push(nums[i]);
        }
        result.push_back(que.front()); // result 记录前k的元素的最大值
        for (int i = k; i < nums.size(); i++) {
            que.pop(nums[i - k]); // 滑动窗口移除最前面元素
            que.push(nums[i]); // 滑动窗口前加入最后面的元素
            result.push_back(que.front()); // 记录对应的最大值
        }
        return result;
    }
};

注意：

单调队列并不是一成不变的，针对不同的应用其pop和push接口也不同，唯一不变的就是要保证队列中单调递减或递增的原则

7.前k个高频元素

解析

实际上本题由三个模块组成：

  1. 统计元素出现的频率 —— 使用map统计；
  2. 对频率进行排序 —— 使用优先级队列（本质上是一个堆，算法动画图解中直接认为堆就是在实现优先级队列时使用）；
  3. 找出前k个高频元素；

之所以使用堆排序而不是快速排序，是因为快排需要将map转换为vector结构；

本题使用小顶堆，要统计前k个最大元素，小顶堆只需要每次将最小的元素弹出，最后小顶堆中积累的就是前k个最大的元素；

寻找前k个最大频率元素的流程如下

C++代码如下

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
// 时间复杂度：O(nlogk)
// 空间复杂度：O(n)
class Solution {
public:
    class mycomparison {  //这个比较运算用于建堆时使用，注意左大于右建立小顶堆，右大于左建立大顶堆
    public:
        bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
            return lhs.second > rhs.second;
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // 统计元素出现频率
        unordered_map<int, int> map; // map<nums[i],对应出现的次数>
        for (int i = 0; i < nums.size(); i++) {
            map[nums[i]]++;
        }
        // 对频率排序
        // 定义一个小顶堆，大小为k，可以直接使用priority实现
        priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;
        // 用固定大小为k的小顶堆，扫面所有频率的数值
        for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
            pri_que.push(*it);
            if (pri_que.size() > k) { // 如果堆的大小大于了k，则队列弹出，保证堆的大小一直为k
                pri_que.pop();
            }
        }
        // 找出前k个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组
        vector<int> result(k);
        for (int i = k - 1; i >= 0; i--) {
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result;
    }
};

六、二叉树

0.二叉树概述

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

满二叉树的深度为k，有2^k^-1个节点；

完全二叉树：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。

若完全二叉树最底层为第h层，则该层包含1~ 2^(h-1)^个节点；

二叉搜索树：又被称为二叉排序树，二叉搜索树是一个有数值的树，二叉搜索树是一个有序树

  • 它的左、右子树也分别为二叉排序树；

  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

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

C++中的map、set等容器的底层实现都是平衡二叉搜索树，实际上红黑树就是一种平衡二叉搜索树，红黑树和平衡二叉搜索树不是独立的，具体信息可以参考(4条消息) 红黑树和AVL树_TABE_的博客-CSDN博客_avl和红黑树区别

二叉树的遍历方式

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

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

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

  • 深度优先遍历（这里的前中后实际上就是指中间节点的遍历顺序）
    • 前序遍历（递归法，迭代法）：中左右
    • 中序遍历（递归法，迭代法）：左中右
    • 后序遍历（递归法，迭代法）：左右中
  • 广度优先遍历
    • 层次遍历（迭代法）

1.二叉树的递归遍历

递归算法的三要素：

  1. 确定递归函数的参数和返回值：确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数，并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型；
  2. 确定终止条件：写完了递归算法，运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出；
  3. 确定单层递归的逻辑：确定每一层递归需要处理的信息，在这里也就会重复调用自己来实现递归的过程；
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:
    //前序遍历
    //1.确定递归函数的参数和返回值：参数就是传入的需要遍历的结点指针和vec结果数组，不需要返回任何值
    void traversal(TreeNode* cur, vector<int>& vec) {
        //2.确定终止条件：当前遍历的结果是空
        if (cur == NULL) return;
        //3.确定单层递归的逻辑：前序遍历的逻辑是中、左、右
        vec.push_back(cur->val);    // 中
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
    }
    
    //中序遍历
    void traversal(TreeNode* cur, vector<int>& vec) {
    if (cur == NULL) return;
    traversal(cur->left, vec);  // 左
    vec.push_back(cur->val);    // 中
    traversal(cur->right, vec); // 右
	}
    
    //后序遍历
    void traversal(TreeNode* cur, vector<int>& vec) {
    if (cur == NULL) return;
    traversal(cur->left, vec);  // 左
    traversal(cur->right, vec); // 右
    vec.push_back(cur->val);    // 中
	}
    
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

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 {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        //栈用来处理节点上的元素（即将节点的数值放入result数组中）
        stack<TreeNode*> st;
        vector<int> result;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
            //node指针用来帮助访问节点，访问节点和处理节点同时进行
            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;
    }
};
/*
关于上面的逻辑，可能直观上不是很好理解（我甚至都不知道怎么想出来这个逻辑的...），我们这里直接拿数据做一个演示；
首先将root 5放入stack中，同时令结点指针指向stack的顶端（也就是root 5）；接着直接stack pop弹出栈顶元素 5，将node指向的值5存入result；然后将6和4依次存入stack中；
第二个while循环，node指针指向stack的顶端也就是节点 4；接着直接stack pop后将node指向的值4存入result；然后将2和1依次存入stack中；
...
*/

中序遍历

前序遍历相对来说较简单，因为要访问的节点和要处理的节点的顺序一致，都是中间节点；

而中序遍历先访问二叉树的顶部节点，然后层层深入直到左子树的最下，再开始处理节点（处理节点意思就是将节点中的数值放入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
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;
    }
};
/*
同样还是举例说明，首先cur指针指向root 5，此时进入while循环；
因为cur不为NULL，所以将cur存入stack中并将cur指向其左孩子；
接着进入第二轮while循环，此时将cur 4存入satck并令cur指向其左孩子；
进入第三轮循环stack中为5，4，1，且cur为NULL;
进入第四轮循环，开始进入else分支，cur指向1，result存入1；
进入第五轮循环，进入else分支，cur指向4，reault存入4；
进入第六轮循环，进入else分支，cur指向5，result存入5，cur重新赋值为2...
*/

后序遍历

后序遍历的实现相对简单，只需要将前序遍历的中左右变为中右左，接着反转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;
    }
};

统一迭代

实际上前中后遍历的迭代代码是可以统一为一样的风格的（了解即可），之所以之前不一样是因为没有解决遍历节点和处理节点不一致的情况，解决方法是将访问的节点放入栈中，将要处理的节点也放入栈中但需要做上标记；

标记的方法就是将要处理的节点放入栈后，紧跟着放入一个空指针作为标记；这样只有空节点弹出的时候，才将下一个节点放进结果集（也就是只有先出现空节点的时候，才对下一个节点进行处理）

迭代法中序遍历

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<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if (root != NULL) {
            st.push(root);
        }
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                    st.pop();                      		// 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中（要是不弹出就会出现中右中左的情况）
                if (node->right) {
                    st.push(node->right);               // 添加右节点（空节点不入栈）
                }
                st.push(node);                          // 添加中节点
                st.push(NULL); 						  // 中节点访问过，但是还没有处理，加入空节点作为标记。
                if (node->left) {
                    st.push(node->left);    		   // 添加左节点（空节点不入栈）
                }    
            } 
            else { 									// 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           				  // 将空节点弹出
                node = st.top();   				      // 重新取出栈中元素
                st.pop();
                result.push_back(node->val); 	       // 加入到结果集
            }
        }
        return result;
    }
};

3.二叉树的层序遍历

解析

层序遍历指的是从左到右，从上到下遍历二叉树，需要借助一个辅助队列来实现，因为队列先进先出的特点符合从上到下、从左到右逐层遍历的逻辑；

实际上这种层序遍历的方式就是图论中的广度优先遍历；

下面这份代码作为二叉树层序遍历的基本模板，有必要好好理解(实际上使用递归也可以实现，并且不需要借助队列数据结构，但是递归的代码的确过于难以理解，故不推荐)

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 {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;      //result数组作为结果数组，简单来说外层容器result的元素类型为vector<int>，内层容器的元素类型为int；之所以这样设计是因为内层容器代表二叉树的每一层；
        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;
    }
};
/*
同样地，我们结合上面的动画和这里的代码一起解释；
首先将root 6存入queue中，接着进入while循环，对size赋值为1；进入for循环，令node指针指向queue队首，接着弹出队首元素并将队首元素加入vec容器，接着依次加入左孩子和右孩子4，7进入队列；
当一层的节点全部存入vec中后（对应for循环遍历结束），将vec存入result数组；进入下一轮的while训话；
此时队首元素为4，size赋值为2，进入for循环后，存入4并依次加入左孩子和右孩子1，3；
同理，第二个for循环队首元素为7，存入7并依次加入左孩子和右孩子5，8...
*/

4.翻转二叉树

解析

这道题解题思想很简单，只需要将每个节点的左右孩子翻转即可，即可达到整体翻转的效果；

但是关键在于遍历顺序(这是所有二叉树问题的重中之重)，不能使用中序遍历（这将导致某些节点的左右孩子被翻转两次）；

  • 前序遍历递归翻转二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    //1.确定递归函数的参数和返回值
    TreeNode* invertTree(TreeNode* root) {
        //2.确定终止条件
        if (root == NULL) return root;
        //3.确定单层递归的逻辑
        swap(root->left, root->right);  // 中
        invertTree(root->left);         // 左
        invertTree(root->right);        // 右
        return root;
    }
};
  • 前序遍历迭代翻转二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()) {
            TreeNode* node = st.top();              // 中
            st.pop();
            swap(node->left, node->right);
            if(node->right) st.push(node->right);   // 右
            if(node->left) st.push(node->left);     // 左
        }
        return root;
    }
};
  • 层序遍历迭代翻转二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                swap(node->left, node->right); // 节点处理
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return root;
    }
};

5.对称二叉树

解析

判断二叉树是否对称，要比较的不是左右节点，而是根节点的左子树和右子树是否是相互翻转的，即比较的是两个树，因此在递归遍历的过程中要同时遍历两棵子树；

接着比较两个子树的内侧和外侧元素是否相等；

递归解法

本题的遍历顺序只能是后序遍历，即“左右中”，因为要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等 —— 实际上一棵树的遍历顺序是“左右中”，另一棵树的遍历顺序是“右左中”

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:
    //1.确定递归函数的参数和返回值，参数就是左子树和右子树（更准确来说是树的节点），返回值是bool类型的值
    bool compare(TreeNode* left, TreeNode* right) {
        //2.确定终止条件
        //2.1 首先排除空节点的情况（否则后面比较数值的时候会操作空指针，是很危险的事）
        if (left == NULL && right != NULL) return false;       //2.1.1 左节点空，右节点不为空
        else if (left != NULL && right == NULL) return false;  //2.1.2 左节点不为空，右节点为空
        else if (left == NULL && right == NULL) return true;   //2.1.3 左右都为空
        //2.2 排除了空节点，再排除数值不相同的情况
        else if (left->val != right->val) return false;        //2.2.1 左右节点不为空，但左右节点的数值不同
	    //3.确定单层递归的逻辑，单层递归的逻辑就是处理左右节点都不为空，且数值相同的情况
        bool outside = compare(left->left, right->right);   // 比较二叉树外侧是否对称，传入左子树的左孩子、右子树的右子树
        bool inside = compare(left->right, right->left);    // 比较二叉树内侧是否对称，传入左子树的右孩子、右子树的左孩子左
        bool isSame = outside && inside;                    // 如果内外侧都对称则返回ture，只要有一侧不对称就返回false
        return isSame;									 //如上代码可以看出来，左子树的遍历方式是左右中，右子树的遍历方式是右左中
    }
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        return compare(root->left, root->right);
    }
};

迭代解法

本题的迭代解法既可以使用队列也可以使用栈，大致的意思参考下面的动画

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
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        queue<TreeNode*> que;
        que.push(root->left);   // 将左子树头结点加入队列
        que.push(root->right);  // 将右子树头结点加入队列
        
        while (!que.empty()) {  // 接下来就要判断这两个树是否相互翻转
            TreeNode* leftNode = que.front(); que.pop();
            TreeNode* rightNode = que.front(); que.pop();
            if (!leftNode && !rightNode) {  // 左节点为空、右节点为空，此时说明是对称的
                continue;                   //continue是指直接进入下层循环，不执行下面的代码
            }

            // 左右一个节点不为空，或者都不为空但数值不相同，返回false
            if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
                return false;
            }
            que.push(leftNode->left);   // 加入左节点左孩子
            que.push(rightNode->right); // 加入右节点右孩子
            que.push(leftNode->right);  // 加入左节点右孩子
            que.push(rightNode->left);  // 加入右节点左孩子
        }
        return true;
    }
};

6.二叉树的最大深度

递归解法

这道题使用前序遍历可以求得深度，使用后序遍历求的是高度，深度和高度的区别是什么？

  • 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
  • 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）

因此根节点的高度就是二叉树的最大深度，因此本题选用后序遍历求根节点的高度进而得到二叉树的最大深度（实际上使用前序遍历才是真正的求深度的逻辑，但此处因为根节点的高度就是二叉树的最大深度，所以可以直接后序遍历求根节点的高度）；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class solution {
public:
    //1.确定递归函数的参数和返回值，参数是树的根节点，返回值是int型树的深度
    int getdepth(treenode* node) {
        //2.确定终止条件，若节点为空则返回0表示高度为0
        if (node == NULL) return 0;
        //3.确定单层递归的逻辑，先求得左子树的深度，再求得右子树的深度，最后取左右子树深度较大者加1即为以当前节点为根节点的树的深度
        int leftdepth = getdepth(node->left);       // 左
        int rightdepth = getdepth(node->right);     // 右
        int depth = 1 + max(leftdepth, rightdepth); // 中
        return depth;
    }
    int maxdepth(treenode* root) {
        return getdepth(root);
    }
};

迭代解法

迭代解法使用层序遍历是最适合的，因为二叉树的层数就是其最大深度，实际上这道题直接使用层序遍历模板即可求解 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class solution {
public:
    int maxdepth(treenode* root) {
        if (root == NULL) return 0;
        int depth = 0;
        queue<treenode*> que;
        que.push(root);
        while(!que.empty()) {
            int size = que.size();
            depth++; // 记录深度
            for (int i = 0; i < size; i++) {
                treenode* node = que.front();
                que.pop();
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return depth;
    }
};

7.n叉树的最大深度

在介绍了二叉树的最大深度之后，可以直接利用类似的思路

后续递归遍历

1
2
3
4
5
6
7
8
9
10
11
12
class solution {
public:
    int maxdepth(node* root) {
        if (root == 0) return 0;
        int depth = 0;
        //找到子树中深度最大的子树深度，最后加1表示当前根节点的最大深度
        for (int i = 0; i < root->children.size(); i++) {
            depth = max (depth, maxdepth(root->children[i]));
        }
        return depth + 1;
    }
};

层序迭代遍历

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 maxdepth(node* root) {
        queue<node*> que;
        if (root != NULL) que.push(root);
        int depth = 0;
        while (!que.empty()) {
            int size = que.size();
            depth++; // 记录深度
            for (int i = 0; i < size; i++) {
                node* node = que.front();
                que.pop();
                //同理，将所有的子节点都加入队列
                for (int j = 0; j < node->children.size(); j++) {
                    if (node->children[j]) que.push(node->children[j]);
                }
            }
        }
        return depth;
    }
};

8.二叉树的最小深度

后序递归遍历

需要注意的是最小深度很容易理解出错，最小深度指的是根节点到最近叶子节点的最短路径上的节点数量，因此不能将根节点本身算进去（叶子节点指的是左右孩子都为空的节点）；

为了解决上述问题，需要利用以下逻辑：

  • 左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度；

  • 右子树为空，左子树不为空，最小深度是 1 + 左子树的深度；

  • 如果左右子树都不为空，返回左右子树深度最小值 + 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:
    //1.确定函数的参数和返回值
    int getDepth(TreeNode* node) {
        //2.终止条件为遇到空节点返回0表示当前节点的高度为0
        if (node == NULL) return 0;
        
        //3.确定单层逻辑
        int leftDepth = getDepth(node->left);           // 左
        int rightDepth = getDepth(node->right);         // 右
                                                        // 中
        /*
        int leftDepth = getDepth(node->left);
	    int rightDepth = getDepth(node->right);
	    int result = 1 + min(leftDepth, rightDepth);
		return result;
		可能很多人会直接套用最大深度的公式，那么就会导致之前所说的根节点会将到达自己的深度算成最小深度
		*/
        //3.1 当一个左子树为空，右不为空
        if (node->left == NULL && node->right != NULL) { 
            return 1 + rightDepth;
        }   
        //3.2 当一个右子树为空，左不为空
        if (node->left != NULL && node->right == NULL) { 
            return 1 + leftDepth;
        }
        //3.3 如果左右子树都不为空，返回左右子树深度最小值 + 1
        int result = 1 + min(leftDepth, rightDepth);
        return result;
    }

    int minDepth(TreeNode* root) {
        return getDepth(root);
    }
};

层序递归遍历

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:

    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        int depth = 0;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()) {
            int size = que.size();
            depth++; // 记录最小深度
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
                if (!node->left && !node->right) { // 当左右孩子都为空的时候，说明是最低点的一层了，退出
                    return depth;
                }
            }
        }
        return depth;
    }
};

9.完全二叉树的节点个数

解析

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

额…我们看输入和输出的时候很容易产生这样一个疑问，我不是只需要获取root数组的元素个数就知道节点个数了吗，关键真的好像是这样？？？实际考察的是我们对完全二叉树性质的掌握（类中的某个函数是不能获取构造函数的参数的），当然不熟悉直接使用普通二叉树的遍历方法也可以做出来，我们下面会介绍这两种解法；

普通二叉树的后序递归解法：

只需要修改模板加入treeNum变量记录节点数量即可，时间复杂度为O(n)，空间复杂度为O(logn)-递归栈会占用空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
private:
    int getNodesNum(TreeNode* cur) {
        if (cur == NULL) return 0;
        int leftNum = getNodesNum(cur->left);      // 左
        int rightNum = getNodesNum(cur->right);    // 右
        int treeNum = leftNum + rightNum + 1;      // 中
        return treeNum;
    }
public:
    int countNodes(TreeNode* root) {
        return getNodesNum(root);
    }
};

普通二叉树的层序迭代解法：

同理，层序遍历模板不变，增加统计节点数量即可，时间复杂度和空间复杂度均为O(n)；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int countNodes(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        int result = 0;
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                result++;   // 记录节点数量
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return result;
    }
};

完全二叉树性质：完全二叉树分为两种情况，当它为满二叉树的时候直接使用2^深度-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
class Solution {
public:
    //1.传入参数以及确定返回值
    int countNodes(TreeNode* root) {
        //2.确定终止条件
        if (root == nullptr) return 0;
        TreeNode* left = root->left;
        TreeNode* right = root->right;
        int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的，为了下面求指数方便
        while (left) {  // 求左子树深度
            left = left->left;
            leftDepth++;
        }
        while (right) { // 求右子树深度
            right = right->right;
            rightDepth++;
        }
        if (leftDepth == rightDepth) {
            return (2 << leftDepth) - 1; // 这里就是满二叉树的节点数量计算方式(2^深度-1)
        }
        //3.确定单层递归逻辑（实际就是后序遍历）
		int leftTreeNum = countNodes(root->left);       // 左
		int rightTreeNum = countNodes(root->right);     // 右
 		int result = leftTreeNum + rightTreeNum + 1;    // 中
         return result;
    }
};

10.平衡二叉树

解析

需要先强调一下之前的概念：

  • 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数 —— 求深度需要从上至下，使用前序遍历(有一种等价情况是，根节点的高度就是该二叉树的最大深度)；
  • 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数 —— 求高度需要从下至上，使用后序遍历；

该定义来自Wiki，但实际上不同的地方有不同的规定，leecode上规定以节点为度，同时不同的地方对根节点的深度究竟是1还是0的定义也各不相同；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//1.明确函数参数(当前节点)和返回值(当前参数节点为根的树的高度)
int getHeight(TreeNode* node) {
    //2.终止条件是遇到空节点，返回值为0，表示当前节点为根节点的树的高度为0
    if (node == NULL) {
        return 0;
    }
    //3.单层递归逻辑：判断当前传入节点为根节点二叉树是否为平衡，依据是其左子树和右子树高度之差不超过1
    int leftHeight = getHeight(node->left);
    if (leftHeight == -1) return -1;// -1标记该二叉树不平衡
    int rightHeight = getHeight(node->right);
    if (rightHeight == -1) return -1;
    return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);
    // 如果左右子树的差值小于等于1，则返回当前平衡二叉树的高度，否则返回-1
    // -1 表示已经不是平衡二叉树了，否则返回值是以该节点为根节点树的高度
}

另外一个想法是能否像使用层序遍历求深度一样来求高度呢？这是不行的，也是求解高度和深度的区别之一；

在一定条件下迭代是可以转换成递归的，但是本题使用迭代的效率非常低而且代码体系也更加复杂，所以这里我们就不再赘述迭代法；

11.二叉树的所有路径

本题需要明确的两个点是需要使用前序遍历(方便父节点指向子节点)和回溯(方便回退并选择另一条路径)，还需要注意的是回溯法就是递归，没有人会去用迭代实现回溯(回溯是复杂递归，拆分为迭代的复杂程度极其大)

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
class Solution {
private:
    //1.递归函数的参数(根节点、记录路径的path、保存结果的result)和返回值(不需要返回值，设置为void)
    void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {
        path.push_back(cur->val); // 前序遍历的中间节点处理，因为最后一个节点也要加入到path中，如果写在终止条件后面就加不上最后的叶子节点了
        //2.确定终止条件，本题不能直接使用cur==NULL来判断，因为cur==NULL表明此时已经超过叶子节点了，但是我们还需要处理叶子节点，所以需要换一种处理方式
        if (cur->left == NULL && cur->right == NULL) {//此节点是叶子节点
            //终止处理的逻辑
            string sPath;//先使用vector的path记录路径，接着将path转换为string类型，最后将这个string类型的path放入vector中，之所以一开始使用vector的path而不是直接用string是因为vector回溯非常方便：vector类型的path，不管每次路径收集的数字是几位数，总之一定是int，所以就一次 pop_back就可以；反之string类型的path进行回溯需要调用对应位数的次数的回溯pop
            for (int i = 0; i < path.size() - 1; i++) {//2.1 将path中的路径转换为string
                sPath += to_string(path[i]);
                sPath += "->";
            }
            sPath += to_string(path[path.size() - 1]); //2.2 加入最后一个节点(最后一个节点单独处理)
            result.push_back(sPath);				 //2.3 将该string类型的path存入结果集result中
            return;
        }
        //3.确定单层递归逻辑，递归和回溯的过程，因为终止条件并没有判断cur是否为NULL，所以这里需要额外判断一下
        //递归和回溯是一一对应的，有一个递归就需要有一个回溯，要么同时在花括号内，要么同时在花括号外
        //回溯的作用是使得path不能一直加入节点，还需要删除节点
        if (cur->left) { // 左 
            traversal(cur->left, path, result);// 递归
            path.pop_back(); // 回溯
        }
        if (cur->right) { // 右
            traversal(cur->right, path, result);// 递归
            path.pop_back(); // 回溯
        }
    }

public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        vector<int> path;
        if (root == NULL) return result;
        traversal(root, path, result);
        return result;
    }
};

七、回溯算法

0.回溯法概述

回溯是递归的副产品，只要有递归就会有回溯，所以我们所说的回溯函数就是递归函数；

回溯法的本质是穷举所有的可能选出我们想要的答案，所以回溯法尽管很难理解但实际上效率并不是很高；

但是有些问题还真的就只能使用暴力穷举能做，我们能够对回溯法做的优化最多就是加一些剪枝的处理，回溯法一般用于解决如下类型的问题：

  • 组合问题：N个数里面按一定规则找出k个数的集合
  • 切割问题：一个字符串按一定规则有几种切割方式
  • 子集问题：一个N个数的集合里有多少符合条件的子集
  • 排列问题：N个数按一定规则全排列，有几种排列方式
  • 棋盘问题：N皇后，解数独等等

结论：回溯法解决的问题都可以抽象为树形结构(N叉树)，所有回溯法的问题都是如此没有例外(现在知道为什么先介绍树再介绍回溯了吧)

因为回溯法解决的问题抽象出来都是在集合中递归的查找子集，因此集合的大小构成了树的宽度，递归的深度构成了树的深度；

回溯法的三个步骤：

  • 确定回溯函数的参数和返回值
    • 回溯法的返回值一般是void；
    • 回溯法的参数不像普通递归那么容易确定，一般是先写逻辑，需要什么参数写什么参数；
  • 确定回溯函数的终止条件
    • 回溯解决的问题是树形结构，一般而言树的终止条件就是搜索到叶子节点中，对回溯来说就是找到了满足条件的一条答案，将该答案保存并结束本层递归即可；
  • 单层回溯搜索

现在可以解释为什么集合大小就是树的宽度了，因为集合大小等于节点的孩子的数量，回溯函数遍历过程的伪代码如下

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

  • for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次；

  • backtracking这里自己调用自己，实现递归；

for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索到的叶子节点就是找到的其中一个结果；

整个回溯算法的模板算法如下

1
2
3
4
5
6
7
8
9
10
11
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

八、贪心算法

九、动态规划

0.动态规划概述

动态规划Dyanmic Programming，简称DP，针对具有很多重叠子问题的问题来说很适合使用动态规划；

动态规划中的每一个状态一定是由上一个状态推导出来的，区别于直接从局部选最优的贪心算法；

需要注意的是分治法和动态规划都要求原问题具有最优子结构（可以认为动态规划也是一种分治思想），都是将原问题分治接着合并子问题的解形成原问题的解，分治法通常使用递归求解，动态规划可以使用自底向上的迭代或自顶向下的递归，不同点在于分治法将子问题看作独立的而动态规划将子问题看作相互依赖的、有重叠部分的；（分治法是万精油，动态规划可以求解全局最优并避免重复的计算，但是在使用上有一定限制(无后效性)）

通识课程
#刷题 #考研 #面试
算法刷题
https://gintoki-jpg.github.io/2022/06/27/其他_算法刷题/
作者
杨再俨
发布于
2022年6月27日
许可协议