Algorithms

Trie 也称字典树，名称来源于Retrieval，支持$O(n)$插入和查询操作，以空间换取时间的数据结构. 用于词频统计和输入统计领域, 可以高效地存储大规模的字典数据, 也可以用于模糊匹配, 搜索最长前缀词等. A trie, also called digital tree, radix tree or prefix tree is a kind of search tree - an ordered tree data structure used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Keys tend to be associated with leaves, though some inner nodes may correspond to keys of interest. Hence, keys are not necessarily associated with every node. ...

Rabin-Karp Fingerprint Rabin-Karp fingerprint(RK) 基于 modular hashing： Compute a hash of pattern characters 0 to M - 1. For each i, compute a hash of text characters i to M + i - 1. If pattern hash = text substring hash, check for a match. 如果在一一比较中对text的每个子串都重新计算hash，那么速度比暴力算法还慢。 所以算法的关键在于如何高效地计算哈希值：Horner’s method - M阶多项式hash的线性时间方法 $$a^b \pmod c = (a \pmod c)^b$$ 引理： $$(a \times b) \pmod c = [( a \pmod c ) \times (b \pmod c) ] \pmod c$$即积的取余等于取余的积的取余. ...

In computer science, string-searching algorithms, sometimes called string-matching algorithms, are an important class of string algorithms that try to find a place where one or several strings (also called patterns) are found within a larger string or text. 字符串搜索/匹配算法在大规模文本应用中有非常重要的作用，比如文章敏感词搜索，多关键词过滤搜索等。如果使用暴力搜索，则时间复杂度很高（若 m 为关键字的长度， n 为要待搜索的字符串长度， k为关键字数量，则复杂度为$O(n \times m \times k)$。而好的算法可以让这些问题的时间复杂度大大降低。 常用的算法有Knuth–Morris–Pratt(KMP), Boyer-Moore(BM), Rabin-Karp(RK), Trie, Trie图, AC自动机等. 一个实例 匹配时，想象我们拿着模式字符串pat=ABABAC, 像尺子一样从左到右对齐依次匹配如图的txt。 从txt[i=0]开始, 把pat的开头pat[j=0]对齐txt[0], 开始比较pat[0]和txt[0], 发现不匹配, 暴力的算法是从txt下一个字符重新开始i=1, 同时把尺子也右移一位对齐新的txt起始点. 从i=3开始, 发现一开始可以匹配上(pat[j=0] == txt[3]), 那么保持尺子不动, 开始比较pat[j+1]和txt[i+1], 结果不匹配. 从i=4开始, 情况也类似, 而且发现连续匹配上了pat[++j]和txt[++i], 假如运气好, 我们能匹配完整个尺子, 那么达到目的. 可惜在i=7时失败了. 问题的关键就是i=3和i=7这里, 特别是i=7, 假如还是用暴力解法1操作, 那么需要重新比对txt[i=5,6,7...]. 但前面已经匹配了一半的尺子了, 那么其实我们已经知道了txt的后缀txt[4,5,6]和尺子的前缀pat[0,1,2]重合, 我们能否利用这个信息来优化算法? 按照前面的分析, 每一个已匹配的前缀等于txt中已匹配的后缀, 那么txt后缀后面可能接的字符有R种, 我们可以提前计算每一个已匹配txt后缀后接每一种字符时, 应该怎么做. ...

