a、凡是用到递归，就画递归树

具体来讲就是分而治之，把一个大问题分成很多相同或相似的小问题，小问题再分，直到无法再分，所有小问题的结果合起来就是最终结果
常见的有排序中的快速排序和归并排序，分治经常和递归一起提及
a、该问题缩小到一定规模就可以解决
b、该问题可以分成若干小问题
c、该问题若干小问题的解可以合并成这个问题的答案
d、该问题分出来的若干小问题都是独立的
若满足a、b，却不满足c，可以考虑贪心算法或者动态规划算法
若不满足d方法，可以考虑一下动态规划算法（这样效率更高）

---

---

这个题目老实说，很难，主要是题目读不懂的难，在题目读不懂的情况下我们可以从示例入手

---

// 说明不是有效括号，入栈 // 计算最后一个括号和留下的最后一个不是括号的

双指针问题主要有两方面，分为快慢指针和左右指针
快慢指针主要针对链表，如链表是否有环
左右指针主要针对数组或字符串，如二分查找

主要是设置两个指针，快指针比满指针步长多1，如果没有环，快指针会遇到null，如果有环，快指针和满指针会相遇

---

b、链表环的起始位置问题
已知链表有环，求环的起始位置
假设在某点相遇，此时快指针走了2k步，慢指针走了k步
若把慢指针或快指针中的一个设为头指针，然后快慢指针一起前进，最后相遇的点就是环的初始位置，因为他们都走了k-m

---

c、寻找无环链表的中步
可以通过让快指针走两步，慢指针走一步，当快指针走到终点的时候，满指针就走到中间了

---

d、寻找链表倒数第k个
这个的思路是让快指针先走k步
然后让快慢指针都同时走1步，当快指针到null后，满指针指向的就是第k个

---

这道题其实用快慢指针是特别方便的，而看出它需要使用快慢指针也是特别重要的，根据这道题，我们可以总结出什么情况下需要使用快慢指针
①当值或其他什么可以作为下标的时候，且永远不会回到0号下标（因为我们知道快慢指针通常用来解决有环问题，而很多时候不会明确告诉你有环，那么什么时候有环呢？只要有重复）
②我们把某个重复的值就作为环开始的地方，需要求这个地方就用快慢指针
③快慢指针不一定只适合于链表，数组等顺序结构也是可以用的

---

这一道题最主要的是要注意慢指针在遇到重复元素后不移动，而快会诊要移动

除此之外，这道题也可以使用循环

---

---

// 因为题目要求索引从1开始

---

---

说白了就是维护一个窗口，然后不断移动窗口边界，最后取出窗口里的数据

先分析一下这道题，首先，他只是要找T中所有字母，也就是说T=‘ABC’，S=‘BAC’这种顺序不同的也可以，不要求顺序，只要有那个字母就OK
同理，如果T=‘AABC’，还是找有两个A，一个B，一个C的串
而且因为要求的是子串，所以找到的这几个字母一定是连续的
具体原理就是，先移动右指针，直到找到一个能包含所有需要字符的串（右边的最后一个一定是需要的字符）
然后移动左指针，看到哪一步就不能再动了（其实就是移动到第一个能匹配上的就不能动了）
但是又因为有可能在右指针后面还有能匹配上的，而且能组成最小匹配子串，所以移动右指针这个东西应当是外层循环，终止条件是到达s字符串末尾
另外这是左开右闭即 [left, right) 的，所以需要把最开始的那一个放进去

// start是最小覆盖子串开始的下标，valid是指满足need条件的字符个数 // len指的是最小覆盖子串的长度 // 窗口数据的一系列更新 // 因为这个其实是左开右闭，所以最开始窗口里什么都没有 // 如果窗口里有需要的就更新valid // 看窗口是否要通过移动左边的指针来收缩窗口 // 如果窗口大小跟要求的t的长度相等就得收缩 // 只要能找到更小的子串个数，就更新start和len // 记录一下将要移出窗口的值 // 移动左指针，看能不能找到小的 // 看一下之前移出的是不是也能匹配上 // 如果能匹配上，就把之前放到window里的减去一个

---

---

c、找出所有字母异位词

---

// 看拓宽右边的同时左边是否要收缩

