/ 注册

首页 > 试题广场 > 0左边必有1的二进制字符串的数量

[编程题]0左边必有1的二进制字符串的数量

热度指数：632 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个整数n，求由“0”字符和“1”字符组成的长度为n的所有字符串中，满足“0”字符的左边必有“1”字符的字符串的数量。

输入描述:

输入一行，包含一个整数n。

输出描述:

输出一个整数，表示返回的答案，由于字符串的数量巨大，可能会溢出，请输出对取模后的答案。

示例1

输入

输出

说明

只有“1”满足

示例2

输入

输出

说明

只有“10”和“11”满足

示例3

输入

输出

说明

只有“101”，“110”，“111”满足

备注:

时间复杂度。额外空间复杂度。

算法知识视频讲解

谢谢今天

#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
long long dp1=1;//末尾为1满足条件数量
long long dp2=0;//末尾为0满足条件数量
for(int i=1;i<n;i++)
{
long long temp=dp1;
dp1=(dp1+dp2)%(1<<29);
dp2=temp;
}
cout<<(dp1+dp2)%(1<<29)<<endl;
}

发表于 2021-01-04 20:45:19 回复(0)

一只老风铃

讨论末尾为0或者为1，时满足条件的数量，由于第k次计算只会使用k-1计算结果。

#include<iostream>
using namespace std;
int main()
{ 
   int n;
   cin>>n;
   long long dp1=1;//末尾为1满足条件数量
   long long dp2=0;//末尾为0满足条件数量
   for(int i=1;i<n;i++)
   {
       long long temp=dp1;
       dp1=(dp1+dp2)%(1<<29);
       dp2=temp;
   } 
    cout<<(dp1+dp2)%(1<<29)<<endl;    
}

发表于 2021-01-04 14:11:49 回复(0)