首页 > 试题广场 >

寻找 520

[编程题]寻找 520
  • 热度指数：396 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个字符串s，里面全都是由 '5'、'2' 和 '0' 组成，这个字符串内总计有 520 个为 "520" 的子序列。现在字符串中将某些部分换成‘？‘，再将'?'部分换成 '5'、'2' 和 '0'，在所有可能的字符串中，位置不同的为 "520" 的子序列共有多少个？答案会很大，所以请你模 998244353 返回

示例1

输入

"552200"

输出

8

说明

显然，这个字符串共有 8 个子序列为 520。
示例2

输入

"5?0"

输出

1

说明

把中间这个 ? 替换为 2 后我们得到一个子序列为 520，其他情况均没有 520。
示例3

输入

"5?2?0"

输出

8
示例4

输入

"?????"

输出

10

备注:
某个字符串的子序列指的是去掉这个字符串中一些字符并保持剩下的字符相对顺序不变的情况下得到的序列。如 "ace" 和 "abc" 都是 "abcde" 的子序列。

数据范围：
- 20% 的数据满足 , '?' 的总数量不超过 5 个，|S| 表示字符串 S 的长度，下同。
- 50% 的数据满足 , '?' 的总数量不超过 5 个。
- 100% 的数据满足 , ’?‘ 总数量无限制。
算法知识视频讲解
添加回答
heyJulian头像 heyJulian 
/**
 * 寻找所有的 520 子序列
 * @param S string字符串 牛牛准备的数字字符串
 * @return int整型
 */
int findOccurrences(char* S ) {
    // write code here
    int sum5 = 0, sum2 = 0, sum0 = 0,i;
    for(i = 0; i < strlen(S); i++){
        switch(S[i]){
            case '5':
                sum5++;
                break;
            case '2':
                sum2 = (sum5 + sum2) % 998244353;
                break;
            case '0':
                sum0 = (sum2 + sum0) % 998244353;
                break;
            case '?':
                sum0 = (sum2 + sum0) % 998244353;
                sum2 = (sum5 + sum2) % 998244353;
                sum5++;
                break;
        }
    }
    return sum0;
}

发表于 2020-07-24 13:47:29 回复(0)
冷潇、头像 冷潇、
没看懂。。
发表于 2020-12-03 09:13:25 回复(0)
一只老风铃头像 一只老风铃
拿字符串作礼物，牛牛你是真的浪漫啊！
发表于 2020-09-27 00:22:57 回复(0)
提交观点

问题信息

字符串 基础数学
难度：
3条回答 2044浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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