---

首先，单调栈是一个特别的数据结构，说白了也是栈，只不过入栈的数据都是有顺序的（升序或降序）
这里主要使用单调栈来解决环形数组

a、求距离最近的大数/小数
问：给一个数组，返回一个等长的数组，返回数组每个值代表比原数组这个下标元素值a更大的值b，且b的下标要大于a的下标，若没有则该元素返回-1

就相当于排队，第一高的把后面的挡到了，就不需要管后面矮的了
从后往前入栈，只要倒数第n+1个比倒数第n个高，把倒数第n个及n-1，n-2之类的出栈，倒数第n+1进栈

// 把放进栈里小于前面数的都清掉，毕竟就算再要更前面的数时 // 前面已经有大的了，也不会看后面的

虽然我这里用了一个 for 循环和一个 while 循环，但是其实实际上一个数也顶多入栈一次，出栈一次，也就是说时间复杂度不为O(n2)，而是O(n)

给你一个数组 T = [73, 74, 75, 71, 69, 72, 76, 73]，这个数组存放的是近几天的天气气温。返回一个数组，计算：对于每一天，你还要至少等多少天才能等到一个更暖和的气温；如果等不到那一天，填 0 。

---

同样是求最近距离的，依旧给一个数组[2, 1, 2, 4, 3]，但是因为首尾相连，所以结果为[4,2,4,-1,4]
首先明确一下，计算机是线性结构，没有真正意义上的环形数组，一般情况下的环形数组，要实现就是通过 % 取模得到的

我们看一下这道题，如果给的是一个环形数组，要求结果，依旧是使用比身高，如图
这里解决方法其实有两种，第一个是把数组再复制一次得到一个新数组，新数组依旧用原来的方法，最后得到的结果截取一半使用即可

这里的话采用的是循环数组的特性（也就是%取模来做）

// 假装把这个数组复制了一份

---

---

---

// 这里是假设该节点有左节点，则该节点为根节点，应该先遍历该节点的右节点 // 否则就代表这个节点之前已经遍历了右节点，直接把这个根节点拿到即可

---

然后我们来总结一下关于树的遍历模板（非迭代方法）
首先树的三种遍历其实都是DFS，一般情况下我们都知道DFS经常和回溯在一起，且DFS经常是递归实现的，所以这里用递归肯定很简单
而使用迭代其实掌握到模板也很简单
DFS使用的主要的数据结构就是栈（因为先进后出），来记录走过的路

// 定义一个栈，储存之前走过的路 // 要继续得到结果的条件，肯定是该节点不为空，或者当前栈中还有东西没遍历完 // 另外，无论是先序、中序还是后序这个条件都是相同的 // 这个条件是什么时候应该入栈（存储过往路径） // 无论先序、中序、后序都是这个条件 // 什么时候入栈，什么时候移动root // 入栈的是什么，自身（中序和后序）还是右边（先序） // 以及怎么移动，向左（先序和中序）还是向右（后序其实是左右判断） // 把之前储存的拿出来 // 是要继续往右吗（中序和后序），有条件吗（后序有条件），条件是什么

---

需要知道当前是哪儿一层的

// 重点，这是能够得到哪儿一层的

---

e、通过中序遍历和后序遍历找一棵树
首先后序遍历的最后一个元素一定是根，而在中序遍历中这个元素的左边是左子树，右边是右子树，再放到后序遍历中通过个数找到左子树和右子树，再求最后一个是根，这样循环

---

f、从前序与中序遍历序列构造二叉树
前面讲了后序和中序，这个前序和中序其实也差不多，只是根出现的位置问题，所以直接上代码

---

g、填充每个节点的下一个右侧节点指针
这道题的巧妙之处在于利用了完美二叉树，而且让递归函数的参数不是一个

---

h、填充每个节点的下一个右侧节点指针 II
然后进阶版，非完美二叉树
不多说，其实就是完美二叉树多了几种判断情况，具体见代码吧

---

i、二叉树的最近公共祖先
其实遇到二叉树，就要先思考，使用哪种遍历，我们这里是找公共祖先的，所以很自然的能想到是从底向上，而从底向上的遍历最显著的就是后序遍历（先序遍历是自顶向下），确认了使用后序后，我们这里采用递归，就把后序遍历改写一下就可以了

