---

前言

这里是学习c++，练习一下算法题，简单的笔记

一、二分法

1、区分边界

情景：在有序且无重复元素的数组中（因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的），找满足某个条件的数的位置；

对于左闭右闭的区间里，也就是**[left, right]** ，默认升序数组。

// 版本一
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;
    }
};

对于在左闭右开的区间里，也就是**[left, right)** ，默认升序数组。

// 版本二
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;
    }
};

int right = nums.size(); 是因为“ 左闭右开 ”，但是我得包含整个数组的元素，所以 right = nums.size() ，此时nums[1]~nums[-1]都可以取到，nums[ nums.size()]不会取到，且符合“ 左闭右开 ”。

二、双指针

1、左右指针

场景：左右双指针算法在解决问题的过程中会生成两个指针，一个指向头部，一个指向尾部，从两端向中间逼近，直到满足条件或者两个指针相遇为止. 二分查找就是一种左右双指针算法的应用场景，其他使用情况基本上可以总结为数组中元素组合问题。

i ：代表左指针，指向数组首部。
j ：代表右指针，指向数组尾部。

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int k = A.size() - 1;
        vector<int> result(A.size(), 0);//赋值为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;
    }
};

2、快慢指针

场景：通过设置两个指针不断进行单向移动来解决问题的方法。

形式:两个指针分别指向不同的序列；两个指针指向同一个序列。比如：快速排序的划分过程。

实现：本来是双层for循环，O(n²)的时间复杂度。通过双指针算法可以优化到O(n)的时间复杂度。那是如何优化的时间复杂度呢？其实是当一个指针满足条件后才会单向移动，没有指针的回溯，而每次都会有指针的移动。简单说就是有个快指针可以不停的移动，有个慢指针需要符合条件后才能移动，在翻转链表中，无需条件，快慢指针同时移动。

①两个指针指向同一个序列

模板：

slow = 0 # 1
   for fast in range(len(nums)):
       if  是slow想要的元素：
              nums[slow] = nums[fast]  #  nums[slow+1] = nums[fast]
              slow += 1
    return slow， nums # slow+1， nums

例题1

②有条件的快慢指针

fast 快指针：指向符合要求的值。
slow 慢指针：指向数组中需要更新的位置。

// 时间复杂度：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];
            }
        }
        return slowIndex;
    }
};

例题2

③无条件的快慢指针

翻转链表，见链表例题

④无条件的一次跳2个单位的快慢指针

两两交换链表节点，见链表

⑤相隔固定单位的快慢指针

删除链表的倒数第N个节点，可以看代码随想录

三、滑动窗口

所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们想要的结果，本质上还是双指针问题。

分清楚：

窗口内是什么？
如何移动窗口的起始位置？
如何移动窗口的结束位置？

滑动窗口，快慢指针类型：

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

其中，i 是慢指针，j 是快指针，前窗口的值大于等于s了就移动慢指针，这里要用while循环，不能用if，这是关键点。

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX;//nums.size()+1即可
        int sum = 0; // 滑动窗口数值之和
        int i = 0; // 滑动窗口起始位置
        int subLength = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
            while (sum >= s) {
                subLength = (j - i + 1); // 取子序列的长度
                result = result < subLength ? result : subLength;
                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};

四、模拟过程

坚持循环不变量原则，就是在循环中保持一定的规则、不变的因素。

例题1

vector<vector<int>> vc ：代表右下左上四个方向的dx与dy。

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<int> v( n, 0 );
        vector<vector<int>> vv(n, v);
        vector<vector<int>> vc = {//int vc[][]
            { 0, 1 },
            { 1, 0 },
            { 0, -1 },
            { -1, 0 }
        };
        int x = 0;
        int y = 0;
        int tmp = 1;
        vv[x][y] = 1;
        while (1) {
            if (tmp == n * n) break;
            for (int i = 0; i < 4; i++) {
                int dx = vc[i][0];
                int dy = vc[i][1];
                while (x+dx >=0 && x+dx <n && y+dy >=0 && y+dy < n && tmp<= n*n) {//越界情况
                    if (vv[x + dx][y + dy] != 0)//已经赋值过的情况
                        break;
                    x += dx;
                    y += dy;
                    tmp++;
                    vv[x][y] = tmp;
                    if (tmp == n * n) break;
                };
            }
        }
        return vv;
    }
};

