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

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

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

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

输入描述:

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

输出描述:

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

示例1

输入

输出

说明

只有“1”满足

示例2

输入

输出

说明

只有“10”和“11”满足

示例3

输入

输出

说明

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

备注:

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

算法知识视频讲解

helloxuanbao

#include <stdio.h>

#define MOD 0x20000000

int main(void) {
    int n;
    scanf("%d", &n);
    if (n == 1) {
        printf("%d\n", 1);
        return 0;
    }
    int next1 = 2, next2 = 1, tmp;
    n -= 2;
    while (n-- > 0) {
        tmp = (next1 + next2) % MOD;
        next2 = next1;
        next1 = tmp;
    }
    printf("%d\n", next1);
    return 0;
}

发表于 2022-02-11 17:09:40 回复(0)