leetcode和牛客网刷题
字符串
jz5. 替换空格
71. 简化路径
150. 逆波兰表达式求值
思路：分离符号位和数字位，注意判断数字的字符号
数组
面试题：一个无序数组中两个数之和等于给定的值N
方法一：穷举法：全部遍历，时间复杂度为O(n^2)
方法二：先排序，然后查找：使用快排（O(nlogn)），然后使用两个指针，一个指针指向头pi，一个指针指向尾部pj，如果两个指针指向的数字的和为N，则找到一组，pi++,pj--;如果和大于N则pj--;如果和小于N，则pi++。
方法三：遍历数组，将所有的值存入hash_map中
查找
jz11.旋转数组的最小数字
时间复杂度的优化为O(logn)
栈与队列
jz.9用两个栈实现队列
jz.30包含min函数的栈
zuo.用递归函数和栈操作逆序栈
zuo.用一个栈实现另一个栈的排序
239.滑动窗口最大值 zuo.生成窗口最大数组
jz31.栈的压入、弹出序列
借助一个栈来实现
链表：
jz6.从尾到头打印链表
有非递归和递归两种解法
234. 回文链表 [已二刷]
请判断一个链表是否为回文链表。
思路：方法一：用遍历链表，同时将结点存入栈中，然后用链表头开始与栈顶一个一个比较，如果不相等返回false，直到遍历完成后全部一样，返回true。这种方法时间复杂度为O(n)，空间复杂度为O(n)。
方法二：用双指针找出中间结点。然后反转后半段链表。反转完毕后，从最左边结点与最右边结点比较，相等都像中间移动，若有结点不相等，则ret=false；最后恢复链表。
86. 分隔链表[已二刷]
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。
思路：定义四个指针，分别是小于x的begin和end指针，小于等于x的begin和end指针。然后遍历链表，并切分结点，将小于x的结点用小于x的begin和end指针维护，将大于等于x的结点用另外两个结点维护。遍历结束时，判断小于x的begin指针是否为空，若为空，返回大于等于x的begin结点，若不为空，将小于x的end结点的next指针指向大于等于x的begin，返回小于x的begin结点。
138. 复制带随机指针的链表
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深度拷贝。
思路：
方法一：使用hasmap，空间复杂度为O(n)
方法二：直接复制，将next指针指向复制的结点，空间复杂度为O(1)
141. 环形链表[已二刷]
给定一个链表，判断链表中是否有环。
思路：
方法一：借助set来判断
方法二：快慢指针
142. 环形链表 II[已二刷]
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
方法一：借助set来判断
方法二：快慢指针(原理一定要说明白)
160. 相交链表[已二刷]
编写一个程序，找到两个单链表相交的起始节点。
方法一：借助set来判断
方法二：通过链表移动来判断
19. 删除链表的倒数第N个节点
典型的快慢指针的，但其中有许多细节需要注意
jz22.链表中的倒数第k个结点
jz25.合并两个排序链表
zuo.删除链表的中间结点和a/b处的结点
删除链表中的结点需要主要找到需要删除结点的前一个元素，然后再删除结点。
二叉树：
144. 二叉树的前序遍历[已二刷]
思路：递归实现与非递归实现
94. 二叉树的中序遍历[已二刷]
思路：递归实现与非递归实现
145. 二叉树的后序遍历[已二刷]
思路：递归实现与非递归实现
jz7. 重建二叉树
是一个很好的面试题，在手写的代码的时候需要注意异常情况的判断
331. 验证二叉树的前序序列化
思路：
空结点 - 非空结点 = 1，维护这条等式。
297. 二叉树的序列化与反序列化
思路：
序列化时将每个结点的数之间加入一个‘#’用来区分结点与结点，用‘_’用来区分空结点。
遍历顺序可以为前序遍历、中序遍历、后序遍历。
反序列化时用‘#’来切分字符串，然后用对应的遍历生成二叉树。
110. 判断平衡二叉树
思路：递归判断左子树和右子树的高度差是否为1
98. 验证二叉搜索树
思路：二叉搜索树的中序遍历的结果为递增序列
222. 完全二叉树的节点个数 注意注意：第一次遇见这样的思路，还需要多练习
思路：通过统计左结点来获取树的高度，然后判断根结点的右结点的最左结点是否为空，若不为空，则左子树加根结点的个数为2 ^（h-level)，若为空，则右子树的加上根结点的个数为2 ^(h-level-1)。递归求和。
226. 翻转二叉树 jz27.二叉树的镜像
注：贝壳二面面试时手撕的代码，现场写出来了，回来看leetcode原来是个简单题，面试官手下留情了。
101. 对称二叉树 jz28.对称二叉树
是上一题的延续，还需要重新回顾。
思路：根据原二叉树的前序遍历顺序与对称二叉树的顺序比较，如果比较的结点有一个为空，另一个不为空，返回false，如果比较的结点中value值不相等，返回false。
655. 输出二叉树
学习到的知识点：vector中不仅可以初始化int类型，也可以初始化string类型，初始值为""。
先将n*m维数组的中的值初始化为"",然后修改与二叉树对应的值。
jz54.二叉搜索树的第k个结点
思路：根据二叉搜索树本的的性质：二叉搜索树中序遍历有序性，可以找到第k个结点。最好用非递归的方法写。
jz. 二叉树的层次遍历 102. 二叉树的层次遍历
思路：借助两个queue交替来层次遍历二叉树
103. 二叉树的锯齿形层次遍历
思路：借助两个栈来实现，其中主要入栈顺序
jz.之字形打印二叉树
思路：借助队列和栈来层次遍历二叉树
jz8.二叉树中序遍历的下一个结点
思路：如果该结点有右子树，则下一个结点为该右子树的最左结点；如果该结点没有右子树，则判断该结点是否为父结点的左孩子，若是，则父结点为该结点的下一个结点；若不是，则向上遍历，若找得到某个结点是父结点的左孩子，则为该结点，若找不到，则为空。
jz26.树的子结构
很好的一递归个思路，需要留意。
jz33.二叉搜索树的后序遍历
遇到这种题，首先先自己画出一个二叉搜索树，并将其后序遍历的数组写出来，查找规律：根据数组最后一个数（根结点）来将数组分为小于根结点的数组和大于根结点的数组，然后递归判断即可。
堆
295. 数据流的中位数
思路：维护一个最大堆和一个最小堆，中位数就在这两个堆的堆顶。
哈希
380. 常数时间插入、删除和获取随机元素
思路：重点是索引的建立
并查集
200. 岛屿的个数
思路：1. 在单CPU中可以用影响函数来标识岛屿；2. 在大数据的时候需要用到并查集
547. 朋友圈
思路：先将每个小朋友当作独立的集合，然后将有联系的小朋友union为同一个集合，最后输出集合的个数。
前缀树（Trie树）
208. 实现 Trie (前缀树)
Trie树的基本实现过程
线段树
贪心
动态规划
其他
jz29.顺时针打印矩阵
这个题的边界条件需要特别主要，理解打印过程就不太难了，难点就在边界条件的考虑上。