五、前缀和

前缀和的思想是重复利用计算过的子数组之和，从而降低区间查询需要累加计算的次数。
sum[ i ] :代表nums[]数组中，下标为0 - i 的元素之和。
or nums[] 数组中前 i 个元素之和，下标为 0~ i-1的元素之和。

例题1

sum[ i ] :代表nums[]数组中，下标为0 - i 的元素之和。
要求 区间下标 [2, 5] 的区间和，那么应该是 sum[5] - sum[1].

class Solution {
public:
    int takeSum(vector<int>nums, int n, int m) {
    	int presum = 0;
    	vector<int> pre(nums.size()-1 , 0);
    	for(int i = 0; i < nums.size(); i++){
    		presum += nums[i];
    		pre[i] = presum;
    	}
    	return pre[m] - pre[n-1];
	 };

六、链表

因next、pre故要考虑其上下结点

单链表定义：

Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

1、虚拟头结点

在单链表中，头节点和其他节点的处理方式不同，为了使得操作一致，可以设置一个虚拟头结点，这样原链表的所有节点就都可以按照统一的方式进行操作了。

ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
dummyHead->next = head; // 将虚拟头结点指向head，这样方便后面做操作

因为next指向的是下一个节点的地址，所以虚拟头节点最好也是指针类型，统一用“ ->” 操作。

2、添加节点

有虚拟节点的情况下，

添加头节点：

newNode->next = _dummyHead->next;
_dummyHead->next = newNode;

添加尾节点：遍历到尾部，再添加新的节点

while(cur->next != nullptr){
	cur = cur->next;
}
cur->next = newNode;

在中间添加节点：在第index个节点处添加节点，需要找到prenode，而不是indexnode。
prenode -》indexnode -》nextnode
prenode -》newnode -》 indexnode -》nextnode

LinkedNode* cur = _dummyHead;//不是_dummyHead->next
while(index--) {
	cur = cur->next;
}
newNode->next = cur->next;
cur->next = newNode;

3、翻转链表

画图分析，注意while中的退出条件。

①双指针法

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp; // 保存cur的下一个节点
        ListNode* cur = head;
        ListNode* pre = NULL;
        while(cur) {
            temp = cur->next;  // 保存一下 cur的下一个节点，因为接下来要改变cur->next
            cur->next = pre; // 翻转操作
            // 更新pre 和 cur指针
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

②递归法

class Solution {
public:
    ListNode* reverse(ListNode* pre,ListNode* cur){
        if(cur == NULL) return pre;
        ListNode* temp = cur->next;
        cur->next = pre;
        // 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步
        // pre = cur;
        // cur = temp;
        return reverse(cur,temp);
    }
    ListNode* reverseList(ListNode* head) {
        // 和双指针法初始化是一样的逻辑
        // ListNode* cur = head;
        // ListNode* pre = NULL;
        return reverse(NULL, head);
    }
};

③栈

其实有时候想到了最优解的方法，但未必能写出来。
将链表从头到尾入栈，再出栈，一个个的next，方法很简单，效率不是最高，但能快速实现。

4、两两交换节点

交换俩个节点，需要知道4个节点：pre（虚拟头节点开始）、cur、cur.nex、tmp;
while (cur != nullptr && cur->next != nullptr)退出条件，分奇偶。

ListNode* swapPairs(ListNode* head) {
	ListNode* myhead = new ListNode(0, head);
	ListNode* pre = myhead;
	ListNode* cur = head;
	ListNode* tmp = nullptr;
	while (cur != nullptr && cur->next != nullptr)
	{
		tmp = cur->next->next;
		pre->next = cur->next;
		cur->next->next = cur;
		cur->next = tmp;
		pre = pre->next->next;
		cur = tmp;
	} 
	return myhead->next;
}

七、哈希表

1、基本知识

哈希表（Hash table）：哈希表是根据关键码的值而直接进行访问的数据结构。牺牲了空间换取了时间。

其实直白来讲其实数组就是一张哈希表，哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素。一般哈希表都是用来快速判断一个元素是否出现集合里。

哈希函数：将关键码映射为哈希表上的索引
哈希碰撞：多个关键码映射到哈希表上的同一个索引处
拉链法：使用链表存储重复索引的元素
线性探测法：哈希表要大，位置要多，在索引下一个位置放重复的元素

2、常见的三种哈希结构

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

数组
set （集合）
map(映射)

这里数组就没啥可说的了，我们来看一下set。需要include相应的头文件<set> / <unorderer_set> 等

在C++中，set 和 map 分别提供以下三种数据结构，其底层实现以及优劣如下表所示：

在map 是一个key = value 的数据结构，map中，对key是有限制，对value没有限制的。

3、关键码（索引）有限

关键码是小写字符，也就是26个，int hash_list[26] 足以覆盖所有情况。

class Solution {
public:
    bool isAnagram(string s, string t) {
        int record[26] = {0};
        for (int i = 0; i < s.size(); i++) {
            // 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
            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;
    }
};

4、关键码（索引）未知

关键码是数组中的元素，元素的取值范围如果未知，就只能使用哈希数据结构。
这里的思路挺好的，不是分别计算nums1 和nums2 的set，记录一个set即可，下一个数组遍历时使用。

5、哈希法 + 双指针

经典例题：
三数之和
四数之和

八、数组

1、填充数组

其实很多数组填充类的问题，其做法都是先预先给数组扩容带填充后的大小，然后在从后向前进行操作。这么做有两个好处：

不用申请新数组。
从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。

因为提前计算好了要填充的大小，所以不会出现填充数据覆盖了原数组中需保留的数据的情况。

例题1

#include <iostream>
using namespace std;
int main() {
    string s;
    while (cin >> s) {
        int sOldIndex = s.size() - 1;
        int count = 0; // 统计数字的个数
        for (int i = 0; i < s.size(); i++) {
            if (s[i] >= '0' && s[i] <= '9') {
                count++;
            }
        }
        // 扩充字符串s的大小，也就是将每个数字替换成"number"之后的大小
        s.resize(s.size() + count * 5);
        int sNewIndex = s.size() - 1;
        // 从后往前将数字替换为"number"
        while (sOldIndex >= 0) {
            if (s[sOldIndex] >= '0' && s[sOldIndex] <= '9') {
                s[sNewIndex--] = 'r';
                s[sNewIndex--] = 'e';
                s[sNewIndex--] = 'b';
                s[sNewIndex--] = 'm';
                s[sNewIndex--] = 'u';
                s[sNewIndex--] = 'n';
            } else {
                s[sNewIndex--] = s[sOldIndex];
            }
            sOldIndex--;
        }
        cout << s << endl;       
    }
}

九、字符串

1、翻转字符串里的单词

我的思路，取出每个单词入栈，出栈生成一个新的string。

不要使用辅助空间，空间复杂度要求为O(1)：
所以解题思路如下：

移除多余空格
将整个字符串反转
将每个单词反转

//版本一 
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); // 重新设置字符串大小
    }
}

