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....

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], 结果不匹配....

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....

如何实现快速的幂运算？ 要求$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....

“找出只出现一次的数”， “找出唯二的只出现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算法： Lets say that the bit at index n is 1 and that the bits in indexes 0 up to n-1 are all 0 (we’ll use little endianess - so index 0 is 1, index 1 is 2, index 2 is 4, index 3 is 8 and so on)....

不使用加减符号求和整数 不能使用+和-, 仅通过^和&操作来求和两个整数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....

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, *), 仅仅记录最近一次计算值即可....