附录

补充知识（持续更新ing）

常用头文件

#include <iostream>     // 输入输出流
#include <vector>       // 向量容器
#include <string>       // 字符串类
#include <algorithm>    // 常用算法
#include <cmath>        // 数学函数
#include <limits>       // 数值极限
#include <climits>      // 整型极限
#include <queue>        // 队列
#include <stack>        // 栈
#include <map>          // 映射容器
#include <set>          // 集合容器
#include <unordered_map>// 无序映射容器
#include <unordered_set>// 无序集合容器
#include <numeric>      // 数值操作

一次性包含所有常用库

#include <bits/stdc++.h>

时间复杂度

时间复杂度是一个函数，它定性描述该算法的运行时间。

通常会估算算法的操作单元数量来代表程序消耗的时间，这里默认CPU的每个单元运行消耗的时间都是相同的。

假设算法的问题规模为n，那么操作单元数量便用函数f(n)来表示，随着数据规模n的增大，算法执行时间的增长率和f(n)的增长率相同，这称作为算法的渐进时间复杂度，简称时间复杂度，记为O(f(n))。

空间复杂度

空间复杂度是一个算法在运行过程中占用内存空间大小的量度，基座S(n) = O(f(n))。

空间复杂度(Space Complexity)基座S(n)依然使用大O来表示。利用程序的空间复杂度，可以对程序运行中需要多少内存有个预先估计。

  • 空间复杂度是考虑程序运行时占用内存的大小，而不是可执行文件的大小。
  • 不要以为空间复杂度就已经精确的掌握了程序的内存使用大小，很多因素会影响程序真正内存使用大小，例如编译器的内存对齐，编程语言容器的底层实现等等这些都会影响到程序内存的开销。所以空间复杂度是预先大体评估程序内存使用的大小。

空间复杂度是logn的情况确实有些特殊，其实是在递归的时候，会出现空间复杂度为logn的情况。

不同语言的内存管理

  • C\C++这种内存堆空间的申请和释放完全考自己管理
  • Java依赖JVM来做内存管理，不了解jvm内存管理的机制，很可能会因一些错误的代码写法而导致内存泄漏或内存溢出
  • Python内存管理是由私有堆空间管理的，所有的python对象和数据结构都存储在私有对空间中。程序员没有访问堆的权限，只有解释器才能操作。

例如Python万物皆对象，并且将内存操作封装的很好，所以python的基本数据类型所用的内存会要远大于存放纯数据类型所占的内存，例如，存储int型数据需要四个字节，但是使用python申请一个对象来存放数据的话，所用空间要远大于四个字节。

C++的内存管理

程序运行时所需的内存空间分为固定部分和可变部分，如下：

内存管理

固定部分的内存消耗是不会随着代码运行产生变化的，可变部分则是会产生变化的，更具体一些，一个由C/C++编译的程序占用的内存分为以下几个部分：

  • 栈区(Stack)：由编译器自动分配释放，存放函数的参数值，局部变量的值等，其操作方式类似于数据结构中的栈。
  • 堆区(Heap)：一般由程序员分配释放，若程序员不释放，程序结束时可能由OS收回。
  • 未初始化数据区(Uninitialized Data)：存放未初始化的全局变量和静态变量
  • 初始化数据区(Initialized Data)：存放已经初始化的全局变量和静态变量
  • 程序代码区(Text)：存放函数体的二进制代码

代码区和数据区所占空间都是固定的，而且占用的空间非常小，那么看运行时消耗的内存主要看可变部分。

在可变部分中，栈区间的数据在代码块之心结束之后，系统会自动回收，而堆区间数据是需要程序员自己回收，所以也就是造成内存泄漏的发源地。

而java和python的话则不需要程序员去考虑内存泄漏的问题，虚拟机都做了这些事情。

如何计算程序占用多大内存

想要计算出自己的程序会占用多少内存就一定要了解自己定义的数据类型的大小，如下：

1个字节占8比特，那么4个字节就是32个比特，可存放数据的大小为2^32，也就是4G空间的大小，即可以寻找4G空间大小的内存地址。