2、右旋字符串

思路：

// 版本一
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
    int n;
    string s;
    cin >> n;
    cin >> s;
    int len = s.size(); //获取长度
    reverse(s.begin(), s.end()); // 整体反转
    reverse(s.begin(), s.begin() + n); // 先反转前一段，长度n
    reverse(s.begin() + n, s.end()); // 再反转后一段
    cout << s << endl;
} 

3、kmp手动实现strstr()

参考：无限十三年up KMP算法原理与实现尝试

①理解kmp

在目标串中查找模式串

暴力（brute force）算法：
当出现字符不匹配时，模式串整体向后移动一位，目标串和模式串的对比指针都回溯到首字符。

目标串length=m，模式串length=n，则bf的时间复杂度为O(m*n)。

优化方向：防止或者减少目标串的指针回溯。

kmp算法中，目标串的对比指针是不回溯的，模式串的对比指针是回溯的，且模式串指针回溯后，两个对比指针前面的字符是匹配的。如何确保“两个对比指针前面的字符是匹配的”——最长公共前后缀，这里的前后缀是指模式串中以及匹配成功的子串的前后缀，例如上图中的“AAAA”。最长公共前后缀有以下三个要求：
从头找：前缀包含头部字符，后缀包含尾部字符
找最长：确保不会遗漏情况，步子要小，如下，步子跨大了。


不能超：前缀不能包含尾字符，后缀不能包含首字符。

有最长公共前后缀后，模式串的对比指针就知道该回溯到那个位置上去了。

