Algorithms

跳台阶 跳上一个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...

在很多语言中，字符char类型是八位, 那么可能取值有256种(-128 ~ -1, 0 ~ 127). 但是用二进制表示为0000 0000 ~ 1111 1111, 无符号整数的全部位都表示数值，而有符号数的最高位是符号位（0表示正数，1表示负数），所以实际表达数值的只剩下n-1位。这样理论上char的取值应该是1111 1111 = -127到0111 1111 = 127. 而-128 = 1 1000 0000需要9位来表达, 所以char是如何仅仅通过八位表达-128? 首先, 因为计算机只能做加法, 所以减法操作要转化为加法, 尝试将符号位参与运算, 1-1就转化为1 + (-1), 用二进制表达为0000 0001 + 1000 0001 = -2, 很明显是错的. 如果用原码表示, 让符号位也参与计算, 显然对于减法来说, 结果是不正确的. 这也就是为何计算机内部不使用原码表示一个数. 为了避免这种错误, 引入反码(正数的反码是其本身, 负数的反码是符号位不变, 其余位取反), 用-1的原码1000 0001的反码1111 1110来表达-1, 这样1 + (-1) = [0000 0001]反 + [1111 1110]反 = [1111 1111]反, 转为原码1000 0000 = -0. 发现用反码计算减法, 结果的真值部分是正确的....