algorithm

类型	题目	思路	备注
数组	二分查找	没啥思路，凭感觉写？有两种形式左闭右开和左闭右闭
	移除元素	1.暴力解决 2.更优解为双指针	需要巩固
	有序数组的平方	1.先全部进行平方操作，在进行排序 2.需要额外的存储空间，双指针	因为负数的存在
	长度最小子数组	1.暴力解决 2.滑动窗口，降低时间复杂度	在看过滑动窗口思路后，可以完整的实现出来。
	螺旋矩阵II	1.没有任何思路，抄答案了解了一下	虽然没涉及算法，但是感觉比较难！
	三数之和	1.双指针方式，但是需要先将数组进行排序	在处理重复元素时，需要注意如何过滤。
字符串	反转字符串	1. 双指针，两两交换	想到了这种方式值得鼓励
	反转字符串II	1.最开始也是没读懂题目，多读几遍就能解出来了	大脑过载的时候确实需要休息！
	替换空格	1.暴力解决，空间复杂度较高 2.看了双指针思路自己实现	在于如何将一个空格扩大
	反转字符串里的单词	1.想到了一种简单的方式，直接 split 然后根据索引交换，但是失去了本题的意义 2.全部反转后，在进行部分的反转，一开始以空格作为分割条件，但是处理结束字符时出现了问题。最后的字符需要使用 \0 处理。	全部反转再部分反转
	左旋转字符串	1.暴力解决 2.通过反转的方式实现，这种方法第一时间真的想不出来..	部分反转，部分反转，全部反转
	strstr	1.复习了 KMP 算法是怎么运行的（主要是理解最长公共前后缀的含义）以及 next 数组的构造和使用。 2.有两种形式，next数组中索引统一减一的方式和常规的方式。这两种方式对于 KMP 原理没有影响，主要影响在于 KMP 算法的实现。	KMP 算法思想：当遇到不匹配的字符时，充分利用之前已经匹配过的字符，避免重新匹配。
	重复子字符串	结合了 KMP 使用，需要充分理解最长相等前后缀的含义。
链表	翻转链表	1.新建一个链表，然后遍历原来的，采用头插法，得到的就是反转链表。时间、空间复杂度都是 O(n) 2.采用双指针的方式，pre, cur, next 一边遍历一遍翻转，最后时限的时候忘记了把 cur 指向 next 需要注意。
	判断链表是否有环	1.因为之前做过这个，所以直接采用了双指针的方式实现。慢指针一次走一个，快指针一次走两个，当快指针追上慢指针时，就说明链表中存在环。	如果说快指针一次走三个不是两个？还能证明链表中有环吗？我认为是可以的，他们都是 1 的倍数，只不过遍历的节点的数量会比2多。
	链表是否相交	1.自己想的是，通过节点计数的方式实现。 2.双指针方式实现，不过需要一些额外的处理，因为两条链表长度不同，在开始遍历前需要将两条链表的起点对齐。
	环形链表II	寻找环的入口 自己这边没思路。	既然没思路，就背下来！
	移除链表倒数第 n 个节点	关键是如何找到被删除节点的前一个节点。 双指针方式实现，快指针先向前移动 n 个节点，然后快慢指针同时移动，当快指针指向末尾时，慢指针指向的就是被删除节点的前一个节点。	很奇妙。