②最长公共前后缀

最长公共前后缀，指引模式串的对比指针的回溯，保存在next[] 数组中，next[i] = k， 代表在模式串下标为i 的字符出现不匹配时，回溯指针应该指向下标为 k的字符，且前[0 , k)的字符一定是和目标串匹配的。

因为前缀 和 后缀是相同的，且后缀 已经和目标串匹配上了，相当于把前缀移动到后缀的位置。

上图中，目标串的“ C ” 不匹配模式串的“ A ”，但是模式串的 “ A ”的前面有重复的 “ A ”，所以这些“ A＂肯定是不匹配的，如其一个个"A"的比较，不如直接跳到最前面那个” A “的next的位置。

这里需要一个去重的next数组——nextval数组，优化方法如下：

③next、nextval数组代码

使用递推的方法求解数组，j ，k 都代表模式串的下标，next[j] = k,代表下标j的字符不匹配时，指针回溯到下标为k的位置。next[0] = -1,这是规定的，可以去看参考视频。如果k == -1，说明没有公共前后缀，那么其对比指针直接从头开始对比，即回溯到首字符。这里可以看出，为了保持规则的不变性，next[0] = -1，k=-1，k+1 = 0，直接就是首字符。

void get_next(char* pattern, int len, int* next) {
    int j = 0;
    int k = -1;
    next[0] = -1;
    while (j < len - 1) {
        if (k == -1 || pattern[j] == pattern[k]) {
            k++;
            j++;
            next[j] = k;
        } else {
           k = next[k];
        }
    }
}

void get_nextval(char* pattern, int len, int* nextval) {
    int j = 0;
    int k = -1;
    nextval[0] = -1;
    while (j < len - 1) {
        if (k == -1 || pattern[j] == pattern[k]) {
            k++;
            j++;
            nextval[j] = k;
            if(pattern[j] == pattern[k]){//从j跳到k，但是pattern[j] == pattern[k]
                nextval[j] = nextval[k];
            }
        } else {
           k = nextval[k];
        }
    }
}

④kmp代码

找到返回匹配的首字符下标，反之，返回 -1.

void KMPSearch(char* text, char* pattern) {
    int M = strlen(pattern);
    int N = strlen(text);
    int result = -1;
    int next[M];
    get_next(pattern, M, next);
    int txt_ind = 0, ptn_ind = 0;
    while (txt_ind < N && ptn_ind < M) {
        if (ptn_ind == -1 || pattern[ptn_ind] == text[txt_ind ]) {//已经匹配，or 从头开始匹配
            ptn_ind++;
            txt_ind++;
        }else{
           ptn_ind = next[ptn_ind ];
        }
    }
    if(ptn_ind >= M){//模式串匹配到最后一个字符之后
        result = txt_ind - M;
    }
    return result;    
}

十、栈与队列

匹配消除问题都是栈的强项

1、单调栈

什么时候用单调栈呢？
通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。时间复杂度为O(n)。

c++实现：

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

单调队列，即单调递减或单调递增的队列，其实队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。

K的限制：先加K个数到deque中，后面的每一次push都会提前pop，这样保证了deque中最多只有k个数，push里面的while循环，确保了deque是一个单调队列（单减）.

2、优先队列

可见c++笔记。

头文件： <queue>

#include <queue>
// 默认大顶堆（降序）
priority_queue<int> pq1;  
priority_queue<int, vector<int>, less<int>> pq2;  
// 小顶堆（升序，需指定比较函数）
priority_queue<int, vector<int>, greater<int>> pq2;  
// 自定义类型需重载比较运算符
priority_queue<Node, vector<Node>, CompareNode> pq3;  

less，greater 是内建函数对象。其中Node为自定义结构体，CompareNode为比较仿函数。

对于复杂类型，可通过重载operator< 或 定义仿函数实现：

只能的重载“ < ”，不能重载“ > ”,但是可以通过重载“ < ”，实现大、小顶堆。

struct Task {
    int priority;
    string name;
    // 重载运算符方式
    bool operator<(const Task& t) const { 
        return priority < t.priority; // 大顶堆
        return priority > t.priority; // 小顶堆
    }
};

或使用仿函数：class 和 struct都可以。

