首页 > 试题广场 >

0左边必有1的二进制字符串的数量

[编程题]0左边必有1的二进制字符串的数量
  • 热度指数：1553 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个整数n，求由“0”字符和“1”字符组成的长度为n的所有字符串中，满足“0”字符的左边必有“1”字符的字符串的数量。

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


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

输入

1

输出

1

说明

只有“1”满足
示例2

输入

2

输出

2

说明

只有“10”和“11”满足
示例3

输入

3

输出

3

说明

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

备注:
时间复杂度。额外空间复杂度。
算法知识视频讲解
添加回答
Java
together"头像 together"

设f(i)表示长度为i的【0左边必有1的二进制字符串的数量】：

  • 先确定第一个字符，显然首个字符必须为1（如果为0则左边没有1给它靠了），所以f(1) = 1；
  • 第二个字符既可以为0也可以为1，即10和11两个，所以f(2) = 2；
  • 如果第二个字符选了0（即前两位是10），那么第三个字符只能是1即101（因为0的左边必须紧挨着一个1，所以没得选）；如果第二个字符选了1（即前两位是11），那么第三个字符既可以是0也可以是1（110或111），所以f(3) = 1+2 = 3；
  • 遵循这种规则做下去，你会发现f(i)总是等于f(i-1) + f(i-2)，也就是典型的斐波那契数列了，只不过这里f(1) = 1，f(2) = 2。搞懂了这个逻辑，编码就是水到渠成了。 
import java.util.Scanner;

public class Main {

    public static final int MOD = 1 << 29;

    public static void main(String[] args) {
        int n = new Scanner(System.in).nextInt();
        System.out.println(getCount(n));
    }

    public static int getCount(int n) {
        if (n <= 2) {
            return n;
        }
        int a = 1, b = 2; // f(1) = 1, f(2) = 2

        for (int i = 3; i <= n; i++) {
            int tmp = (a + b) % MOD;
            a = b;
            b = tmp;
        }
        return b;
    }
}


发表于 2022-02-15 09:14:55 回复(0)
提交观点

问题信息

动态规划 字符串 数学 基础数学
上传者：小小
难度：
1条回答 7593浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号