---

j、二叉树的序列化和反序列化

这一道题其实最开始应该首先是想到object的，但是object是无序的，同理，set也是无序的，所以我们可以自然而然地想到map，在js中map是根据插入顺序来的，这里跟java不同（java的map无序，hashMap根据hashcode排序跟object差不多）

map和set的共同点和区别

1、map是根据插入顺序来排序的（FIFO），而set无序
2、map是键值对，set只有值

---

然后我们再来讲讲 页面置换算法（这东西可以在操作系统里看到）
页面置换算法：当要访问某页面，但是内存不够时，就会将内存中的某一页面替换成新的页面，计算到底是哪儿个页面被置换出去的算法就叫做页面置换算法
如果算法不够好，有可能刚换出去的页面又要被换进来，这种情况叫做抖动（把时间都浪费在置换页面上了）
这里主要介绍4种页面置换算法
相当于看一下现在放在页面区域的页码哪个越靠后或者没有在后面被使用的就置换出去
这个就相当于队列，先进先出，没有考虑过之后是否使用这种，所以这也是最坏的置换方法

③LRU置换算法（又称最久未被使用的页面置换方法）
望文生义，把储存的页面中最少被使用的给置换出去
但其实这个的实现方法是有一个栈，然后把使用了的从栈的某个位置拿出，放到栈底，而如果需要置换的时候直接从栈顶拿就行
④LFU页面置换算法（最少使用）
给每个页面计数，如果使用的次数少就被置换出去

// 为什么用map而不用object，map有序，按照插入的顺序

---

首先这里的子数组，就其实类似于子串，毕竟子串和子数组都是紧挨着的，而子序列是不需要紧挨的

// res[i]表示最后%k的值为i的子数组个数 // 表示能被整除的总共的次数 // 为什么这里又是1呢，毕竟要的是子数组，子数组里不能为空嘛 // 所以把最开始的那个去掉 // 这里要考虑如果有负会怎么样，因为是mod后依旧有负数，所以加一个K就能变成正的 // 不能用负数，毕竟没有负数的下标

---

看到这个格式统一的字符串，很容易就想到了正则表达式

代码放完，我们来重温一下正则表达式
首先，正则表达式对象是 RegExp，我们在本题中有了子匹配，而子匹配就是存在 RegExp 中的以 $1、$2 等的属性
这里有个很重要的一点，那就是子匹配的 $1、$2会被覆盖！ 所以我们的正则匹配里不能写成全局的（也就是 g）
以上为根据这道题延伸出来的正则
接下来系统地说一下正则
以上叫做匹配元字符，除了这个还有匹配修饰符，如下
我们可以看出如果字符串中有**[]、()、|、-**这些，就必须加斜杠（\）进行转义
相当于构造函数的斜杠是字面量的两倍

如果只有元字符，没有量词，那么那个元字符代表的必须出现且只能出现一次，而加上量词后出现次数由量词决定

除了以上的，还有一些特殊的字符如

然后我们再来看看使用正则表达式的方法（都是 RegExp.prototype 上的）
而字符串的方法主要是两个，search和replace

---

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。
先谈谈这道题的基本思路，首先我们要求面积，那么就可以很自然的想到公式面积=宽*高，而在这里面高是最好得到的，就是heights[i]，而宽的话要求到就需要一点技巧
因为我们最开始是不知道要怎么求到宽的，所以最先就想到暴力解法，如图
然后我们就可以找到规律，如果后面的那根柱子比当前的高，那么宽度就不能向后继续延伸，如果前面某根柱子比当前的高，宽度也不能继续向前延伸，也就是如下所示
我们要找左边一个什么什么怎么怎么样，右边什么什么怎么怎么样，很自然就能想到用栈（这里可以回忆一下之前求括号那个题，就跟求括号一样，后面的结果会引起前面结果计算完成，也可能要等到很后面的结果才能使前面能计算到结果），所以用栈
好了，接下来我们想想栈的条件，我们可以很清楚地发现当我们拿到某个heights[i]且当这个heights[i]比heigths[i - 1]小时，它是能决定前面是已经得到后面的边界了，这样我们就可以推出，放在栈里的应该是比后一个小的，而如果每一个都比后一个小，那么这个栈应当是单调递增栈
单调递增栈出来了，现在就应该考虑进栈的元素是什么，因为我们要的是宽度，宽度与下标有关，所以下标进栈
其他具体的我们从代码上来看