struct CompareTask {
    bool operator()(const Task& a, const Task& b) {
        return a.priority < b.priority; // 大顶堆
        return a.priority > b.priority; // 小顶堆
    }
};
priority_queue<Task, vector<Task>, CompareTask> taskQueue;

例题1

小顶堆，因为要的是频率高的元素，故需要删除频率低的元素，因此，用小顶堆

十一、二叉树

递归算法的三个要素：
1、确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么，进而确定递归函数的返回类型。 参数要考虑是传值、传址还是传引用。

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

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

递归函数什么时候需要返回值？什么时候不需要返回值？这里总结如下三点：

如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。
如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。
如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。

1、二叉树-深度优先遍历

前序遍历：

class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) return;
        vec.push_back(cur->val);    // 中
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

那么前序遍历写出来之后，中序和后序遍历就不难理解了，代码如下：

中序遍历：

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);    // 中
}

2、二叉树-广度优先遍历

层序遍历

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

3、二叉树节点的深度与高度

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

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

根节点的高度就是二叉树的最大深度，叶子节点是左右都为空的节点，看清题目要求,如果结束条件有关叶子节点，那么在dfs的时候，需要考虑当前节点是否为空，再决定是否继续递归，当然也可以添加空节点的结束条件，看具体题目。

①最大深度

后序遍历（左右中）求高度，从叶子节点到该节点：

class Solution {
public:
    int getdepth(TreeNode* node) {
        if (node == NULL) return 0;
        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);
    }
};

前序遍历（中左右）求深度，从根节点到叶子节点：

class Solution {
public:
    int ret = 0;
    void dfs(TreeNode* root, int num){
        if(root == nullptr) return;
        if(++num > ret) ret = num;
        dfs(root->right, num);
        dfs(root->left, num);
    }
    int maxDepth(TreeNode* root) {
        dfs(root, 0);
        return ret;
    }
};

class Solution {
public:
    int result;
    void getdepth(TreeNode* node, int depth) {
        result = depth > result ? depth : result; // 中
        if (node->left == NULL && node->right == NULL) return ;// 中
        if (node->left) { // 左
            getdepth(node->left, depth + 1);
        }
        if (node->right) { // 右
            getdepth(node->right, depth + 1);
        }
        return ;
    }
    int maxDepth(TreeNode* root) {
        result = 0;
        if (root == 0) return result;
        getdepth(root, 1);
        return result;
    }
};

②最小深度

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

后序遍历（左右中）求高度，从叶子节点到该节点：

class Solution {
public:
    int getDepth(TreeNode* node) {
        if (node == NULL) return 0;
        int leftDepth = getDepth(node->left);           // 左
        int rightDepth = getDepth(node->right);         // 右
                                                        // 中
        // 当一个左子树为空，右不为空，这时并不是最低点
        if (node->left == NULL && node->right != NULL) { 
            return 1 + rightDepth;
        }   
        // 当一个右子树为空，左不为空，这时并不是最低点
        if (node->left != NULL && node->right == NULL) { 
            return 1 + leftDepth;
        }
        int result = 1 + min(leftDepth, rightDepth);
        return result;
    }

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

前序遍历（中左右）求深度，从根节点到叶子节点：

class Solution {
private:
    int result;
    void getdepth(TreeNode* node, int depth) {
        // 函数递归终止条件
        if (node == nullptr) {
            return;
        }
        // 中，处理逻辑：判断是不是叶子结点
        if (node -> left == nullptr && node->right == nullptr) {
            result = min(result, depth);
        }
        getdepth(node->left, depth + 1);
        getdepth(node->right, depth + 1);
        return ;
    }
public:
    int minDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        result = INT_MAX;
        getdepth(root, 1);
        return result;
    }
};

class Solution {
private:
    int result;
    void getdepth(TreeNode* node, int depth) {
        // 函数递归终止条件
        if (node == nullptr) {
            return;
        }
        depth++;
        // 中，处理逻辑：判断是不是叶子结点
        if (node -> left == nullptr && node->right == nullptr) {
            result = min(result, depth);
        }
        if (node->left) { // 左
            getdepth(node->left, depth);
        }
        if (node->right) { // 右
            getdepth(node->right, depth);
        }
        return ;
    }

public:
    int minDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        result = INT_MAX;
        getdepth(root, 0);
        return result;
    }
};

十二、回溯

