一道Google算法题:n位编码的海明码生成

[oneleaf]

来源： http://www.blogjava.net/copydogcn/archi ... 94256.html

写一个算法生成n位编码的编码串（结果有多种，任意一种都可以接受）并且符合如下条件：相邻的两个编码之间有且只能有一位不同，并给出时间与空间复杂度

比如 2位的二进制的编码生成的编码串：00 01 11 10
比如 3位的二进制编码生成的编码串：001 011 111 101 100 110 010 000

[异域追梦者]

什么是时间与空间复杂度?

[lslove]

这个题有点意思

[林葭一]

递规

代码： 全选

public class HaiMingBin {

	public HaiMingBin() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		HaiMingBin hm = new HaiMingBin();
		int time = 13;
		int m = exp(2, time);
		System.out.println(m);
		int[] arr = new int[m];
		hm.calc(arr, time);
		for (int i = 0; i < m; i++) {
			System.out.println(cvtBinNum(arr[i], time));
		}
	}

	public void calc(int[] arr, int time) {
		if (time == 0) {
			arr[0] = 0;
			return;
		}
		int m = exp(2, time);
		calc(arr, time - 1);
		for (int i = 0; i < m / 2; i++) {
			arr[m - 1 - i] = (m / 2) | arr[i];
		}
	}

	public static int exp(int num, int time) {
		int k = 1;
		int t = time;
		while (t-- > 0) {
			k *= num;
		}
		return k;
	}

	public static String cvtBinNum(int num, int digit) {
		StringBuffer sb = new StringBuffer();
		for (int i = digit - 1; i >= 0; i--) {
			if ((exp(2, i) & num) != 0) {
				sb.append('1');
			} else {
				sb.append('0');
			}
		}
		return sb.toString();
	}

}

[BigSnake.NET]

忘记了, 2007NORP初赛倒数第二题

[BigSnake.NET]

代码： 全选

#!/usr/bin/python
import sys, string

def Genhm(n):
    if n <= 0 :
        yield ''
    else:
        tmp = []
        for i in Genhm(n-1):
            yield '0' + i
            tmp.append(i)
        while tmp : # is not empty
            yield '1' + tmp.pop()

if '__main__' == __name__ :
    print sys.argv[1]
    for i in Genhm(string.atoi(sys.argv[1])):
        print i

生成器能反转用吗, 现在只好用一个stack了..

时 O(2^n) 空 O(2^n)

[BigSnake.NET]

时间测试

代码： 全选

n       用时
1       0.00s
2       0.00s
3       0.01s
4       0.00s
5       0.00s
6       0.00s
7       0.01s
8       0.01s
9       0.00s
10      0.00s
11      0.01s
12      0.01s
13      0.02s
14      0.03s
15      0.05s
16      0.10s
17      0.20s
18      0.38s
19      0.78s
20      1.57s
21      3.05s
22      5.93s
23      11.81s
24      24.08s
25      48.22s

[vipzhicheng]

PHP语言解法

代码： 全选

function go($n)
{
    if (!is_int($n) || $n < 1) return;
    if ($n-- == 1) return array('0', '1');
    return array_merge(array_map(create_function('$item', 'return "0" . $item;'), go($n)), array_map(create_function('$item', 'return "1" . $item;'), array_reverse(go($n))));
 
}
print_r(go(4));

[ptpt52]

代码： 全选

1位
real	0m0.040s
user	0m0.020s
sys	0m0.004s

2位
real	0m0.041s
user	0m0.024s
sys	0m0.004s

3位
real	0m0.039s
user	0m0.016s
sys	0m0.012s

4位
real	0m0.041s
user	0m0.024s
sys	0m0.000s

5位
real	0m0.042s
user	0m0.020s
sys	0m0.008s

6位
real	0m0.039s
user	0m0.028s
sys	0m0.004s

7位
real	0m0.039s
user	0m0.020s
sys	0m0.012s

8位
real	0m0.059s
user	0m0.016s
sys	0m0.012s

9位
real	0m0.039s
user	0m0.016s
sys	0m0.016s

10位
real	0m0.040s
user	0m0.024s
sys	0m0.004s

11位
real	0m0.045s
user	0m0.028s
sys	0m0.000s

12位
real	0m0.048s
user	0m0.024s
sys	0m0.012s

13位
real	0m0.056s
user	0m0.036s
sys	0m0.004s

14位
real	0m0.076s
user	0m0.044s
sys	0m0.012s

15位
real	0m0.110s
user	0m0.084s
sys	0m0.008s

16位
real	0m0.183s
user	0m0.160s
sys	0m0.004s

[mir_lww]

支持递归～～～

代码： 全选

public class GenHammingCode {

	private static Boolean isAppendLeft;

	public String[] gen(final Integer bitCount) {
		if (bitCount == 1)
			return new String[] { "0", "1" };
		String[] result = new String[2 << bitCount - 1];
		String[] temp = gen(bitCount - 1);
		isAppendLeft = new Random().nextBoolean();
		for (int i = 0; i < temp.length; i++) {
			result[i] = append(temp[i], "0", isAppendLeft);
			result[result.length - 1 - i] = append(temp[i], "1", isAppendLeft);
		}
		return result;
	}

	private String append(String src, String appendStr, Boolean isAppendLeft) {
		return isAppendLeft ? appendStr + src : src + appendStr;
	}

	public static void main(String[] args) {
		System.out.println(Arrays.deepToString(new GenHammingCode().gen(3)));
	}
}

[guyuhao088]

忘记了, 2007NORP初赛倒数第二题

NOIP2007提高组初赛
格雷码- -
挺经典的一道题= =

[ShingRay]

binary Gray code

代码： 全选

#!/usr/bin/env python

for i in xrange(1 << input()):
	print('%d ' % (i ^ i >> 1))