Hedvig 1st Phone Interview

1. Given integer n, find the number of different binary strings of size n where there are no consecutive 1's.Eg: If n is 2

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式

Product of Array Exclude Itself

假设f(n, k)是第n位上为k的数字的个数

无论第n-1位是0还是1，第n位都能取0，故有：
f(n, 0) = f(n-1, 0) + f(n-1, 1)

而只有在第n-1位取0时，第n位才能取1，即：
f(n, 1) = f(n-1, 0)

n位bit能表示的数目总和是：
f(n) = f(n, 0) + f(n, 1) = [f(n-1, 0) + f(n-1, 1)] + f(n-1, 0) = f(n-1) + [f(n-2, 0) + f(n-2, 1)] = f(n-1) + f(n-2)

所以，f(n)就是一个Fibonacci数。简单迭代即可得到。

第一题是数学题吧....有什么好思路么

全部 - 连续的?

public int find(int n) {
        return (int)Math.pow(2,n) - (n-1)*(n) / 2;
    }

readman 发表于 2015-7-10 10:35
public int find(int n) {
        return (int)Math.pow(2,n) - (n-1)*(n) / 2;
    }

这个方法不行的。比如当n = 4时，总共有
0000
0001
0010
0100
1000
0101
1010
1001
8种情况。

而这个代码给出的结果则是2^4 - 3*4/2 = 16 - 6 = 10

stellari 发表于 2015-7-9 23:13
假设f(n, k)是第n位上为k的数字的个数

无论第n-1位是0还是1，第n位都能取0，故有：

赞！我没发现是Fibonacci

stellari 发表于 2015-7-10 12:15
这个方法不行的。比如当n = 4时，总共有
0000
0001

恩,            

stellari 发表于 2015-7-10 12:13
假设f(n, k)是第n位上为k的数字的个数

无论第n-1位是0还是1，第n位都能取0，故有：

机智！

简单说来就是，已经有n-1长度，往后加个0，可以随便加。
往后加个1的话，必须最后一位是0，而末尾为0的数，是在再前一轮随便+0产生的，所以是f(n-2).
f(n) = f(n-1) + f(n-2)

楼主多久会有消息？