回溯是递归的副产品，只要有递归就会有回溯。回溯的本质是穷举，就是暴力查找，穷举所有可能，然后选出我们想要的答案，效率低，虽然可以剪枝，但提升有限, 一般是在for循环中，进入dfs的时候进行判断剪枝。

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

1、回溯模板

回溯法解决的问题都可以抽象为树形结构，回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。

回溯、递归三部曲：

①回溯函数模板返回值以及参数
回溯算法中函数返回值一般为void。回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数，其实参数可以使用全局变量代替，合理考虑就行。

起始位置这个参数要小心，需不需要关心起始位置（同一集合元素不能重复），起始位置能不能重复（同一集合元素可以重复）

②回溯函数终止条件
遍历树形结构一定要有终止条件。所以回溯也有要终止条件，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。

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

模板：如果需要剪枝，还需要添加其他条件判断。

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

for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了.

2、组合问题

例题1

暴力：如果n为100，k为50呢，那就50层for循环。
递归来做层叠嵌套（可以理解是开k层for循环），每一次的递归中嵌套一个for循环，那么递归就可以用于解决多层嵌套循环的问题了。

把组合问题抽象为如下树形结构：

每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。 图中可以发现n相当于树的宽度，k相当于树的深度。

回溯+剪枝：

class Solution {
private:
    vector<vector<int>> result;// 存放符合条件结果的集合
    vector<int> path;// 用来存放符合条件结果
    void backtracking(int n, int k, int startIndex) {//startIndex 就是防止出现重复的组合,调整可选择的范围
        if (path.size() == k) {
            result.push_back(path);
            return;
        }
        //(k - path.size())还需要选择的数目，i + (k - path.size()) - 1 因为从i开始，包括了i，所以需要 -1
        for (int i = startIndex; i + (k - path.size()) - 1 <= n; i++) { // 优化的地方
            path.push_back(i); // 处理节点
            backtracking(n, k, i + 1);
            path.pop_back(); // 回溯，撤销处理的节点
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }
};

3、树枝/层去重

树枝：节点有血缘关系，相互构成父子节点。
树层：同一父节点下的各个子节点。

先排序：

如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，就说明：同层的前一个树枝，使用了candidates[i - 1]，也就是说同一树层使用过candidates[i - 1]。

可以看出在candidates[i] == candidates[i - 1]相同的情况下：
used[i - 1] == true，说明同一树枝candidates[i - 1]使用过。
used[i - 1] == false，说明同一树层candidates[i - 1]使用过。

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) {
        if (sum == target) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
            if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
                continue;
            }
            sum += candidates[i];
            path.push_back(candidates[i]);
            used[i] = true;
            backtracking(candidates, target, sum, i + 1, used); // 这里是i+1，每个数字在每个组合中只能使用一次
            used[i] = false;
            sum -= candidates[i];
            path.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<bool> used(candidates.size(), false);
        path.clear();
        result.clear();
        // 首先把给candidates排序，让其相同的元素都挨在一起。
        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0, 0, used);
        return result;
    }
};

4、分割问题

例题1

本题有分割个数的限制，即正好分割成4块，所以需要有dots进行记录，为了确保字符串的字符全部都参与了分割，所以start必须 >= 字符串的长度，故成功的条件就是 dots >= 4 && start >= s.size

class Solution {
private:
	vector<string> ret;
	vector<string> path;
	bool isOk(const string& s, int start, int end) {
        if (end - start + 1 > 3)return false;
		if (s[start] == '0'&& end-start+1>1) return false;
		int tmp = stoi(s.substr(start, end - start + 1));
		if (tmp <= 255 && tmp >= 0) return true;
		return false;
	}
	void dfs(const string& s, int start, int dots) {
		if (dots >= 4) {
			if (start < s.size()) return;
			string tmp;
			for (string s1 : path) {
				tmp += (s1+'.');
			}
			tmp.pop_back();
			ret.push_back(tmp);
			return;
		}
		for (int i = start; i < s.size(); i++) {
			if (isOk(s, start, i)) {
				path.push_back(s.substr(start, i - start + 1));
				dfs(s, i + 1, dots+1);
				path.pop_back();
			}
			else {
				break;
			}
		}
	}
public:
	vector<string> restoreIpAddresses(string s) {
		dfs(s, 0, 0);
		return ret;
	}
};