// 为什么要在头尾都各加一根长度为0的柱子 // 我们这里想想，我们是什么时候会进行计算max？ // 当后面的柱子比我们放在栈顶的柱子低的时候就要计算 // 那么如果我们不在尾巴上添加一根为0的柱子（毕竟没有为负的），怎么才能计算到最后一根柱子的max呢 // 毕竟这里的max其实是每个柱子的max最后取的最大值 // 至于在头加一个0，是为了方便，这样下标就表示是第几根柱子 // 只有当新判断的下标比栈顶高时才进行入栈和计算面积操作 // 一般判断这种的就得先看一下栈是否为空 // 我们每次在最后都会把i给push到栈顶，就相当于是下一轮的i-1 // 所以如果是第一次的话其实这个就是栈顶，直接写heigths[i - 1]也是可以的 // 一直比较不能作为终止条件 // 毕竟while的条件是要后面比栈顶矮 // 毕竟要求的面积是前一个柱子的

关于这个的时间复杂度，感觉上可能跟暴力解法差不多，都是O(n2)的样子，但实际上不是，毕竟进栈和出栈都只有一次，所以时间复杂度应该是O(n)

---

首先，镜像对称就相当于人的左手=人的右手，也就是说左节点的左孩子=右节点的右孩子，左节点的右孩子=右节点的左孩子
另外，我们要明确，我们比较的时候是从上往下比，如果父节点都不同，那就没必要比较子节点
我们这里先使用递归，所以要找到终止条件，条件很好找，因为我们比较的是左右节点的左右孩子，传进去的参数就是两个节点（两个孩子），所以只要这两个节点都为空，则正确，若两个节点只有一个是空，则错误（不对称）

我们再来思考一下迭代的写法，首先递归转迭代一般都需要一个东西存储之前递归的入参，这里我们因为是要从上往下比较，所以是先进先出，很自然地就能想到用队列，然后使用循环并写出条件（如果在递归中中返回true的，这里就应该是continue，毕竟不能只因为一个条件正确就认为这个结果正确，但是false不一样，有一个是错的，结果必定是错的）

---

我再做第9的时候发现自己使用递归还是有点懵逼，这里总结一下套路
②找入参和具体一次的操作
③找返回给上一次递归的值

我们来看一下这道题，首先我们因为看到树其实很自然就能想到要用递归或者迭代（毕竟树可以拆分成多个子树，每个子树做的操作其实都差不多）
然后我们再看一下这道题的三要素：
①终止条件：这道题要求最大深度很显然是要遍历整棵树，而遍历终止的条件就是该节点为空，所以我们的终止条件就找到了，此时的深度就是0
②入参及其操作：我们知道了终止条件，而且也说明了跟每个节点有关，所以我们的入参就是每个节点
每次要做的操作就是上一层的层数+1，就能得到当前的深度
那么这样就有一个问题，我们怎么拿到上一层的深度，很自然地就能想到放到入参里，当然我们也可以想到因为我们有返回值，返回的就是深度，所以直接用返回值+1就ok
所以，最后我们的入参是节点
要做的操作就是深度+1和再次调用函数拿左右节点
③要返回些什么，首先，我们要求的是最大深度，所以我们应该返回的就是当前的深度，然后让上一层通过Math.max来比较即可

稍微进阶一下，求N叉树的深度，这个其实就相当于把比较条件变了一下，然后加个循环

---