Boyer-Moore算法 在从头到尾对齐txt的字符时, 每一次对齐, BM算法反方向从尾到头检查patternP=BAABBAA和txt字符是否匹配。匹配过程中如果发现txt[i] != P[j], 也就说二者子串不相等, 如...XAA != ...BAA, 且字符txt[i] = X在P中不存在时，可以把P开头对齐到txt[i+7], 一次就跳过了7个位置. 模式相较于文本一般较短, 所以模式中包含的字符种类相对也比较少, 那么这样的跳跃出现情况就很可观了, 可以大大加速匹配. 不过一般来说, 可能txt的某些子串会和P的其他子串重合，不失一般性我们需要像Knuth-Morris-Pratt算法一样的重启位置数组。 Bad Character Heuristic(BCH) 重启点位: 预先计算各个字符c在Pattern的最rightmost的位置(若无则-1), 这些位置告诉我们如果是txt中的字符c导致不匹配, pattern可以右移的距离. badCharacterPreprocess(String pat) { // Compute skip table. this.pat = pat; int M = pat.length(); int R = 256; right = new int[R]; for (int c = 0; c < R; c++) right[c] = -1; // -1 for chars not in pattern for (int j = 0; j < M; j++) // rightmost position for right[pat.charAt(j)] = j; // chars in pattern } 有了right数组后, 一个例子说明匹配过程: ...

如何实现快速的幂运算？ 要求$c = a^b$, 按照朴素算法把a连乘b次的时间复杂度是$O(n)$. 而快速幂能做到$O(\log n)$。把b转换为二进制, 二进制数第i位的权为$2^{i-1}$，就可以把二进制拆分为若干个以2为底的真数, 然后利用幂数的性质，例如用朴素算法求$a^{11}$要求乘11次. 考虑到11的二进制为1011, 如果把$a^{11}$拆分为: $$a^{11} = a^{a_0 2^0 + a_1 2^1 + a_2 2^2 + a_3 2^3} = a^1 a^2 a^8$$ 可以看到每一个因子都是上一个因子的平方，利用$a^2 a^2$求出$a^4$, 同样利用$a^4$的平方求出$a^8$, 每次计算只需要用到上一次计算出来的结果, 所以总的运算次数是4次. 任何一个数b最多能写成长度为$O(\log b)$的二进制, 因此这个算法就是$O(\log n)$. 在程序设计中是根据b的二进制中是否为1来控制是否乘以上一次翻倍的积 不断右移b, 直到b不再有1： 根据当前位的权重（当前b最后一位）是否为1来决定c是否乘以最新的a 把a平方，用于下一位计算 在Java中要考虑极端值INT_MIN // 递归 public double myPow(double x, int n) { if(n==0) return 1; double temp = myPow(x, n/2); if (n % 2 ==0) return temp * temp; else { if(n > 0) return x*temp*temp; else return (temp*temp) / x; } } // 循环 public double myPow(double x, int n) { double ans = 1; if(n < 0){ n = -(n+1); // 处理极端值 x = 1/x; ans *= x; } System.out.println(n); while (n > 0) { if ((n & 1) == 1) ans *= x; x *= x; n >>= 1; } return ans; } 快速幂取余 求a^b mod c. 如果b是偶数, a^b mod c = $(a^2)^{b/2} \% c$ 如果b是奇数, a^b mod c = $((a^2)^{b/2} \times a) \% c$ ...

“找出只出现一次的数”， “找出唯二的只出现M次的数”， “找出缺失的数”等等这类问题，都可以利用异或操作的特性， 即一个整数和自己进行异或运算会归0的性质。 找出缺失的数字 问题1：给定一个包含n个不同数字的数组，取自0,1,2,...,n，找到数组中缺少的数字。 最直觉的解法是利用等差数列的性质直接数学求解。但这个方法限制于等差数列. 问题2: 在一个长度为n的数组里的所有数字都在0 ~ n-1之间, 数组中有些数字是重复的, 找出任意一个重复的数字. 这也是«剑指offer»的一道题. 但是如果利用数组大小和元素范围的特性, 就可以发现, 这里的数组的大小和数字的范围是有限定关系的. 对于第二个问题, 假如没有重复, 那么重新排列的话数组每一个位置都可以放上自己对应的数字. 对于第一个问题, 假如没有缺失, 那么除了每一个index都可以重新放上自己对应的数字外, 还会多出一个最大的数字没地方放. 这样就可以把数组包含的数字解读为index, 然后在遍历检查数组时, 同时检查以各个数字为index的其他位置的数字. 使用这种思路可以同时解决两个问题, 这里以问题1解法为例: public int missingNumber(int[] nums) { int n = nums.length; int misP = n; // points to the position where misssing. for (int i = 0; i < n; i++) { while (i != nums[i] && nums[i] != misP) { int j = nums[i]; nums[i] = nums[j]; nums[j] = j; } if (nums[i] == misP) misP = i; } return misP; } 找出只出现一次的数 问题3：在一个非空整数数组，找出那个只出现了一次的元素，已知其余每个元素均出现两次。 ...

求两个整数的汉明距离 hamming distance Leetcode 461 两个整数之间的汉明距离是该两个数之间不同的位数。 给定两个整数x和y，计算汉明距离。问题也可以理解为对于两个整数m和n, 需要改变m的二进制多少位才能得到n: /** Use Brian Kernighan's way to count bits */ public int hammingDistance(int x, int y) { x = x ^ y; y = 0; while(x != 0){ y++; x &= x - 1; } return y; } public class Solution { public int hammingDistance(int x, int y) { return Integer.bitCount(x ^ y); } } 同样用到Brian Kernighan算法： ...

不使用加减符号求和整数 不能使用+和-, 仅通过^和&操作来求和两个整数a. 参考 每位相加可能会产生进位(carry), 所以可以把相加拆分为两部分, 如759 + 674可以拆分为不考虑进位的部分323和仅考虑进位的部分1110, 故759 + 674 = 323 + 1110 = 1433. 二进制的加法也是从低位开始逐步往高位计算: 进行一位二进制的加法, 也就是暂不考虑进位的位相加: 0+0=0， 0+1=1, 1+0=1， 1+1=0, 那么就是^操作. 所得的和作为新的a. 求进位: 通过a & b判断是否进位, 因为只有两个位均为1才会进位. 所得的进位左移一位作为新的b. 不断重复这个过程, 把低位的进位传递到高位, 累加到a中, 直到进位为0, 最后得到的a就是答案. public class Solution { public int getSum(int a, int b) { while (b != 0) { // 关键在于判断终止的时机 int c = a & b; //carry a ^= b; //add b = c << 1; } return a; } } 涉及的运算就是一个多位二进制加法真值表：(对应于硬件中的全加器) ...

通过位移实现很多风骚的操作， 参考这个视频。 检查一个数是否是偶数, 本质上就是取最后一位来判断, 如果是1那么就一定是奇数, 反之则为偶数: (x & 1) == 0 Check if power of two: (x & x - 1) == 0 因为如果数x是以2底的真数, 那么其二进制一定只有一个位置是1, 如0b1000, 那么x-1就会变成只有该位置是0其右边所有位变为1, 即0b0111, 也就是说这种情况下x和x-1所有位置都互异. 那么它们的位与运算就是x & x - 1 = 0b0000. x & x - 1的广义用途是求x二进制中1的个数, Counting bits set: unsigned int v; // count the number of bits set in v unsigned int c; // c accumulates the total bits set in v for (c = 0; v; c++) { v &= v - 1; // clear the least significant bit set } Brian Kernighan’s algorithm takes O(log N) to count set bits (1s) in an integer: each iteration sets the least significance bit that isn’t zero to zero - and only it. Since each iteration converts exactly bit from 1 to 0, it’ll take as many iterations as there are non-0 bits to convert all the bits to 0(and thus v == 0 and the loop finishes). An integer n has log(n) bits, hence the worst case is O(log(n)) ...

Knapsack背包问题 背包问题（Knapsack problem）是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。 也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V。 0-1背包 最基础的背包问题：有N件物品和一个体积为V的背包, 每种物品均只有一件, 第i件物品的大小/重量是s[i]，价值是v[i]. 求将哪些物品装入背包可使这些物品的体积总和不超过背包体积，且价值总和最大. 对于每一个物品，只有两种结果，放入或者不放入背包，那么kn(i, j)则表示背包容量剩余j时, 前i个物品能够达到的最大值: kn1 = kn(i-1, j-s(i)) + v(i)表示物品i放入背包后的总价值, 为前i-1物品在第i个物品占用了背包容量s(i)后的的最优解加上第i个物品的价值v(i). kn2 = kn(i-1, j)表示物品i并没有放入背包, 等于前i-1个物品在相同背包容量的最优价值. 归纳出来的大小子问题间的关系(转移方程)为: kn(i, j) = max(kn1, kn2) = max(kn(i-1, j-s(i)) + v(i), kn(i-1, j)). 初始状态是对于不同背包剩余容量, 当没有物品可放时, 返回的最大价值一定是0. 所以背包问题, 就是二维的动态规划问题. 需要确定初始状态, 和哪些信息需要记忆. 可以简单地用一个二维数组记忆所有kn(i, j), 但要考虑到当容量非常大, 物品非常多时, 这个二维数组是很大的, 比如当(i, j) = (2000, 2000000), 会抛出java.lang.OutOfMemoryError: Java heap space. 特别是, 当每个物品的价值也比较大时, 二维数组的j维度其实利用率很低. 所以存在很多优化的空间. 优化的关键点在于减少记忆点. 注意到转移方程中: kn(i, *)只需要用到kn(i-1, *)的值, 但我们又清楚地知道，物品在这里是没有顺序的意义的，所以这里的i仅仅是表示迭代的步骤, 只是为了遍历所有物品, 至于具体的顺序是不重要的, 所以不需要记录所有i对应的kn(i, *), 仅仅记录最近一次计算值即可. 所以我们只需要至多两个数组用来记录i-1和i对应的kn值. kn(i, j)要用到kn(i-1, k), k<=j的值, 具体要用到哪些k是取决于i. 所以j维度的值必须都要记录下来, 以防后续需要用到. 结合起来发现只需要一个一维数组kn = new int[size + 1]即可, i对应的值可以直接在数组上更新, 不需要额外的数组记录上一次迭代的值. 在实现中, 因为kn(i, j)要用到kn(i-1, <=j)的值, 也就是kn[<j]的值不能先于kn[j]更新, 所以kn的计算要从右往左(j = size; j--). 每次决定是否加入i物品之前, 如果剩余容量j小于s[i], 那么肯定无法放入, 这个判断可以融合进j的遍历中, 因为j本身代表了剩余容量. static int[] values; static int[] sizes; public static int knapsack(int size) { int n = values.length; int[] vs = new int[size + 1]; for (int i = 0; i < n; i++) { // items for (int j = size; j >= sizes[i]; j--) { vs[j] = Math.max(vs[j - sizes[i]] + values[i], vs[j]); } } return vs[size]; } 优化以后空间复杂度由$\theta(NS)$降到$\theta(S)$。但时间复杂度不变. ...