5、子集问题

组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！

例题1

需要对每一个节点进行保存，且不能有重复的子集。需要进行排序，树层去重。

result.push_back(path); 放在递归开始是为了包含空集。

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int startIndex, vector<bool>& used) {
        result.push_back(path);
        for (int i = startIndex; i < nums.size(); i++) {
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            path.push_back(nums[i]);
            used[i] = true;
            backtracking(nums, i + 1, used);
            used[i] = false;
            path.pop_back();
        }
    }

public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        result.clear();
        path.clear();
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end()); // 去重需要排序
        backtracking(nums, 0, used);
        return result;
    }
};

6、无序树层去重

树层去重是有序的情况下，使用同一个used数组进行标记，回溯时需要复原。
无序树层去重是无序数组，每一个递归都需要有一个used数组（unordered_set）进行标记，单独记录该层的重复情况，无需复原。

例题1

同一父节点下的同层上使用过的元素就不能再使用了。

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int startIndex) {
        if (path.size() > 1) {
            result.push_back(path);
        }
        int used[201] = {0}; // 这里使用数组来进行去重操作，题目说数值范围[-100, 100]
        for (int i = startIndex; i < nums.size(); i++) {
            if ((!path.empty() && nums[i] < path.back())
                    || used[nums[i] + 100] == 1) {
                    continue;
            }
            used[nums[i] + 100] = 1; // 记录这个元素在本层用过了，本层后面不能再用了，回溯时，无需复原
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        result.clear();
        path.clear();
        backtracking(nums, 0);
        return result;
    }
};

7、排列问题

每层都是从0开始搜索而不是startIndex,从头开始选，每一个递归都选择了一个元素，故不存在遍历完数组还有元素未选择的情况。
需要used数组记录path里都放了哪些元素了，已经使用过的元素不能重复使用。

涉及到去重，有树枝、层去重，有树层无、有序去重。

树层有序去重：used数组有两个作用：①used[i]元素不能重复使用；②used[i-1]用于树层去重。

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking (vector<int>& nums, vector<bool>& used) {
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            if (used[i] == false) {
                used[i] = true;
                path.push_back(nums[i]);
                backtracking(nums, used);
                path.pop_back();
                used[i] = false;
            }
        }
    }
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        result.clear();
        path.clear();
        sort(nums.begin(), nums.end()); // 排序
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};

树层无序去重：

class Solution {
    vector<vector<int>> ret;
    vector<int> path;
    void dfs(vector<int>& nums, vector<int>& used){
        if(path.size() == nums.size()){
            ret.push_back(path);
            return;
        }
        int tmp[21] = {0};//同一父节点的子节点不能重复使用
        for(int i = 0; i < nums.size(); i++){
            if(used[i] == 1) continue;
            if(tmp[nums[i]+10] == 1) continue;
            tmp[nums[i]+10] = 1;//回溯时，无需复原
            used[i] = 1;
            path.push_back(nums[i]);
            dfs(nums, used);
            path.pop_back();
            used[i] = 0;
        }
    }
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<int> used(nums.size(), 0);
        dfs(nums, used);
        return ret;
    }
};

8、重新安排行程

会超时，需要剪枝

class Solution {
private:
// unordered_map<出发机场, map<到达机场, 航班次数>> targets
unordered_map<string, map<string, int>> targets;
bool backtracking(int ticketNum, vector<string>& result) {
    if (result.size() == ticketNum + 1) {
        return true;
    }
    for (pair<const string, int>& target : targets[result[result.size() - 1]]) {
        if (target.second > 0 ) { // 记录到达机场是否飞过了
            result.push_back(target.first);
            target.second--;
            if (backtracking(ticketNum, result)) return true;
            result.pop_back();
            target.second++;
        }
    }
    return false;
}
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        targets.clear();
        vector<string> result;
        for (const vector<string>& vec : tickets) {
            targets[vec[0]][vec[1]]++; // 记录映射关系
        }
        result.push_back("JFK"); // 起始机场
        backtracking(tickets.size(), result);
        return result;
    }
};

映射关系有俩种选择：
unordered_map<string, multiset> targets：unordered_map<出发机场, 到达机场的集合> targets
unordered_map<string, map<string, int>> targets：unordered_map<出发机场, map<到达机场, 航班次数>> targets

