Posts

求两个整数的汉明距离 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, *), 仅仅记录最近一次计算值即可....

跳台阶 跳上一个n级的台阶总共有多少种跳法，先后次序不同算不同的结果，限制条件是每次只能跳1级或者2级。 抽象出来的模型是：给定正整数N，有多少种累加方案，不同顺序当做不同方案，限制条件可以是给定的整数$n_0, n_1, …, n_k$作为可选累加元素. 对于限制条件为只有两种跳法, 即1阶或者2阶的, 问题可以分解为: 假定第一次跳的是1阶，那么就剩下n-1个台阶，剩余跳法是f(n-1); 假定第一次跳的是2阶，则剩下n-2个台阶，剩余跳法是f(n-2) 可以归纳出通用的公式: f(n) = f(n-1) + f(n-2), 只有一阶的时候f(1) = 1, 只有两阶的时候可以有f(2) = 2, 刚好就是斐波那契数列. 所以这个简单的跳台阶问题就是计算斐波那契数列的问题。 反过来思考, 比如对于8个台阶, 有多少种回滚方案? 只有两种: 回滚1个台阶, 就到了7; 回滚2个台阶, 就到了6. 等于说: 假如有f(7)种方案跳到7, 有f(6)种方案跳到6，那么就有f(7) + f(6)种方案到达8 从树结构来理解: 如果节点代表台阶数n对应的跳法f(n), 节点与节点间的枝代表单次可以跳的阶数, 父节点的值就是其所有子节点的值和. 对于只有两种跳法限制问题, 父节点f(n)就只有两个子节点, 分别为f(n-1)和f(n-2). 斐波那契数列 举例：Fibonacci sequence: ${\displaystyle 0,;1,;1,;2,;3,;5,;8,;13,;21,;34,;55,;89,;144,;\ldots }$ $$F_0 = 0, F_1 = 1, F_2 = 1, F_n = F_{n-1} + F_{n-2} (n>2) $$ Fibonacci numbers grow almost as fast as the powers of 2....

丑数 把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。 要判断一个数是不是丑数, 不断地分别除以2, 3, 5，然后检查num是否到达1: public boolean isUgly(int num) { //(除数包括`4`可以让代码更简洁) for (int i=2; i<6 && num>0; i++) while (num % i == 0) num /= i; return num == 1; } 如果要返回第n个丑数(leetcode原题), 情况就稍微复杂点. 从动态规划的角度考虑, 对于一个较大的丑数N, 必定是由某个更小的丑数M乘以2, 3, 5其中一个得来的. 所以可以从小到大不断生成丑数. 为了避免在循环中每一次计算都从头开始检查每一个数k对应的2*k, 3*k, 5*k, 需要用三个变量last2, last3, last5来分别记录最近一次用到的丑数的索引, 下一次计算时就直接从上一次停止的地方开始运行. /** return the nth ugly number */ public static int unglyNumber(int n) { final int INIT = 5; int[] uglys = new int[n + INIT]; for (int i = 0; i < 5;) { uglys[i] = ++i; } int last2, last3, last5, m2, m3, m5; last2 = last3 = last5 = 0; m2 = m3 = m5 = 1; for (int i = INIT; i < n; i++) { for (int j = last2 + 1; j < i; j++) { if (m2 <= uglys[i - 1] && uglys[j] * 2 > uglys[i - 1]) { m2 = uglys[j] * 2; last2 = j; } } for (int j = last3 + 1; j < i; j++) { if (m3 <= uglys[i - 1] && uglys[j] * 3 > uglys[i - 1]) { m3 = uglys[j] * 3; last3 = j; } } for (int j = last5 + 1; j < i; j++) { if (m5 <= uglys[i - 1] && uglys[j] * 5 > uglys[i - 1]) { m5 = uglys[j] * 5; last5 = j; } } uglys[i] = Math....

最长公共子序列 对于一个字符串, 它的子序列，就是将给字符串中任意个元素去掉之后剩余的字符串, 所以子序列不要求是连续的, 但是维持原来的顺序. 在文本相似度比较中，常用到最长公共子序列（longest common sequence）。 同时遍历两个字符串, 如果x[i] == y[j], 则x[i]和y[j]参与了最长公共子序列z[k]的构建. 如果用lcs[i, j]表示遍历到x[0-i]和y[0-j]时的LCS长度, 那么现在就需要判断x[i]和y[j]的关系, 分两种情况: 如果二者相等, 那么lcs1 = lcs[i - 1, j - 1] + 1 若不相等, 那么只能在x和y中选择一个进行推进, 选择依据就是取较大值, lcs2 = max(lcs[i - 1, j], lcs[i, j - 1]) 初始状态自然是lcs[0, 0] = 0. static int[][] lcs; public static int longestCS(String x, String y) { char[] xList = x.toCharArray(); char[] yList = y.toCharArray(); for (int i = 1; i <= xList....

最大子序列 Maximum subarray problem: In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6. The problem was first posed by Ulf Grenander of Brown University in 1977, as a simplified model for maximum likelihood estimation of patterns in digitized images....

我们已经看到了一些优雅的设计原则，例如分而治之，图探索和贪婪的选择，它们为各种重要的计算任务提供了确定的算法。这些工具的缺点是只能用于非常特定类型的问题。现在我们来谈谈算法工艺的两个大锤，即动态编程和线性编程，这两种适用性非常广泛的技术可以在更专门的方法失败时调用。可以预见的是，这种普遍性通常会带来效率上的损失。 很多经典的方法，如 divide-and-conquer, graph exploration, and greedy等, 为各种重要的计算任务提供了确定性的解法。但是这些算法只能用于特定类型的问题。 这里介绍两个算法大杀器: Dynamic programing 和 linear programming. 这两种适用性非常广的算法可以在黔驴技穷时考虑调用（如 the knapsack problem, sequence alignment, and optimal binary search trees）。当然，普遍性往往会带来效率上的损失。 动态规划 动态规划作为一种编程范例，可以从一个例子着手理解：求数列的 maximum-weighted independent sets (MIS, 最大非连续非相邻子集)和, 对于a = [1, 4, 5, 4], 其MIS为{a[1], a[3]} = 8. 如果使用贪心法, 每次都在可选范围内取最大值, 那么就会得到{a[2], a[0]} = 6. 如果使用分而治之法, 把数组分为两半a1 = [1, 4], a2 = [5, 4], 则分别得到MIS{a1[1]}, {a2[0]}, 合并后发现是相邻的, 与要求相悖. 要解决这个问题，关键的步骤是找到基于子问题最优解的最优解：想办法把缩小最优解备选方案的数量，在这个较小的空间中可以直接采取暴力搜索寻找最优解。 对于a = [1, 4, 5, 4], 假设其MIS为S, 假如从最右边的元素开始考虑, a[3] = 4只有属于S和不属于S两种情况...

一些常规的操作， 参考这个视频。 基本位操作 把某一位变为1： def set_bit(x, position): mask = 1 << position return x | mask bin(set_bit(0b110, 0b101)) 输出0b100110. 因为x = 0b110 = 6, 翻转第五位，就用position = 0b101 = 5， 得到mask = 0b00100000, 用|把第五位变为1. 清除某一位（1变0)： def clear_bit(x, position): mask = 1 << position return x & ~mask 通过XOR^和1来翻转某一位： def flip_bit(x, position): mask = 1 << position return x ^ mask 通过&1可以作为取位操作, 来判断某一位是否是1: def is_bit_set(x, position): shifted = x >> position return shifted & 1 0b1100110 >> 0b101 = 0b11, 0b11 & 0b01 = 1...