b、两两交换链表中的结点
这一道题我最初是想用快慢指针来做的，结果发现因为是原地交换，有些就会出问题（主要是我菜）
所以这里后来看了下题解，写出了递归的思路
首先，我们依旧来想想为什么要用递归，其实这个分解开来看，就是多个两两交换，而且步骤是重复的，所以很自然能想到递归
然后我们想想什么地方需要递归，什么地方需要我们自己做操作
整个链表可以分为三个部分，目前需要交换的头的部分，交换的后面那个部分，需要递归重复交换的部分
至于为什么没要把之前做过操作的也算进一部分，是因为都已经做过操作了，之后不会做操作，放进来也没啥用
红箭头其实就是我们递归函数的入参，它会不断向后面移动
至于什么时候终止呢？如果红箭头，或者粉箭头为空了，自然就不需要进行递归了
为什么选红箭头和粉箭头为终止条件，而不是用绿箭头呢？因为我们交换的就是红箭头和粉箭头，也就是说递归的终止条件是自己进行操作的部分的条件判断
然后我们再来看一下返回什么，之前有说到入参是不断向后移动的红箭头，那么就相当于是当前的粉色箭头，而因为终止条件也是需要返回值的，那个时候要么自己是空的，要么自己的下一个是空的，所以返回入参（为什么不直接返回null呢，因为我们的入参是红箭头，但我们可能后箭头有值而粉箭头没值）

---

这一道题其实是求二叉树深度的变种，因为我们要判断是否为二叉平衡树，只要左子树是平衡树，右子树也是平衡树且左右子树的深度的绝对值不大于1即可
从这个定义中可以看出，主要要求的是两个东西，所以按常理，我们的返回值也应当是两个（如果只有一个，那么因为是递归，就无法能够进行下一步操作）
然后要明确一点，返回值≠入参，一般情况下二叉树的入参都是节点，可能还会增加些其他的东西，如深度之类的，这里我我们的返回值是{深度，是否为平衡树}，那就没必要让入参也是深度了，所以决定入参就是节点
要做的事情其实就一个，判断左右两边是否为平衡树，有一个不是就返回false，并把深度也带上，如果两边深度的绝对值大于1，也返回深度和false，其他情况就说明暂且该子树为平衡树，返回深度和true
这里有一个难点，那就是深度怎么求？
我们要判断是否为平衡树，应当是自底向上的，但我们递归的顺序是自顶向下的，所以肯定会浪费很多空间，但我们求深度，肯定是自底向上的，毕竟我们没办法在根节点就拿到深度，而左右子树的深度又可能是不一样的，所以应当用Math.max来比较一下
但是实际上，这个的求深度就是二叉树求最大深度（见a或如下）

// 只考虑终止情况下的深度

---

这道题其实有点坑爹，乍一看，感觉就像是求最大深度，但是有个示例[1, 2]，却一直过不了，这是因为我们在最大深度时只判断了是否为空，而没有判断过该节点是否为叶子节点（毕竟求最大深度用的是Math.max，只要它的左节点或右节点为null，用max一定能准确找到最大的那个叶子节点）
所以要判断，如果左边或者右边没有节点了，那么它的深度应当是左边+右边+1（这里是一个很巧妙的公式，毕竟如果一个个判断是左边为空，所以用右边+1，或者是右边为空，用左边+1，都太麻烦了）
这道题其实主要考察终止条件！！

---

这道题的备注甚骚哈哈哈，这道题就跟镜像差不多，不多讲了，直接上代码

---

---

这道题，主要告诉我们其实很多题是真的只能用暴力解法+递归，这已经算是最优解了，所以完全可以先想暴力解法

---

|| 短路或，如果 a || b 中 a 是能转化出来等于 true 的就返回 a（短路）
短路，也就是说不执行后面的，使用 || 或者 && 都是直接输出值而不会转化成boolean类型
如果n === 0那么就不会进行后面的递归了

---

这一道题其实如果不考虑时间复杂度和空间复杂度，可以用出栈入栈的暴力解法来（时间复杂度O(n2)）
最简单的方法，就是循环遍历，时间为O(n)，用两个常数存储
主要思想就是要求数组乘积，其实就是左边*右边，然后找规律
当然拓宽一下思想就是前缀积 * 后缀积

---

这里其实就只是想说明一下，不是所有题都有算法的，所以我们很多都只有用暴力破解，如果第一反应没想到简便方法，那么就用暴力破解，管它时间复杂度和空间复杂度之类的

就像这一道题，乍一看，根本看不出什么简便方法（我顶多想到可能用用栈这种东西），所以就直接暴力破呗，不要怕

---