现在大家使用的计算机一般都是64位了，所以编译器也都是64位的。

安装64位的操作系统的计算机内存都已经超过了4G，也就是指针大小如果还是4个字节的话，就已经不能寻址全部的内存地址，所以64位编译器使用8个字节的指针才能寻找所有的内存地址。

内存对齐

只要可以跨平台的编程语言都需要做内存对齐，Java、Python都是一样的。

为什么会有内存对齐？

主要有两个原因：

  • 1.平台原因：不是所有的硬件平台都能访问内存地址上的任意数据，某些硬件平台只能在某些地址处取某些特定类型的数据，否则抛出硬件异常。为了同一个程序可以在多平台运行，需要内存对齐。
  • 2.硬件原因：经过内存对齐后，CPU访问内存的速度大大提升。
struct node{
   int num;
   char cha;
}st;
int main() {
    int a[100];
    char b[100];
    cout << sizeof(int) << endl;
    cout << sizeof(char) << endl;
    cout << sizeof(a) << endl;
    cout << sizeof(b) << endl;
    cout << sizeof(st) << endl;
}

其输出的结果依次为：

4
1
400
100
8

此时会发现，和单纯计算字节数的话是有一些误差的。

这就是因为内存对齐的原因。

来看一下内存对齐和非内存对齐产生的效果区别。

CPU读取内存不是一次读取单个字节，而是一块一块的来读取内存，块的大小可以是2，4，8，16个字节，具体取多少个字节取决于硬件。

假设CPU把内存划分为4字节大小的块，要读取一个4字节大小的int型数据，来看一下这两种情况下CPU的工作量：

char型的数据和int型的数据挨在一起，该int数据从地址1开始，那么CPU想要读这个数据的话需要以下几步操作：

  • 1.因为CPU是四个字节来寻址，首先CPU先读取0、1、2、3处的四个字节数据
  • 2.CPU读取4、5、6、7处的四个字节数据
  • 3.合并地址1、2、3、4处四个字节的数据才是本次操作需要的int数据

此时一共需要两次寻址，一次合并的操作

内存对齐会浪费内存资源，但事实上，相对来说计算机内存资源一般都是充足的，我们更希望的是提高运行速度。

编译器一般都会做内存对齐的优化操作，也就是说当考虑程序真正占用的内存大小的时候，也需要认识到内存对齐的影响。

数组

基础知识

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

数组可以方便的通过下标索引的方式获取到下标下对应的数据。

两点注意：

  • 数组下标都是从0开始的
  • 数组内存空间的地址是连续的

正是因为数组的内存空间地址是连续的，所以在删除或增添元素的时候，就难免要移动其他元素的地址。

数组的元素是不能删的，只能覆盖。

不同编程语言的内存管理是不一样的，以C++为例，在C++中二维数组是连续分布的。

leetcode题目链接

二分查找

移除元素

有序数组的平方

长度最小的子数组

螺旋矩阵 II

链表

链表理论基础

链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域，最后一个节点的指针域指向null。

链表的入口节点称为链表的头节点也就是head。

链表的类型

单链表

单链表（Singly Linked List）是一种常见的线性数据结构，由一系列节点组成，每个节点包含两部分：数据部分和指针部分。其中，数据部分用于存储数据，指针部分用于指向下一个节点。

单链表中的节点按照顺序连接，每个节点只有一个指针指向下一个节点，而最后一个节点的指针部分通常指向一个特殊的值（如NULL），表示链表的结束。

双链表

单链表中的指针域只能指向节点的下一个节点。

双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

双链表既可以向前查询也可以向后查询。

循环链表

顾名思义，就是链表首尾相连。

循环链表可以用来解决瑟夫环问题。

链表的存储方式

链表是通过指针域的指针链接在内存中各个节点。

所以链表中的节点在内存中不是连续分布的，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

链表的定义

// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

链表的操作

删除节点

添加节点

性能分析

数组在定义的时候，长度是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。

链表的长度可以是不固定的，并且可以动态增删，适合数量不固定，频繁增删，较少查询的场景。

leetcode题目链接