选择了后者，因为如果使用unordered_map<string, multiset<string>> targets 遍历multiset的时候，不能删除元素，一旦删除元素，迭代器就失效了。且必须遍历，如果直接使用字符小的那个路径，无法确保最终能够遍历完所有路径，所有需要有回溯的过程。

初始化：不用find，targets[vec[0]] 代表指定string下的map<string, int>，targets[vec[0]][vec[1]]代表指定string下的map指定string下的int。

//auto& vec:tickets 
for (const vector<string>& vec : tickets) {
    targets[vec[0]][vec[1]]++; // 记录映射关系
}

递归终止条件：所有的机票都使用完，一个机票对应一个机场，所有机票用完时，跑了（机票数+1）个机场

if (result.size() == ticketNum + 1) {
    return true;
}

需要返回值，是因为只需要找到一条可以遍历完所有机票且字母最小的路径即可，找到即结束。

9、N皇后

std::vector<std::string> chessboard(n, std::string(n, '.')); 单个棋盘提前初始化，不用一行行的push_back，且vector<string> chessboard 可以像二维数组那样进行赋值，chessboard[ x ][ y ].

class Solution {
private:
vector<vector<string>> result;
// n 为输入的棋盘大小
// row 是当前递归到棋盘的第几行了
void backtracking(int n, int row, vector<string>& chessboard) {
    if (row == n) {
        result.push_back(chessboard);
        return;
    }
    for (int col = 0; col < n; col++) {
        if (isValid(row, col, chessboard, n)) { // 验证合法就可以放
            chessboard[row][col] = 'Q'; // 放置皇后
            backtracking(n, row + 1, chessboard);
            chessboard[row][col] = '.'; // 回溯，撤销皇后
        }
    }
}
bool isValid(int row, int col, vector<string>& chessboard, int n) {
    // 检查列
    for (int i = 0; i < row; i++) { // 这是一个剪枝
        if (chessboard[i][col] == 'Q') {
            return false;
        }
    }
    // 检查 45度角是否有皇后
    for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    // 检查 135度角是否有皇后
    for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    return true;
}
public:
    vector<vector<string>> solveNQueens(int n) {
        result.clear();
        std::vector<std::string> chessboard(n, std::string(n, '.'));
        backtracking(n, 0, chessboard);
        return result;
    }
};

十三、贪心

贪心算法是一种思路简单、实现较为容易、效率较高的算法。它的核心思想是：每一步都选择当前局部最优解，并且期望通过不断的选择来达到全局最优解。

贪心算法主要分为两个部分：选择策略和优化问题。选择策略指的是，每一步如何从多个选项中选择一个局部最优解，而优化问题指的是，当已经选择了一个局部最优解后，如何把问题规模缩小，以便下一步仍然能够找到局部最优解。

1、摆动序列

思路1：根据前一次的flag（前面的差值diff），和当前的差值diff，判断是否构成一个“V”形：

class Solution {
public:
	int wiggleMaxLength(vector<int>& nums) {
		if (nums.size() < 2)return nums.size();
		int ret = 0;
		int diff = nums[1] - nums[0];
		int flag = 0;
		if (diff < 0)ret++;//flag = 0,下坡，能够成为‘V’的一部分。
		if (diff > 0) {//flag = 1，上坡。
			flag = 1;
			ret++;
		}
		else if(diff == 0) {//flag = -1,平坡，不能构成“V”。
			flag = -1;
		}
		for (int i = 2; i < nums.size(); i++) {
			diff = nums[i] - nums[i - 1];
			if (flag == 0 && diff > 0) {//前面是上坡，当前是下坡，
				flag = 1;
				ret++;
			}
			else if (flag == 1 && diff < 0) {//前面是上坡，当前是下坡
				ret++;
				flag = 0;
			}else if(flag == -1){//前面是平坡
				if (diff > 0) flag = 1;
				else if (diff < 0) flag = 0;
				else if (diff == 0)continue;
				ret++;
			}
		}
		return ++ret;

	}
};

思路2：找凹凸点，每个凹凸点都是一个“V”形。

十四、动态规划

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

对于动态规划五步曲：
1、确定dp数组（dp table）以及下标的含义
2、确定递推公式
3、dp数组如何初始化
4、确定遍历顺序
5、举例推导dp数组