之前做题从来没有关注过提示，这次我们从提示入手，首先，提示说最多有1000个数，意思就是时间复杂度可以为O(n2)，然后我们再来思考一下这道题，这道题，初看确实没啥想法，但一想暴力解法肯定不在这个时间复杂度里吧，排除暴力解法，我们再想想
题中有提到，可能会有两个相邻元素交换顺序，或是多个元素倒序，可能看多个元素看不出什么东西来，但是相邻元素交换顺序不就是冒泡吗？？所以我们就试试将两个数组都先排序，然后再比较，一看结果，正确的，这就证明了排序可行

---

b、检查字符串是否包含所有长度为K的二进制子串
首先理解下题意，题意用白话来说就是，通过k来构造k位数的01这种字符串，然后去s中找，但是如果先把所有字符串找到，然后在s中循环找就很麻烦，所以直接通过在s中查找所有类型的字符串，然后看总个数是否大于等于2**k即可

---

做这道题的时候隐隐约约觉着要用排序+双指针，但是具体怎么搞却没有思路。但是其实这就是一个快排类型的题，难点其实在于不能重复，这个问题，不多说，直接上代码

---

d、转变数组后最接近目标值的数组和
这道题我已经算是很接近答案了，只不过有两个问题，而最终没有解决主要是两个问题没弄清楚，第一个是数组和最接近这个的意思就是要比较Math.floor()和Math.ceil()哪个值更接近平均值，第二个是每次循环都要去找剩下数组的平均值，而不是先判断target和当前的arr[i]的大小后再去找平均值
想清楚这两点，其实这道题就很简单

---

这道题其实只要别被这么多字难住，然后把某一门课和能达到的课用一个map来存储，里面的key就是那门先修课，value就是能到达的所有课，这样就能判断了

---

这道题其实从动态规划的角度上不难，只要想到了动态规划就可以，难的是条件的判断，以及最开始所有的初始值为-1这一个点，我之前使用0，但是因为0会出现在grid数组里，所以一直报错，最后才发现是初始值的问题

// 设置为-1是重点 // dp[i][j][k]表示当走到第i行，第一个机器人在j，第二个机器人在k的时候最大的樱桃数目 // 循环找上一层最大的（从左上，上，右上角三个地方中选最大） // 判断值为-1是重点（这代表着这一步不能走）

---

十进制转换其他进制模板（转更高进制的，低进制就少个判断）：

 // bit代表需要转换的进制
 // 这是针对高进制，低进制不需要，毕竟不会有字母
 // 重点，先得到的会放后面

---

h、从先序遍历还原二叉树
这道题首先因为是先序遍历，所以是根节点 -> 左孩子 -> 右孩子
这其实就是个找父亲的过程，使用深度的单调递增栈，如果孩子深度（即-个数）>栈顶，就入栈，否则出栈，一直循环到找到父亲

// 先构造树，再入栈（所有都要入栈）

---

这道题的正规做法应该是使用图的DFS或者BFS，奈何我不会（之后补），所以这里采用了维持一个数组，遍历各路径（这里遍历的路径里存在的点要先排序，毕竟遍历的时候是连续的，所以应该先对所有路径排序，保证后面出现的点一定是比前面出现的点大的）

---

DFS和邻接链表的写法
这里要明确，因为DFS是自顶向下（其实BFS也是自顶向下），所以如果发现能从start到end，就说明要重新规划了
而因为这里最开始是有向图，为了知道什么是能到的，什么是不能到的，就把它弄成无向图，但是要设置一下什么是自己添加的（如果不做成无向图就没办法让这棵树连通，就更没办法往下遍历了）
然后因为图有两条边，但是不能经过同一顶点两次，所以拿个数组存一下，然后再用栈存一下顶点

// 这个的意思是0能到1，也能到2 // 存1是有讲究的，因为是DFS，自顶向下，所以如果能找到start对应的end就说明是要重新规划的，存1方便到时候加 // 因为如果没出现start->end就一定是end->start，如果遍历到了，因为是自底向上，所以不用重新规划 // 保存经过了的节点 // 如果已经走过该节点，就继续循环

---

这一道题和之前的15题差不多也是三数之和，也是使用排序+双指针

---