移除链表元素

链表操作的两种方式：

  • 直接使用原来的链表来进行删除操作

  • 设置一个虚拟头结点在进行删除操作

在单链表中移除头结点 和 移除其他节点的操作方式是不一样

可以设置一个虚拟头结点，这样原链表的所有节点就都可以按照统一的方式进行移除了

时间复杂度: O(n)

空间复杂度: O(1)

设计链表

这道题目设计链表的五个接口：

  • 获取链表第index个节点的数值

  • 在链表的最前面插入一个节点

  • 在链表的最后面插入一个节点

  • 在链表第index个节点前面插入一个节点

  • 删除链表的第index个节点

时间复杂度: 涉及 index 的相关操作为 O(index), 其余为 O(1)

空间复杂度: O(n)

反转链表

  1. 再定义一个新的链表，实现链表元素的反转，但这是对内存空间的浪费

  2. 改变链表的next指针的指向，直接将链表反转

双指针法

时间复杂度: O(n)
空间复杂度: O(1)

两两交换链表中的节点

画图模拟

时间复杂度：O(n)

空间复杂度：O(1)

删除链表的倒数第N个结点

最开始想的是直接用链表结点个数减去倒数第n个，找到倒数第n个节点的前一个节点，然后直接删除，但是这有一个前提，就是链表的长度或者节点个数已知，可以先遍历整个链表得到，但这样的话总共要遍历两次链表

用双指针法就巧妙许多，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾，删掉slow所指向的节点就可以了

fast首先走n + 1步 ，为什么是n+1呢，因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作）

时间复杂度: O(n)

空间复杂度: O(1)

链表相交

指针相等

求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，因为相交的节点一定在对齐之后的位置

环形链表 II

使用快慢指针法，分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环

fast是走两步，slow是走一步，其实相对于slow来说，fast是一个节点一个节点的靠近slow的，所以fast一定可以和slow重合

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
            // 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇
            if (slow == fast) {
                ListNode* index1 = fast;
                ListNode* index2 = head;
                while (index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index2; // 返回环的入口
            }
        }
        return NULL;
    }
};

这道题仔细看一下

哈希表

哈希表理论基础

哈希表(Hash table)——散列表

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

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

一般哈希表都是用来快速判断一个元素是否出现集合里

哈希函数

例如要查询一个名字是否在学校里，哈希函数把学生的姓名直接映射为哈希表上的索引，然后就可以通过查询索引下标快速知道这位同学是否在这所学校里

为了保证映射出来的索引数值都落在哈希表上，会再次对数值做一个取模的操作

哈希碰撞

拉链法：发生冲突的元素都被存储在链表中

线性探测法:使用线性探测法，一定要保证tableSize大于dataSize。依靠哈希表中的空位来解决碰撞问题

常见的三种哈希结构

使用哈希法来解决问题的时候，一般会选择如下三种数据结构：

  • 数组

  • set（集合）

  • map（映射）

std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。

std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的。

当要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。

map 是一个key value 的数据结构，map中，对key是有限制，对value没有限制的，因为key的存储方式使用红黑树实现的。

虽然std::set、std::multiset 的底层实现是红黑树，不是哈希表，std::set、std::multiset 使用红黑树来索引和存储，不过给我们的使用方式，还是哈希法的使用方式，即key和value。所以使用这些数据结构来解决映射问题的方法，依然称之为哈希法。 map也是一样的道理。

总结

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

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

leetcode题目链接

有效的字母异位词

数组其实就是一个简单哈希表，这道题目中字符串只有小写字符，可以定义一个数组，来记录字符串s里字符出现的次数

遍历字符串s的时候，只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可

同样在遍历字符串t的时候，对t中出现的字符映射哈希表索引上的数值再做-1的操作

时间复杂度: O(n)

空间复杂度: O(1)

两个数组的交集

std::unordered_set的底层实现是哈希表， 使用unordered_set 读写效率是最高的，并不需要对数据进行排序，而且还不要让数据重复，所以选择unordered_set

先把第一个数组转化为unordered_set

