`

Hedvig Interview - Count of number with no consecutive 1's

 
阅读更多

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, valid strings are 00, 01, 10. You should return 3.

 

假设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 static int noConsucetive1(int n) {
	if(n <= 0) return 0;
	int[] f1 = new int[n+1];
	int[] f0 = new int[n+1];
	f0[1] = f1[1] = 1;
	for(int i=2; i<=n; i++) {
		f0[i] = f0[i-1] + f1[i-1];
		f1[i] = f0[i-1];
	}
	return f0[n]+f1[n];
}

 

public static int noConsucetive1(int n) {
	if(n <= 0) return 0;
	int[] f = new int[n+1];
	f[0] = 1; f[1] = 2;
	for(int i=2; i<=n; i++) {
		f[i] = f[i-1] + f[i-2];
	}
	return f[n];
}

 

分享到:
评论

相关推荐

    labyrinths-of-hedvig:VPG项目

    1. **Pascal语言基础**: Pascal是一种结构化编程语言,它强调程序的清晰性和可读性。在《海德维格迷宫》中,开发者利用Pascal的变量、常量、数据类型、控制结构(如循环和条件语句)、函数和过程等基本概念来编写...

    rapio:与Hedvig的融合

    与Hedvig的整合 价格对比 创建比较: https:/xxxx/v1/quote签署报价: https://xxxx/v1/quote/{quote_id}/sign 建立要求 request_id String product_type String ='HOME' quote_data personal_number String ...

    labirynth:终极游戏 Hedvig 的迷宫

    迷路 终极游戏开发商 Hedvig Labirynth:Veres Péter Gimnázium 的学生(匈牙利,布达佩斯) 请阅读 LICENSE.md! (如果您不会阅读:CC-BY-NC-SA)

    back-office:Hedvigs主要后台服务

    H.OPE:Hedvig OPErations,后端 开发 不幸的是,GitHub Packages需要一个github令牌才能下载一些共享的Hedvig库。 使用write:packages访问权限创建一个GitHub dev令牌。 然后像下面这样在本地~/.m2/settings.xml ...

    ugglan:这只是iOS的保险应用

    Hedvig是目前在瑞典和挪威可用的一种新的保险方式,我们以透明为生,因此我们将代码公开并在Github上发布我们的所有源代码,如果您有兴趣与我们合作,请随时来看看退出我们的。 乌兰 :owl: 这只是iOS的保险应用 ...

    underwriter:报价,承销指南等服务

    不幸的是,GitHub Packages需要一个github令牌才能下载一些共享的Hedvig库。 使用write:packages访问权限创建一个GitHub dev令牌。 然后像下面这样在本地~/.m2/settings.xml : &lt; settings xmlns = " ...

    dorigo开山之作

    报告主要由瑞典国防研究署(FOI)出版,作者包括Pontus Svenson、Christian Mårtenson、Hedvig Sidenbladh和Michael Malm等人。这份报告重点介绍了群体智能(Swarm Intelligence, SI)的基本概念及其在网络化防御中...

    NVIDIA将GPU虚拟化引入人工智能和数据科学领域.pdf

    在内容部分,还提到了Commvault收购Hedvig的事件,这笔交易标志着Commvault开始进军软件定义存储(SDS)市场,进一步强化了其在数据管理领域的实力。这表明存储和数据管理解决方案对于当前的数字化转型至关重要,它...

Global site tag (gtag.js) - Google Analytics