July 的干货还是不少的……
数据结构
一、字符串
旋转
三步反转法，O (N) 复杂度。
字符串包含
这里的问题是字符串是否包含某些字母，这里可以用 bit-map 实现。
字符串转数字（AtoI）
考虑问题需要全面：
- 开头的正负号，是否只有正负号
- 字符串是否为空
- 字符串中包含非数字字符
- 溢出：
- 如 2147483650, result > MAX/10
- 如 2147483649, result == MAX/10 && digit > MAX%10
回文（palindrome）
- 判断：从中间往两边或者是从两边往中间，两个指针扫描一次即可。
- 最长回文子串（LPS）：
- Manacher 算法，O（N）复杂度。
全排列
没有重复元素的全排列
这个情况下的全排列可以使用递归完成。每次排列都是首字母依次与包含首字母在内的元素进行交换，交换后从次字母开始递归的进行算法。
如：abc，首先 a 与 a 交换位置，求 bc 的全排列，b 与 b 交换位置，求 c 的全排列，c 的位置是最后一个，输出此时的字符串 abc，退回到之前的状态栈，b 与 c 交换位置，求 b 的全排列，b 是最后一个，输出此时的字符串 acb，退回到之前的状态栈……
有重复元素的全排列
这个情况下的全排列依然是上面的思路，但是这里需要注意的是，在元素 i 与元素 j 进行交换的时候，要求 [i,j) 中没有与第 j 个元素相等的元素。即被交换的元素不能曾经被交换过。
如：abb，a 与 a 交换，对 bb 进行递归，不满足交换条件，对 b 进行递归，到达底部无法交换，输出 abb；a 与 b 交换，满足条件可以交换，对 ab 进行递归，对 a 进行交换，得到 ab，对 b 进行递归，发现到达底部无法交换，输出 bab；对 b 进行交换，满足交换条件，得到 ba，对 a 进行递归，发现到达底部无法交换，输出 bba；a 与 b 进行交换，发现不满足条件，略过，输出结束。
全组合
使用 bit-map 解决。
问题集【待补完】
- 第一个只出现一次的字符
- 在字符串中删除特定的字符
- 字符串匹配
- 字符个数统计
- Hash
- 字符串的集合
- 最长重复子串（LCS）
- 字符串压缩
- 均分 01
- 给定一个字符串，长度不超过 100，其中只包含字符 0 和 1, 并且字符 0 和 1 出现得次数都是偶数。你可以把字符串任意切分，把切分后得字符串任意分给两个人，让两个人得到的 0 的总个数相等，得到的 1 的总个数也相等。
- 将该串字符串看做一个环，由于 01 均为偶数且切分后字符串可任意组合，那么必然存在一个直径将所有的 1 分为两个部分，同时也将 0 分为了两个部分，这两个部分的 01 个数相同。由此我们可以得到结论是，在该字符串中切至多两刀，我们就能找到一个窗，其中的 01 个数与其外的 01 个数相同。
- 代码实现可以以 n/2 的间隔建立两个窗边界，遍历一次即可知道该窗应放置在哪个位置了。
二、链表
在 O (1) 时间删除链表节点
用下个节点的数据覆盖前一个。注意链尾的情况。
单链表的转置
使用三个工作指针，不断的将每个节点的指向改变。
第 k 个节点
使用两个指针，前一个距离后一个 K 的距离，遍历至末尾。
中间节点
使用两个指针遍历，前一个的移动速度时候一个的两倍，遍历至末尾。
环
判断是否成环
使用两个指针，前一个的移动速度是后一个的两倍，遍历至两者相遇，则说明存在环。
寻找入口
接上，在两个指针相遇之后，后指针回到链表起点，前指针以与后指针相同的速度从相遇点开始遍历链表，两者相遇节点就是环的开始节点。
判断是否相交（无环）
若相交，则两链表从相交处往后一定是相同的，那么只需要考察两链表最终是否指向同一节点。
有环情况下（有环）
若相交，在有环情况下，其必然共有一个环，只需要遍历其中一个链表，找到一个环中元素，再在另一个链表中寻找该元素即可。
相交的第一个公共节点（无环）
由对其的思想可知，在无环情况下，其公共部分是一样的，那么，只需要找到两个链表长度的差值，长的链表从该差值开始，与短链表一起同时遍历，遇到的第一个公共节点就是两个链表的第一个公共节点。
三、数组
K-th
求一个数组中第 K 大的数，可以有以下集中思路：
排序，取第 K 个。复杂度最好是 O (NlogN)。
维护一个大小为 K 的堆，以最大堆为例，首先以 O (K) 的时间用前 K 个数建立一个最大堆，然后遍历后 n-k 个数，如果比对顶的元素小，那么将堆顶元素出堆，将该数加入堆中，出堆元素回到新入堆元素的位置上。
由于堆操作的时间复杂度为 O (logK)，复杂度可以简化至 O (K+(N-K) logK)=O (NlogK)
使用 QuickSelect 算法。平均情况下 O (N) 复杂度。
- 使用快速排序思想，选取一个锚点 pivot 将数组分为两个部分 Sa 和 Sb，若 Sa 的元素（不含 pivot）个数大于等于 K，那么第 K 大得数在 Sa 里，继续递归的对 Sa 进行考察；若 Sa 的元素等于 K-1（即含 pivot 在内共有 k 个元素），那么该 pivot 即为待求的第 K 个值；若 Sa 的元素少于 K 个，那么说明第 K 大得元素在 Sb 中，应对这个序列应用算法。
- 在求 pivot 的时候使用 median3 算法，其做法是将给定序列的首中尾按照大小顺序排列，并把 pivot 放置在倒数第二个位置。
两个有序数列和的 K-th 问题
使用最小堆进行处理。其思想在于从小到大依次找到前 K 个组合，由于 A [0]+B [0] 必然是第一个元素，紧跟其后仅比这个组合小的元素是 A [0]+B [1] 或 A [1]+B [0]，将 A [0]+B [0] 出堆之后，将这两个元素压入堆中，作为下一次出堆的备选。推而广之的，设每次出堆的组合为 A [i]+B [j]，那么需要同时将 A [i+1]+B [j] 和 A [i]+B [j+1] 压入堆中，直到完成 K 次出堆。由于建堆的时间复杂度为 O (K)，堆操作时间为 O (logK)，共有 K*O (logK) 次堆操作，总的时间复杂度为 O (NlogK)。
K-Sum
- 2Sum：
- 排序后二分搜索，O (NlogN)/O (1)
- 排序后从头尾双向扫描，O (NlogN)/O (1)
- 构造 X-S [i] 数组或 Hash，O (N)/O (N)
- K-Sum:
- 3Sum 可以转化为 2Sum；4Sum 可转化为 3Sum 然后转化为 2Sum……
- KSum 的递归 Sum (A,Sum,i) 函数实现：（数组 A，和为 Sum，还有 i 个值）
- 若取第 i 个数，则问题转化为 Sum (A,Sum-A [i],i-1)
- 若不取第 i 个数，则问题转化成 Sum (A,Sum,i-1)
- 终止条件为 Sum<=0 或 n<=0
- 输出结果条件为 Sum==A [i]
- 2Sum：
背包问题（经典的动态规划模型）【待补完】
01 背包
N 件物品，V 个背包，放入第 i 件物品的费用是 C [i]，价值为 W [i]，求解放入哪些物品使得背包价值最大。
解法：设 f [i][v] 代表了前 i 件商品恰好放入一个容量为 v 的背包中的最大价值那么可以得到这么一个等式：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}其代表的意义是，f [i][v] 的最大值是 “不放第 i 件商品得到的最大价值” 和 “放入第 i 件商品得到的最大价值” 的大者。
最大连续子数组和
输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。 求所有子数组的和的最大值，要求时间复杂度为 O (n)。
解法：由于最大子数组的首尾肯定不能包含和为负的子数组，由此我们可以从头开始遍历该数组，得到从上一个非负位置开始的累加和，若累加和为负则清零并重新记录起点。并且在整个过程中维护两个变量：CurSum 和 MaxSum。由以下的公式来维护 CurSum：
currSum = (a[j] > currSum + a[j]) ? a[j] : currSum + a[j];
跳台阶问题
一个台阶总共有 n 级，如果一次可以跳 1 级，也可以跳 2 级。是斐波那契数列的一个变体。写出通项即可。
换硬币问题
给定几个面额的硬币和一个价值和，问有多少种换法。
递归解法：设换法有 F (Value,Kind) 种，硬币面额数组为 value [Kind] 那么有:
F(v,k)=F(v,k-1)+F(v-value[K-1],k)意义为，使用 K 种硬币的换法等于不使用第 k 种硬币的换法加上使用第 k 种硬币的换法。
非递归解法：使用 DP。【待补完】
荷兰国旗问题
现有 n 个红白蓝三种不同颜色的小球，乱序排列在一起，请通过两两交换任意两个球，使得从左至右，依次是一些红球、一些白球、一些蓝球。
- 解法：类似于快排中的 partition 过程，中间的白球就是锚点，设置三个指针，Begin、Current、End，以以下原则进行移动、交换：
- 开始时 Begin 和 Current 在起点，End 在终点。
- 若 Current 指向白球，则移动至下一个（Current++）。
- 若 Current 指向红球，则与 Begin 交换，并且 Begin 指向下一个，Current 指向下一个（Begin++，Current++）
- 若 Current 指向蓝秋，则与 End 交换，Current 不动，End 指向前一个（End–）
- 运行至 End 遇到 Current，结束算法。
- 解法：类似于快排中的 partition 过程，中间的白球就是锚点，设置三个指针，Begin、Current、End，以以下原则进行移动、交换：
问题集
找出数组中的唯一出现过两次的元素，其余数都只出现过一次。
（1-1000 放在含有 1001 个元素的数组中，找到重复的那一个。）
- 对数组求和，减去 1-1000 的和，就是重复的数字。这个方法可能因为相乘的结果过大而溢出。
- 利用异或的性质：
a^b^a=a^a^b=0^b=b(0与0异或为0，1与0异或为1，相当于不会对原数造成变化)，将该 1001 个数组元素与 0-1000 进行异或，那么最终得到的结果就是重复的一个数。 - Bit-map 或 Hash，将这 1001 个元素映射到每一位上，重复的那个数位置上为 0。但是这种方法会带来额外的空间开销。时间复杂度都是线性的。
找出数组中唯一一个只出现一次的元素，其余元素均出现过两次。
- 利用异或的性质将求整个数组的异或和，结果即为唯一一个不重复的元素。
找出数组中唯一一个只出现一次的数，其余元素均出现过三次。
- 统计这个数组中的所有数（int）在各个位上的 1 出现的次数，单个的那个数如果在这个位上是 1，那么肯定无法被 3 整除，反之可以，通过统计这个可以知道该单个的数在哪些位上是 1，从而得到这个数。
找出唯一的 K 个数，其余的数都出现过两次，有几个数只出现过一次。
- K=2
- 其思路在于，这两个只出现过一次的数肯定是不一样的，在某些位上肯定是不相同的，我们通过将整个数组进行异或和计算得到哪一位是不同的，根据该位是 0 还是 1 将原数组分为两个子数组，这两个子数组必然分别包含了这两个数以及其他重复的数，我们对这两个数组分别进行异或和的计算就可以分别得到这两个非重复的数了。
- K=3
- [待补完]
- K=2
寻找数组中的逆序数
给定一整型数组，若数组中某个下标值大的元素值小于某个下标值比它小的元素值，称这是一个反序。
- 利用并归排序算法的过程中自然产生的对于逆序数的访问，累计逆序数的个数。在并归排序每一次的变序选择中，可以记录下所有的逆序个数。
【待补完】
四、树
- 二叉查找树
- 性质：
- 若任意结点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若任意结点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 任意结点的左、右子树也分别为二叉查找树。
- 没有键值相等的结点
- 查找、插入、删除的时间复杂度均为 O (logN)，但有可能退化至 O (N)
- 性质：
- 红黑树
- 本质上来说就是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为 O (log n)。
- 性质：
- 每个结点要么是红的，要么是黑的。
- 根结点是黑的。
- 每个叶结点（叶结点即指树尾端 NIL 指针或 NULL 结点）是黑的。
- 如果一个结点是红的，那么它的俩个儿子都是黑的。
- 对于任一结点而言，其到叶结点树尾端 NIL 指针的每一条路径都包含相同数目的黑结点。
以上的性质保证了红黑树的高度始终为 logN，进而保证了各项操作的时间复杂度始终为 O (logN)
- 【待补完】
五、算法心得
- 有序数组的查找
- 二分搜索【要会写】
- 杨氏矩阵的搜索
- 首先直接定位到最右上角的元素，配以二分查找，如果当前元素比待查数大则往左走，比待查数小则往下走。
- 出现次数超过一半的数字
- 数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。
- 解法：
- 排序，O (NlogN)/O (1)
- Hash，O(N)/O(N)
- 使用 time/candidate
- 在遍历数组的时候保存两个值：一个 candidate，用来保存数组中遍历到的某个数字；一个 nTimes，表示当前数字的出现次数，其中，nTimes 初始化为 1。当我们遍历到数组中下一个数字的时候：
- 如果下一个数字与之前 candidate 保存的数字相同，则 nTimes 加 1；
- 如果下一个数字与之前 candidate 保存的数字不同，则 nTimes 减 1；
- 每当出现次数 nTimes 变为 0 后，用 candidate 保存下一个数字，并把 nTimes 重新设为 1。 直到遍历完数组中的所有数字为止。
- 在遍历数组的时候保存两个值：一个 candidate，用来保存数组中遍历到的某个数字；一个 nTimes，表示当前数字的出现次数，其中，nTimes 初始化为 1。当我们遍历到数组中下一个数字的时候：
v1.5.2