数组篇

1. 二分法：

1. 写程序的时候，一般会用左闭右闭区间，或者左闭右开区间。

左闭右闭：while left <= right:             right = middle -1 

左闭右开： while left < right:              right = middle （反正取不到right）

2. 移除元素

数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

题目：给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。

这题可以用快慢指针，等于val的快指针多走一步，然后用快指针的值覆盖慢指针的值。

3. 滑动窗口

滑动窗口解法：其实就是用一个循环来做两个for循环的事情。left等价于控制开始位置的for循环，right等价于控制结束位置的for循环。

链表篇：

1. 移除链表元素（虚拟头结点）

题目：给定一个链表和一个值，将链表中与值相等的节点删除。

因为删除头结点和其他节点的方式不同。导致代码不统一。加入一个虚拟头结点后，头结点就和其他节点一样了，就可以用统一的代码处理。

2. 反转链表类

题目：把一个列表翻转。

用prev current两个指针来实现。自己画图把逻辑理清楚，然后写一遍就好。

题目：将相邻的节点两两交换

这就比反转列表更提高难度了。要用更多个指针。还是一样，自己画图把逻辑理清楚，然后写一遍就好。

3. 链表相交&环形

题目：给出两个单链表的头结点，返回他们的相交节点。

既然相交，那尾部应该是一样的。那就求出两个链表的长度。求长度差N，长链表先走N步后，短链表的指针也出发。两指针相遇的点就是交点。

题目：判断链表是否有环。如果有环返回环的入口。

思路，创造一个两指针相遇在环入口节点的机会！

假设入口节点为x, 入环后再走y个点，快慢指针相遇，y再走z步又到入口节点x。则我们有2(x+y) = x + n(y+z) + y => x = (y+z) - y

这意味着，如果有个新指针2, 在环内先走了y步，然后另个一个指针1从head出发，两指针都走x步的时间，将会在环的入口相会。这就创造出了指针相等的条件。

哈希表篇

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

题目：两个单词，判断是否由相同的字母构成。