然后循环第二个数组，分别在第一个set中查找第二个数组中的值，找到就放入结果set中

快乐数

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

判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止

判断sum是否重复出现就可以使用unordered_set

时间复杂度: O(logn)

空间复杂度: O(logn)

两数之和

需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法

本题不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用key value结构来存放，key来存元素，value来存下标，使用map正合适

这道题目中并不需要key有序，选择std::unordered_map效率更高

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map <int,int> map;
        for(int i = 0; i < nums.size(); i++) {
            // 遍历当前元素，并在map中寻找是否有匹配的key
            auto iter = map.find(target - nums[i]); 
            if(iter != map.end()) {
                return {iter->second, i};
            }
            // 如果没找到匹配对，就把访问过的元素和下标加入到map中
            map.insert(pair<int, int>(nums[i], i)); 
        }
        return {};
    }
};

时间复杂度: O(n)

空间复杂度: O(n)

四数相加 II

定义一个unordered_map，key放前两个数组的两数之和，value放相同的两数之和出现的次数

遍历另外两个数组，找到如果 0-两数之和 在map中出现过的话，就用把map中key对应的value也就是出现次数统计出来

赎金信

判断一个字符串是否可以由另一个字符串组成

  1. 两层暴力for循环

  2. 哈希法

    因为只有小写字母，可以采用空间换取时间的哈希策略，用一个长度为26的数组来记录magazine里字母出现的次数

    然后再用ransomNote去验证这个数组是否包含了ransomNote所需要的所有字母

    依然是数组在哈希法中的应用

为什么使用数组而不用map？

因为使用map的空间消耗要比数组大一些的，map要维护红黑树或者哈希表，而且还要做哈希函数，费时，数据量大的话就能体现出来差别

数组更加简单直接有效

时间复杂度: O(n)

空间复杂度: O(1)

双指针法：

三数之和

先对数组进行排序

在数组中找到 abc 使得a + b +c =0，相当于 a = nums[i]，b = nums[left]，c = nums[right]

接下来何移动left 和right呢， 如果nums[i] + nums[left] + nums[right] > 0 就说明此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些

如果 nums[i] + nums[left] + nums[right] < 0 说明 此时三数之和小了，left就向右移动，才能让三数之和大一些，直到left与right相遇为止

去重
O(n^2)

四数之和

四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值，依然是循环内有left和right下标作为双指针，找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况，三数之和的时间复杂度是O(n^2)，四数之和的时间复杂度是O(n^3)

剪枝

字符串

反转字符串

反转字符串 II

在遍历字符串的过程中，让 i += (2 * k)，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间

替换数字

双指针法

先把字符串扩容成替换后的长度，然后一个指针指向新的末尾，一个指针指向旧的末尾

s.resize(s.size() + count * 5);

从后向前替换

很多数组填充类的问题，其做法都是先预先给数组扩容带填充后的大小，然后在从后向前进行操作

反转字符串里的单词

先将整个字符串都反转过来，单词的顺序指定是倒序了，只不过单词本身也倒序了，再把单词反转一下，单词就正过来了

综合性的题目

右旋字符串

先整体倒叙，把两段子串顺序颠倒，两个段子串里的的字符再倒叙一次

找出字符串中第一个匹配项的下标

KMP 经典题目

KMP主要应用在字符串匹配上

KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了

如何记录已经匹配的文本内容，是KMP的重点，也是next数组的重任

next数组就是一个前缀表（prefix table）

前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配

前缀表的任务是当前位置匹配失败，找到之前已经匹配上的位置，再重新匹配，此也意味着在某个字符比匹配的时候，前缀表会告诉你下一步匹配中，模式串应该跳到哪个位置

前缀表：记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀

最长公共前后缀

字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。

后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串

这道题要重点看

重复的子字符串

判断字符串s是否由重复子串组成，只要两个s拼接在一起，里面还出现一个s的话，就说明是由重复子串组成

双指针法

移除元素

双指针法：通过一个快指针和慢指针在一个for循环下完成两个for循环的工作

快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组、

慢指针：指向更新 新数组下标的位置

时间复杂度：O(n)

