Java

The Line Patterns Recognition A basic but important application of pattern recognition is to recognize line patterns in a given set of points. http://coursera.cs.princeton.edu/algs4/assignments/collinear.html. This blog will give a breif introduction to this problem and provide an enfficient solution. Codes available in algs4/collinear/src/ The problem could be described as: Given a set of n distinct points in the plane, find every (maximal) line segment that connects a subset of 4 or more of the points....

This blog explains an apllication of randomized queue algorithms. Permutation client memory challenge A client program Permutation.java that takes an integer k as a command-line argument; reads in a sequence of strings from standard input using StdIn.readString(); and prints exactly k of them, uniformly at random. Print each item from the sequence at most once. More detail could be found at programming assignment specification and checklist, codes available in algs4/queues/src/....

Union-find applications: Percolation Problem discriptions Percolation data type. To model a percolation system, create a data type Percolation with the following API: public class Percolation { public Percolation(int n); // create n-by-n grid, with all sites blocked public void open(int row, int col); // open site (row, col) if it is not open already public boolean isOpen(int row, int col); // is site (row, col) open? public boolean isFull(int row, int col); // is site (row, col) full?...

Algorithms, Part I, https://online.princeton.edu/course/algorithms-part-i Algorithms, Part II, https://online.princeton.edu/course/algorithms-part-ii Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne https://algs4.cs.princeton.edu/ Union−Find Considering the dynamic connectivity problem, modeling of multiple objects connected in a space/network. Applications involve manipulating objects of all types. ・Pixels in a digital photo. ・Computers in a network. ・Friends in a social network. ・Transistors in a computer chip. Given a set of N objects. union(a, b): connect two objects. connected(p, q): is two objects connected?...

Bit Map Bit-map用一个bit位来标记某个元素对应的Value， 而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。 假设我们要对0-7内的5个元素4,7,2,5,3排序（假设这些元素没有重复）。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数，我们就只需要8个Bit（1Bytes）， 首先我们开辟1Byte的空间，将这些空间的所有Bit位都置为0，0 0 0 0 0 0 0 0. 然后遍历这5个元素，首先第一个元素是4，那么就把4对应的位置设为1, p+(i/8)|(0x01<<(i%8)), 这里默认为Big-ending, 0 0 0 0 1 0 0 0. 然后再处理第二个元素7，将第八位置为1,，接着再处理第三个元素，一直到最后处理完所有的元素，将相应的位置为1，这时候的内存的Bit位的状态0 0 1 1 1 1 0 1 遍历一遍Bit区域，把1的索引依次输出（2，3，4，5，7），这样就达到了排序的目的。 算法的关键是如何确定十进制的数映射到二进制bit位的map图。算法占用很少内存，比如N=10000000；只需占用内存为N/8=1250000Byte=1.25M。缺点是不能有重复数据。 Map映射表 假设需要排序或者查找的总数N=10000000，那么我们需要申请内存空间的大小为int a[1 + N/32]，其中：a[0]在内存中占32位, 可以对应十进制数0-31，依次类推： bitmap表为： a[0]--------->0-31 a[1]--------->32-63 a[2]--------->64-95 a[3]--------->96-127 .......... 十进制数需要转换为对应的bit位 位移转换 将十进制数转换为对应的bit位, 申请一个int一维数组，作为32列的二维数组， int a[0] |0000000000000000000000000000000000000| int a[1] |0000000000000000000000000000000000000| ……………… int a[N] |0000000000000000000000000000000000000| 例如十进制0，对应在a[0]第一位： 00000000000000000000000000000001 求十进制0-N对应在数组a的索引：十进制0-31，对应a[0]，先由十进制数n转换为与32的余可转化为对应在数组a中的索引0。比如n=24,那么 n/32=0，则24对应a[0]。又比如n=60, 那么n/32=1，则60对应a[1]。 求0-N对应0-31中的数：十进制0-31就对应0-31，而32-63则对应也是0-31，即给定一个数n可以通过模32求得对应0-31中的数。 利用移位0-31使得对应32bit位为1. 找到对应0-31的数为M, 左移M位：即2 ^ M, 置1....

数组中有一个数字出现的次数超过数组长度的一半，例如输入一个长度为9的数组1,2,3,2,2,2,5,4,2。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。因为这个数出现次数超过了数组长度一半以上, 那么它就是数组中出现次数最多的数, 故谓之众数. class Solution: def MoreThanHalfNum_Solution(self, numbers): # write code here most = numbers[0] count = 1 for item in numbers: if item == most: count += 1 else: count -= 1 if count < 0: most = item count = 1 return 0 if numbers.count(most) <= len(numbers) / 2 else most 众数问题 众数问题可以推广泛化：给定大小为n的整数数组，找到所有出现超过n / m次的元素。这种问题可以使用 Boyer-Moore 算法解决. The Boyer–Moore majority vote algorithm is an algorithm for finding the majority of a sequence of elements using linear time and constant space....

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