字符串！！，动态规划！！！，跟回文数其实差不多，知道动态规划后基本上5分钟搞定，虽然我这没想出来是动态规划

---

---

这个解法是很容易就能想到的，主要就是考虑情况（面向测试用例编程），过滤的时间复杂度是O（N），里面找最小也是O（N），空间复杂度就是O（1）

---

这个其实我也想到了，就是结合下标和值，但不知道咋的就以为时间复杂度是O（n2），但实际上如果放对位置或者是负数或0，就不会移动位置，所以是O（n2）
而且我们要求出的最小正数是[1, len + 1]里的

---

---

很显然是一道能够通过数学方程做出来的题

---

先明确一下，单独的一个.是可以存在的，不依靠其他的进行判断
但是*要么与前面的某一位一起跟某几个相同的字符匹配，要么跟某一个相同的字符匹配，要么跟后面的空气进行匹配
不匹配和跟跟空气匹配其实结果是一样的，但是我们这里分的条件是匹配和不匹配，所以要分开写
因为*依靠前一位，所以初始化的时候就应该让是*的那个结果和倒数第二位的相同

// 这个初始化相当重点 // 如果上一位是.，或者这一位能匹配上 // 那么结果就跟上一次的相同 // 否则如果是*就再继续分 // 如果是其他乱七糟八的还匹配不上，铁定就是false（也就是初始值） // *因为不能单独出现，必须和其他字母一起搭配 // 这里不匹配的情况 // 这里是匹配的情况 // 所以这里分3种情况，以下任意一种成立就可以 // 3、能匹配多个，就说明s少一位p也能匹配上，dp[i - 1][j]

---

一道相同类型的题，这道题里的*可以单独存在

---

b、二叉树的最大路径和
这道题其实说难也不难，主要就是看到二叉想遍历，最开始我是在纠结使用中序还是后序（毕竟根节点可能不要，如果用先序就会直接放进去），但其实这道题用递归是最方便的（迭代还太麻烦，我也想不出方法）
以这三个节点为例，就可能是A，AB，AC，ABC
而这里面AB和AC可以合并，因为我们必然会去分开求B、C各自的最大值（毕竟还有ABC）
而且这里很明显可以看出，无论如何A的值都是需要的，然后我们就可以开始递归了（需要递归的点其实就是B和C，因为B和C可以继续往下分，而且B和C可以通过A的left和A的right得到）

// 因为必须包含一个节点，所以初始化的值是根节点的值而不是0 // 这里其实分三种情况，只需要左边，只需要右边，左右都要 // 用左边和0比较，如果0大就说明不要左边 // 用右边和0比较，如果0大就说明不要右边 // 用最大值和左右都要比较 // 因为至少包含一个节点，那么这个节点一定是我每次遍历到的那个节点 // 返回的就是左边或者右边中的最大值

---

c、二叉搜索树的后序遍历
这道题解法其实用的就是之前的那道h、二叉树的先序遍历里的单调栈
这里说明一下，为什么要用单调栈，二叉搜索树是一种很明显的有序的东西，单调栈里最主要的就是单调俩字，所以单调栈天生跟排序就很有关系
这道题其实也是找父亲，因为最开始我们假设了一个无穷大的根节点，所以来的节点一定是左边的，比这个小的

// 相当于给树再加一个父亲，现在的树时无穷大的数的左子树 // 记录下上一个父亲的结果 // 如果小于栈顶元素，说明右边没东西了，就是往左子树里加东西 // 所以把右边的都从stack里去掉

---

这道题就一道二元一次方程，通过暴力破就行，难点其实在于找边界，就面向测试用例

// 其实这道题就是二元一次方程 // 我们假设a的字母长度（通过遍历） // 然后再把它拼起来与原pattern比较即可 // flag来表示开头第一个是否为a // 如果在value为空的情况下，a和b同时存在，又因为a的字符不能等于b的字符 // 如果只有a，或者只有b // 遍历a的字母长度 // a可以为空,a也可以为满

---

简介： 如果斐波那契数小于8位的就输出这个数，大于8位的就输出前四位，以及后四位

• 通过打表可以发现到39位为止都不超过8位数，当n>39时再分别求前四位和后四位 F(n)的前四位（整数部分只是贡献结果末尾的0罢了）