栈与队列	使用栈实现队列	1.两个栈实现队列，具体思路已经写在代码注释中了
	使用队列实现栈	同上一题类似，自己也想了能不能使用两个队列来完成，后来发现第二个队列同第一个是无差别的，主要还是队列的性质导致。 思考片刻后，一个队列就足够了，比如 12345 入队，但是出队的第一个元素应该是最后进入队列的，但是队列是需要满足 FIFO的。 所以我们对应的操作就是，把前四个元素重新入队，然后 5 就排在了队头的位置，弹出即可。其余元素处理方式相同。
	有效的括号	1.自己采用了左右括号技术的方式实现，但存在问题。当括号为 )( 情况时，算法执行输出错误。 2.使用栈完成，左括号入栈，但是入栈的右括号，比如左括号 ( 但是入栈时是) 可以减少代码量。只需要在栈顶匹配是由同右括号相同即可。	三种情况： 1.左括号多了 2.括号不匹配 3.右括号多了
	移除相邻重复的字符	1.使用栈，入一个，比对一个，相同就弹出，不相同就继续往里放。
	逆波兰表达式	1.其实同上一题类似，需要明白计算机是如何处理运算表达式的。
	滑动窗口最大值	1.自己想了一种指针移动的方式，但是需要根据窗口大小进行调整。 2.单调队列的方式实现，单调递增/减的队列。	入队和出队时需要额外处理。
	前K个高频元素	1.利用堆数据结构，为什么应该使用小顶堆呢？	面试时候出这种题还挺恶心的.. 因为没有现成堆给你用，需要自己实现..
二叉树	二叉树的遍历	1.前序遍历 2.中序遍历 3.后序遍历	中间节点位置的变化 1.递归方式 2.迭代方式，需要借助额外的数据结构 3.层序遍历
	翻转二叉树	1.在遍历的过程中，进行节点的交换，采用前序遍历，先处理中间节点然后将左右两个子树进行交换
	对称二叉树	判断二叉树是否是对称的，即左子树的左孩子与右子树的右孩子是否相同，需要注意递归的终止条件，即什么情况下就知道当前这棵树不是对称的。
	二叉树的最大深度	关键在于根节点到叶子节点的最大深度就是求当前这棵树的高度。 所以应采用后序遍历的方式 1.收集左子树的高度 （左） 2.收集右子树的高度 （右） 3.取左子树和右子树的最大值 （中） 另一种方法：层序遍历	深度，前序遍历 高度，后序遍历
	二叉树的最小深度	1.层序遍历，这是一种比较简单的方式，关键在于如何判断当前遍历的节点就是叶子节点 答：cur.left == nil && cur.right == nil	注意：最小深度指的是根节点到最近的叶子节点。 需要注意子树为空的情况。
	完全二叉树的节点个数	1.最初，写了几种求普通二叉树节点个数的方法，后序遍历求节点个数，层序遍历求节点个数 但是。 针对完全二叉树有更优解，即，判断其子树是否有满二叉树，然后利用公式求满二叉树的节点个数。	完全二叉树的性质
	平衡二叉树	后序遍历，求左右子树的深度，然后进行减法运算判断是否大于一。	平衡二叉树的性质，每个节点的左右两个子树的高度差的绝对值不超过一。
	二叉树的所有路径	遍历方式采用前序遍历，每次将节点压入栈中，直到遇到叶子节点，打印出该路径。 碰到叶子说明到底了，该返回到父节点继续执行，所以这时候需要将刚刚的叶子节点弹出。	没想明白回溯的过程，涉及到递归传值时候就很懵逼。
	左叶子之和	关键在于如何判断二叉树的左叶子节点。	通过父节点进行判断。
	二叉树左下角的值	递归的方式没看，层序遍历比较简单，每次获取该层的第一个节点即可。
	路经总和	寻找从根节点到叶子节点是否有等于 target 的值。 这里只要找到一条路径就可以，不需要遍历整棵树。所以遇到满足条件的要及时返回。	采用减法的方式更简单，每次用 target 的值减去节点中的值。
	路径总和ii	需要找到所有满足条件的路径，这时候就需要遍历整棵二叉树。	同上一题类似，涉及到回溯的过程。
	从中序后序构造二叉树	首先要理解理论知识，通过中序后序的数组进行构建，然后再将理论知识转化为代码实现，这一步还是挺难的，因为又涉及到递归。
	从前序中序构造二叉树	方法同上一题	前序和后序可以构造二叉树吗？不能，因为没有办法判断中间节点的位置。
	最大二叉树	同样是构造二叉树，找到数组中的最大值当作根节点，然后最大值左边的子数组作为左子树，最大值右边的子数组作为右子树。	相对来说比前两个要简单些。
	合并二叉树	有两种情况需要特殊处理： 1.左子树为空，右子树不为空 2.左子树不为空，右子树为空 其余节点直接合并即可。	我这里选择的是将树合并到左边的二叉树上。 迭代法实现，自己一开始使用了两个队列，其实没必要，一个队列即可，只不过入队的时候将两个父节点入队。
	二叉搜索树中的搜索	给定一个值，在二叉搜索树中进行查找操作。	采用哪种遍历方式都可以，因为都没有对中间节点进行处理。
	验证二叉搜索树	这道题把该踩的坑都踩了.. 1.理解二叉树的特性，最后验证得到的数组是否有序即可。 2.双指针的方式，一个指针指向前边的节点，一个指向当前节点，仍然采用中序遍历的方式，中序遍历肯定是有序的，所以比较两个指针的大小即可。	这道题要理解二叉搜索树的特性，中序遍历二叉搜索树的结果是有序的。 不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了。
	二叉搜索树的最小绝对差值	怪自己没审题..求了一个最大值差值.. 求最小绝对差值的原理其实同上一题类似，仍然使用双指针的方式实现。	记录当前的最小值，然后使用中序遍历二叉树，计算两个指针的差值即可。
	二叉搜索树中的众数	普通二叉树求众数，统计出节点信息，然后过滤出众数。 二叉搜索树求众数，双指针方式实现，还涉及到了清空结果集的过程。	这里学到了 map 的高级用法，不需要判断 key 是否存在，然后再进行赋值，直接通过 map[key]++ 就能进行 key 的初始化或者是将 val 加一。
	二叉树的最近公共祖先	从叶子节点开始查找，一般这种情况都采用后续遍历的方式。
	二叉搜索树的最近公共祖先	利用二叉搜索树的特性：中序遍历为有序数组，然后进行处理。
	二叉搜索树的插入操作	插入操作相对简单，找到合适的叶子节点直接插入即可
	二叉搜索树的删除操作	删除操作比较复杂：需要考虑是否为叶子节点。如果不是叶子节点需要考虑左右子节点是否为空的情况。
	修剪二叉搜索树
	将有序数组转化为二叉搜索树	同根据前中序遍历构造二叉树类似，都是找到切割点然后进行递归处理。
	把二叉搜索树转化为累加树	概念就熟悉了一会，了解了累加树是什么意思..	有难度..
		从这里开始就是回溯的内容，回溯相关的东西还是比较难得，因为都是需要进行递归处理，在递归后边的操作就是回溯内容..
回溯	组合问题	题目：给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。	可以用 for 循环实现，如果 k 是 2 可以用两个 for 实现，k 是 3 用三个 for，以此类推..如果 k 是 50 .. 50 个 for .. 所以这时候就需要使用递归处理..