空间复杂度：O(1)

反转字符串

翻转字符串里的单词

思路：

  1. 移除多余空格

  2. 将整个字符串反转

  3. 将每个单词反转

反转链表

删除链表的倒数第 N 个结点

链表相交

环形链表 II

三数之和

四数之和

栈与队列

基础知识

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

栈

栈和队列是STL（C++标准库）里面的两个数据结构

C++标准库是有多个版本的，要知道我们使用的STL是哪个版本，才能知道对应的栈和队列的实现原理

三个最为普遍的STL版本：

HP STL 其他版本的C++ STL，一般是以HP STL为蓝本实现出来的，HP STL是C++ STL的第一个实现版本，而且开放源代码。

P.J.Plauger STL 由P.J.Plauger参照HP STL实现出来的，被Visual C++编译器所采用，不是开源的。

SGI STL 由Silicon Graphics Computer Systems公司参照HP STL实现，被Linux的C++编译器GCC所采用，SGI STL是开源软件，源码可读性甚高。

接下来介绍的栈和队列也是SGI STL里面的数据结构， 知道了使用版本，才知道对应的底层实现。

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

栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）。

所以STL中栈往往不被归类为容器，而被归类为container adapter（容器适配器）。

那么问题来了，STL 中栈是用什么容器实现的？

栈的内部结构，栈的底层实现可以是vector，deque，list 都是可以的， 主要就是数组和链表的底层实现。

我们常用的SGI STL，如果没有指定底层实现的话，默认是以deque为缺省情况下栈的底层结构。

deque是一个双向队列，只要封住一段，只开通另一端就可以实现栈的逻辑了。

SGI STL中 队列底层实现缺省情况下一样使用deque实现的。

我们也可以指定vector为栈的底层实现，初始化语句如下

std::stack<int, std::vector<int> > third;  // 使用vector为底层容器的栈

队列

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

也可以指定list 为起底层实现，初始化queue的语句如下：

std::queue<int, std::list<int>> third; // 定义以list为底层容器的队列

所以STL 队列也不被归类为容器，而被归类为container adapter（ 容器适配器）。

这里讲的都是C++语言中的情况， 使用其他语言也要思考栈与队列的底层实现问题

leetcode题目链接

用栈实现队列

两个栈，一个进 一个出

用队列实现栈

一个队列

将除了最后一个元素外的所有元素重新添加到队列尾部即可实现先进后出

有效的括号

括号匹配是使用栈解决的经典问题

失败有三种情况：

左边多了

左右不匹配

右边多了

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

有效的括号 是匹配左右括号，本题是匹配相邻元素，最后都是做消除的操作

可以使用一个栈作为辅助，可以把字符串直接作为栈，这样就省去了最后再把栈转化为字符串的操作

逆波兰表达式求值

每一个子表达式要得出一个结果，然后拿这个结果再进行运算，这不就是一个相邻字符串消除的过程

滑动窗口最大值

单调队列（再看一下）

前 K 个高频元素

要统计元素出现频率
对频率排序
找出前K个高频元素(小顶堆)

二叉树

理论基础

二叉树的种类

满二叉树

完全二叉树

二叉搜索树

二叉搜索树是一个有序树。

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

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

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

平衡二叉搜索树

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

C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是logn，

注意这里没有说unordered_map、unordered_set，unordered_map、unordered_set底层实现是哈希表

二叉树的存储方式

二叉树可以链式存储，也可以顺序存储

二叉树的遍历方式

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

深度优先遍历：先往深走，遇到叶子节点再往回走

广度优先遍历：一层一层的去遍历

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

深度优先遍历

前序遍历（递归法，迭代法）

中序遍历（递归法，迭代法）

后序遍历（递归法，迭代法）

广度优先遍历

层次遍历（迭代法）

二叉树的定义

链式存储的二叉树节点的定义方式：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

letcode题目

二叉树的递归遍历

递归算法三要素

  1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。

  2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。

  3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

二叉树的前序遍历

二叉树的后序遍历

二叉树的中序遍历

二叉树的迭代遍历

二叉树的统一迭代法

