算法练习
- three sum
- next permutation
- search in rotated sorted array
- combination sum
- combinatiion sum ii
- unique paths
- subsets
- sum root to leaf numbers
- surrounded regions
- palindrome partitioning
- word break
- bitwise and of numbers range
- kth largest element in an array . solution 1 use heap, solution 2 use quick select.
- maximal square. Use dynamic programming. solution 2 use just O(n) space. The extra space equals matrix col length.
- majority element ii . 解法一使用 "摩尔投票法"。
- LCA 二叉树最近共同祖先问题.
递归解法递归结题的思路，在左子树、右子树查找两个节点，可能的结果有：
- 该节点就是其中的一个节点，则返回该节点
- 两个节点都不在左边，那么肯定都在右边，返回右边找到的节点
- 两个节点都不在右边，那边肯定都在左边，返回左边找到的节点
- 左右两边都找到一个节点，则返回当前节点
- search a 2d matrix ii. 递归解法
每次仅能将搜索区域缩减为之前的3/4，效率一般。解法二从左下角或右上角扫描矩阵，时间复杂度为O(m+n)代码简单，且有较高的效率。
- perfect square. 解法一使用动态规划，但转化方程较复杂。
- best time to buy and sell stock with cooldown.
非常经典的动态规划题目，状态转移方程比较复杂，需要两个方程。非常重要！递归解法
- coin change. 动态规划解法
- increasing triple subsequence.需要理解解法的思想：
- 维护一个有序数组（仅通过两个变量的方式）
- 更新数组使数组有更大的可能性满足条件
- 更新数组要确保判断条件始终成立，即若更新后的数组满足条件，那么更新前的数组一定也满足条件
- water and jup problem. 裴蜀定理解法. 了解哪些场景可以使用裴蜀定理以及裴蜀定理的内容：对于两个整数a, b其最大公约数定义为gcd(a,b)那么对于任意的两个正整数x,y，xa+yb其一定是gcd(a,b)的倍数。
- kth smallest element in a sorted matrix.解法一使用堆来查找第k小的元素，需要注意某一列扫描完毕时堆的长度减一，以及如何缩减堆的长度。解法二使用二分查找，需要注意的是当找到某个数n，矩阵中小于等于n的个数为k时需要继续缩小搜索空间的上限，直到搜索空间不存在。此行为是为了避免矩阵中不存在n。
- partition equal subset sum. 使用经典的背包问题解题。
- 4 sum ii. 解法一将4层遍历缩减到2层遍历，但需要注意时间与空间优化的细节。
- ones and zeroes. 解法一使用背包思想。有两个背包，一个装zero一个装one。判断能否再装下一个字符串的条件时必须同时装下这个字符串中的zero和one。解题时需要注意的是在更新dp数组是需要从后往前更新，防止在一轮更新中后面的dp使用本轮之前更新的dp。解法二首选尝试暴力破解带需要花费太长的时间，之后通过cache，减少重复扫描，减少运算时间。主要注意该解法中的key。
- coin change 2. 两种解法都使用背包解题思想。[解法一](./src/medium/coin_change_2_1
.js)使用常规的思路从后往前更新dp数组。由于不限制某种面额硬币的数量，解法二采用从前向后更新dp数组，避免了最内层针对硬币面额的循环，提高了一定的效率。
- friend circles. 解法一
使用比较传统的DFS算法。解法二使用Union Find算法，简化了算法的复杂度，降低了运行时间。但需要注意在更新parent数组时更新的是最根节点的父节点。
- koko eating bananas. 解法一
使用简单的二分查找法寻找最小的吃香蕉速度，循环结束时(low === high)需要确保该最小值任然要满足吃完的条件，要注意如何更新low和high。
- super egg drop. 解法一使用动态规划思想。
dp[i][j]表示i个鸡蛋j次操作最多可以搜索的楼层数；dp[i][j] = dp[i-1][j-1] + 1 /*鸡蛋碎了*/ + dp[i][j-1] /*鸡蛋没碎*/;。
- 求两个有序数组的中位数。首先需要理解什么是中位数，以及与平均值的差异。简单理解中位数就是有序数组中中间位置的数值。其次就是注意二分查找解法中缩减查找范围的条件。
- 求最长合法括号字符串长度。需要注意解法中dp[i+1]的意义，以及状态转移方程。
- dp[i+1]表示以第i个字符串结尾的最长合法字符串长度
- 若第i个字符为')'且前一个合法子串之前的一个字符为'('，则dp[i+1]=2+')'之前的合法子串的长度+'('之前的合法子串长度
- 注意保护变量的使用，减少循环中的判断
- 计算总的雨水收集量。分治解法中dp[i+1]表示以i位置结尾时的雨水收集量，状态转移方程较复杂，需要找到该位置之前的最高高度所在的位置，并重新计算最高高度所在位置与当前位置的雨水容量。解法二
通过累加每一个位置的雨水容量，求得总的雨水容量。某一位置的雨水容量等于其左侧的最高高度与右侧的最高高度中较小的高度减去当前高度，若为负值则记为0。代码简单效率较高，仅需要扫描两次数组。
- 复制复杂链表。复杂链表中包含两个指针：next和sibling，sibling可以指向任意一个兄弟节点。解法将复制过程分解为三部：
- 复制每一个节点，并将复制的新节点链接在原节点之后。
- 设置新节点的sibling指针。dup.sibling = node.sibling.next。该步骤完成之后，所有新节点的sibling指针都已指向正确的节点。
- 将链表拆分成新旧链表。
- 计算"1"的个数。给定一个正整数n，计算从1到n之前1数字1出现的个数。解法一
使用递归思路计算每一位上"1"出现的次数，例如对于正整数12X34，计算百位上1出现的次数：
- 若X == 0，则百位上1出现的次数为 12 X 100 = 1200次，从1100~12199。
- 若X == 1，则在case 1的基础上增加34+1次，范围从12100~12134。
- 若 X > 1，则在case 1的基础上增加100次，范围从12100~12199。