用一个字典统计字母频数即可。这里需要记住一个ord(）函数

题目：两数相加

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

用字典储存。遍历一遍，如果num的补数（target - num）在字典内，则返回他们的数组下标。不在，就把num和对应的下标计入字典。

题目：三数之和 

给定一个长度超过3的数组，返回所有的三数组合 [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. 答案中不含重复的三数组合。

排序后，最外层的循环是第一个数。然后在区间[i, n-1]里面用双指针，left, right。找三数之和为0.

题目：四数之和 I

将上一题的三数之和拓展为四数之和。三数组合是一层for循环，加一层左右指针。四数组合可以两层for循环，加一层左右指针。

题目：四数相加II

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。

和两数之和类似。AB相加的和放入一个set，然后计算-(C+D)看是否在set中。

字符串篇

1. 反转字符串

题目：将输入的字符串反转过来。你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

左右指针对应值互换即可

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

定义一个翻转的函数，然后逐一处理每一段2k个字符。

2. 全部翻转+局部翻转

题目：给定一个字符串，逐个翻转字符串中的每个单词。

没啥把句子里的单词翻转的方法。那就把整个字符串全部翻转，然后每个单词内部翻转回去。

题目：右旋转字符串：给定一个字符串 s 和一个正整数 k，将字符串中的后面 k 个字符移到字符串的前面。

先这个字符串全部翻转，然后局部翻转：前k个字符翻转，剩下的翻转。

栈与队列篇

1. 栈和队列的相互转换

题目：用栈实现队列

思路：用两个栈实现队列。stack1存入，要pop前先转移元素到stack2, 此时stack2就类似队列了；接着把stack2栈顶的元素弹出即可。注意：在stack2清空前（也就是队列前面部分耗光前），不需要再做移动的操作。

题目：用队列实现栈

思路：用两个队列实现栈。q1存入。如果要弹出，就把q1元素移动到q2，然后剩最后一个元素，弹出。注意：移动完后，直接把q1 q2互换，不需要移回来。因为两个队列顺序都一样。

2. 栈的应用

题目：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否合法。

思路：用字典把左右括号对应起来。碰到左括号入栈，右括号出栈。

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

碰到与栈顶元素不一样的就入栈，碰到一样的就弹出。最后返回栈这个列表组成的字符串即可。

题目：逆波兰表达式求值

思路：碰到数字存入栈；碰到符号则弹出栈顶的两个元素，运算后的结果存入栈

3. 最小堆的应用

题目：给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

思路：1. 要统计元素出现频率：用map统计频率；2. 对频率排序，用大顶堆排序；3. 找出前K个高频元素。

题目：给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。返回滑动窗口中的最大值。

思路：其实队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了。移动窗口时候，是根据index移除，因此窗口里也维护index就好了。

二叉树篇

深度优先：前中后序遍历； 广度优先：层序遍历。要熟练掌握递归迭代的方法。

1.  求二叉树的属性

题目：给定一个二叉树，检查它是否是镜像对称的。

思路：1. 递归法：终止条件：if 左右都为空，对称，返回true；elif 有一个为空，不对称，return false；elif 左右都有值，但值不等，不对称 return false。递归条件：else 比较 left.left vs right.right 和 left.right vs right.left.

题目：二叉树的最大深度。 & n叉树的最大深度。

思路：迭代法：层序遍历。递归法，前序遍历。

题目：给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

思路：递归：终止条件：碰到叶节点则返回1. 递归条件：返回左子树（如果有）和右子树（如果有）的最小深度，取较小者。

题目：完全二叉树的节点个数

思路：完全二叉树只有两种情况，1：就是满二叉树，2：最后一层叶子节点没有满。但左子树或右子树一定有一个满二叉树。

对于情况一，可以直接用 2^树深度 - 1 来计算。对于情况二，左右孩子中，满二叉树的那个直接计算。而另一个进行递归。

题目：给定一个二叉树，判断它是否是高度平衡的二叉树。

思路：一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

递归法：终止条件：如果根节点为空，返回True；如果左右子树高度差超过1，就返回False。递归条件：递归左右子树。迭代法一样。

题目：给定一个二叉树，返回从根节点到叶子节点的所有路径。叶子节点是指没有子节点的节点。

思路：需要记录路径，回溯算法最合适。

题目：计算给定二叉树的所有左叶子之和。

思路：要注意是判断左叶子，不是二叉树左侧节点，所以不要上来想着层序遍历。简单的前序遍历即可。左叶子三个约束条件：1. 不是根节点 2. 是叶节点 3. 是父节点的左节点。 迭代的时候，根节点以下，把节点放入stack的时候，带上一个标签表示是否是左节点。

题目：给定一个二叉树，在树的最后一行找到最左边的值。

思路：用层序遍历是非常简单的了，反而用递归的话会比较难一点。

这里的层序遍历，在每一层内部从右到左，保证最后一个节点是最左的节点。

题目：给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。112返回布尔值，113返回所有符合的路径。

思路：终止条件：到叶节点的时候，看路径上所有节点的值总和是否等于targetSum。如果相等，就把路径贴入结果。如果不是叶节点，就继续放进栈迭代。

2. 二叉树的修改与构造

题目：翻转一棵二叉树。

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

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

题目：中序+前/后序 构造二叉树

思路：前序遍历第一个元素是根，后序遍历最后一个元素是根，中序遍历根元素左边是左子树，右边是右子树。

题目：给定一个不含重复元素的整数数组。构建最大二叉树

思路：最大二叉树的根是数组中的最大元素。左子树是通过数组中最大值左边部分构造出的最大二叉树。右子树是通过数组中最大值右边部分构造出的最大二叉树。与上一题一样。

题目：合并二叉树 。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

思路：递归法终止条件：两个root都为空，返回空；一个为空，返回另一个；递归条件：两个都不为空，root.val等于两个相加，左右节点递归。

迭代法：层序遍历比较方便。

3. 二叉搜索树的属性

题目：给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中搜索到节点值等于给定值的节点。 

思路：二分搜索法

题目：给定一个二叉树，验证其是否是一个有效的二叉搜索树。

思路：递归法和迭代法都很直观，见代码。还有一种做法是：二叉搜索树的中序遍历是递增序列（反之也成立）。

题目： 二叉搜索树中节点值之间的最小绝对差 

思路：搜索二叉树的中序遍历是递增数列。然后对递增序列求最小绝对差。用callback: callback其实就是把函数diff()作为参数传入中序遍历函数inorder_traversal()。

题目：二叉搜索树中的众数 

思路：依然是利用中序遍历转为递增数列。用callback把函数update_mode 作为参数传入遍历函数inorder_traversal()。

题目：把二叉搜索树转换为累加树 ，使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

思路：可以用右中左逆中序遍历转为递减序列。这样只要从前往后累加就好了。

4. 二叉搜索树的修改与构造

题目：二叉搜索树中的插入操作 

思路：递归：和二分法查找类似。迭代：稍微麻烦点，需要记录父节点，插入的方向，这样才能做插入操作

题目：删除二叉搜索树中的节点 

思路：1. 在二叉搜索树中找到该节点。如果是叶节点，直接删除；如果有一个左右节点，用左右子树代替当前节点；如果同时有左右节点，就去找右子树的最小值，把这个最小值填入当前节点。然后在右子树中，删除最小值节点（一定是叶节点）。

用迭代法要注意，如果删除子节点，要更新父节点对其的引用。因为二叉树节点是一个对象实例，而python 是没有办法立即释放一个对象的。我们只可以通过修改 父节点的 left 或 right 指针来解除对子节点的引用，而不能直接让子节点等于None而实现删除。

题目：给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。

迭代法：用stack写有些麻烦，可以利用二叉搜索树的性质，最大和最小的节点都在最边上，只要把最边上超出范围的节点修剪去即可，不比遍历所有节点。不过这里最好用一个虚拟头结点才好处理。

递归法：如果当前节点超出右边界，就返回左节点；如果超出左边界，就返回右节点；如果不超出边界，就对左右节点递归使用函数。

题目：从一个递增数组，构造一棵高度平衡二叉搜索树。

思路：找出数组的中间节点为根节点。

5. 二叉树公共祖先问题

 题目：二叉树的最近公共祖先  

思路：递归法是最直观的：

终止条件：找到等于p or 找到等于q or 找到None，都返回node. 

递归条件：递归每个node的left和right，如果left right都有返回，则返回当前Node，如果只有left有返回，则返回left的返回，如果只有right也一样。

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

思路：比普通二叉树更容易。但要注意，返回节点的终止条件是：min(p.val, q.val) <= root.val <= max(p.val, q.val)，要取等。因为如果遍历到p或者q时候，另一个node一定在其子树上。

单调栈篇

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

题目：根据每日温度输出：要想观测到更高的气温，至少需要等待的天数。

思路：使用一个从栈底到栈顶递减的单调栈，while新元素 i 比栈顶的元素大，那就弹出栈顶元素x，那元素x距离第一个比自己大的元素就是 i-x.

题目：下一个更大元素 I

nums1 是 nums2 的子集（没有重复元素）。找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

思路：和上一题几乎一模一样，就不过把元素放到了nums1而已。

题目：下一个更大元素II

给定一个循环数组，输出每个元素的下一个更大元素。

思路：还是单调栈的应用。只要循环两个数组长度即可。

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

接雨水这题本质上是寻找左右第一个高于自己的柱子。用一个从栈低到栈顶递减的单调栈即可。

那雨水面积就是 water += (i - stack[-1] - 1) * (min(right, left) - mid)。这里要注意，头尾两侧没有柱子围着。如果stack pop到空，也就意味着此时没有左柱子围着了。那就要break。

题目：柱状图中最大的矩形。给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

单调栈思路：最大矩形实际上就是寻找左右第一个低于自己的柱子。用一个从栈底到栈顶递增的单调栈即可。

那矩形面积就是：(right-left-1)*heights[mid] 。不过这里要注意，左右第一个柱子，没有更左或更右的低于自身的柱子。那就头尾加两个0好了。

回溯算法篇

代码模板：

题目太多就不总结了。看文章第20-26天。

以及卡哥总结 https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E6%80%BB%E7%BB%93.html

贪心算法篇

看文章27-32。重点看31 32两天。

卡哥总结 https://programmercarl.com/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93%E7%AF%87.html