二叉树层序遍历

二叉树的层序遍历

用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑

二叉树的层次遍历 II

相对于二叉树的层序遍历，就是最后把result数组反转一下就可以了。
reverse(begin(),end())

二叉树的右视图

层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result就可以了。

二叉树的层平均值

层序遍历的时候把一层求个总和在取一个均值

因为要求均值，所以定义的vector要为double类型

在每个树行中找最大值

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

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

和上题一样

二叉树的最大深度

前序求的是深度，后序求的是高度

而根节点的高度就是二叉树的最大深度

递归 求左右子树的高度 然后再求最大值 然后+1

同样可以层序遍历，每层+1

二叉树的最小深度

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。注意是叶子节点。

左右子树都为空的节点才是叶子节点！

其他题目链接

翻转二叉树

遍历的过程中去翻转每一个节点的左右孩子就可以达到整体翻转的效果。

注意只要把每一个节点的左右孩子翻转一下，就可以达到整体翻转的效果

这道题目使用前序遍历和后序遍历都可以，唯独中序遍历不方便，因为中序遍历会把某些节点的左右孩子翻转了两次！

红黑树就是一种二叉平衡搜索树，这两个树不是独立的，所以C++中map、multimap、set、multiset的底层实现机制是二叉平衡搜索树，再具体一点是红黑树。

对称二叉树

比较的其实不是左孩子和右孩子，而是左节点右节点

完全二叉树的节点个数

万能的层序遍历，每次循环+1就是节点个数

当然也可以用递归

平衡二叉树

求深度可以从上到下去查 所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）

二叉树的所有路径

回溯 后面再看

左叶子之和

左叶子的明确定义：节点A的左不为空，且左的左右都为空（说明是叶子节点），那么A节点的左为左叶子节点

找树左下角的值

层序遍历，把每层第一个值赋给result，循环结束最后的值就是树左下角的值

路径总和

如果最后count == 0，同时到了叶子节点的话，说明找到了目标

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

没看懂，之后再看

最大二叉树

在数组[left,right]构造，左右分别构造，找出区间的最大值的索引，创建一个新节点

合并二叉树

递归

二叉搜索树中的搜索

二叉搜索树是一个有序树

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

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

它的左、右子树也分别为二叉搜索树

验证二叉搜索树

有效 二叉搜索树定义如下：

节点的左子树只包含 小于 当前节点的数

节点的右子树只包含 大于 当前节点的数

所有左子树和右子树自身必须也是二叉搜索树

中序遍历下，输出的二叉搜索树节点的数值是有序序列

二叉搜索树中不能有重复元素

所以先中序遍历整个树得到一个数组，然后判断这个数组是否有序

二叉搜索树的最小绝对差

二叉搜索树是有序的

遇到在二叉搜索树上求什么最值，差值之类的，就把它想成在一个有序数组上求最值，求差值

二叉搜索树中的众数

把这个树都遍历了，用 map 统计频率，用 vector 排个序，最后出去前面高频的元素

二叉树的最近公共祖先

后面再做，还有7题

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

26-33

回溯算法

理论基础

回溯法也可以叫做回溯搜索法，它是一种搜索的方式。

回溯是递归的副产品，只要有递归就会有回溯。

回溯法的效率

回溯法并不是什么高效的算法。

回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

回溯法解决的问题

回溯法，一般可以解决如下几种问题：

组合问题：N个数里面按一定规则找出k个数的集合

切割问题：一个字符串按一定规则有几种切割方式

子集问题：一个N个数的集合里有多少符合条件的子集

排列问题：N个数按一定规则全排列，有几种排列方式

棋盘问题：N皇后，解数独等等

组合是不强调元素顺序的，排列是强调元素顺序。

组合无序，排列有序

如何理解回溯法

回溯法解决的问题都可以抽象为树形结构

因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。

递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。

回溯法模板

回溯三部曲

回溯函数模板返回值以及参数

回溯算法中函数返回值一般为void。

因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。

回溯函数伪代码如下：

void backtracking(参数)

回溯函数终止条件

什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。

所以回溯函数终止条件伪代码如下：

if (终止条件) {
    存放结果;
    return;
}

回溯搜索的遍历过程

回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。

回溯函数遍历过程伪代码如下：

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

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

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

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

回溯算法模板框架如下：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

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

LeetCode题目链接

组合

每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围

图中可以发现n相当于树的宽度，k相当于树的深度

图中每次搜索到了叶子节点，我们就找到了一个结果

剪枝：

如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了

  1. 已经选择的元素个数：path.size();

  2. 所需需要的元素个数为: k - path.size();

  3. 列表中剩余元素（n-i） >= 所需需要的元素个数（k - path.size()）

  4. 在集合n中至多要从该起始位置 : i <= n - (k - path.size()) + 1，开始遍历

组合总和III

处理过程 和 回溯过程是一一对应的，处理有加，回溯就要有减

电话号码的字母组合

组合总和

组合总和II

树层去重的话，需要对数组排序

分割回文串

判断一个字符串是否是回文,可以使用双指针法，一个指针从前向后，一个指针从后向前，如果前后指针所指向的元素是相等的，就是回文字符串了。

复原IP地址

段位以0为开头的数字不合法

段位里有非正整数字符不合法

段位如果大于255了不合法

子集

子集II

去重：

if (i > 0 && nums[i] == nums[i - 1] &&used[i - 1] == false) {
                continue;
            }

递增子序列

类似求子集问题，也是要遍历树形结构找每一个节点，所以和回溯算法：求子集问题一样，可以不加终止条件，startIndex每次都会加1，并不会无限递归。

全排列

全排列 II

一般来说，组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果

重新安排行程

困难题，之后看

N皇后

皇后们的约束条件：

不能同行

不能同列

不能同斜线

解数独

之后看

贪心算法

贪心的本质是选择每一阶段的局部最优，从而达到全局最优

常识性推导加上举反例

LeetCode题目链接

分发饼干

这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩

摆动序列

局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值

整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列

最大子序和

遇到累积和为负数，直接重置为0

买卖股票的最佳时机 II

本题要清楚两点：

只有一只股票

当前只有买股票或者卖股票的操作

收集正利润的区间，就是股票买卖的区间，而我们只需要关注最终利润，不需要记录区间

局部最优：收集每天的正利润，全局最优：求得最大利润

跳跃游戏

贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点

跳跃游戏 II

K次取反后最大化的数组和

加油站

再看看

分发糖果

确定一边之后，再确定另一边，例如比较每一个孩子的左边，然后再比较右边，如果两边一起考虑一定会顾此失彼

柠檬水找零

根据身高重建队列

到两个维度权衡的时候，一定要先确定一个维度，再确定另一个维度

如果两个维度一起考虑一定会顾此失彼

list比vector高效

vector的底层实现也是普通数组

vector的大小有两个维度一个是size一个是capicity

而capicity是vector底层数组（就是普通数组）的大小，capicity可不一定就是size

当insert数据的时候，如果已经大于capicity，capicity会成倍扩容，但对外暴漏的size其实仅仅是+1

重新申请一个二倍于原数组大小的数组，然后把数据都拷贝过去，并释放原数组内存

用最少数量的箭引爆气球

无重叠区间

划分字母区间

合并区间

单调递增的数字

监控二叉树

困难题，之后看

动态规划

理论基础

Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的

动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的

动态规划是由前一个状态推导出来的，而贪心是局部直接选最优的

解题步骤

  1. 确定dp数组（dp table）以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

遇到问题时，可以先思考这三个问题：

  1. 这道题目我举例推导状态转移公式了么？

  2. 我打印dp数组的日志了么？

  3. 打印出来了dp数组和我想的一样么？

leetcode题目链接

斐波那契数

爬楼梯

使用最小花费爬楼梯

不同路径

不同路径 II

整数拆分

用贪心做更简单

动规之后再看看

不同的二叉搜索树

dp[i] += dp[j - 1] * dp[i - j]; ，j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量

分割等和子集

此系列博客是我在学习过程中，参考代码随想录博客，自己手敲实现一遍的，作为一个学习过程的记录。