首页 > 试题广场 >

好多牛牛

[编程题]好多牛牛
  • 热度指数：1826 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给出一个字符串S，牛牛想知道这个字符串有多少个子序列等于"niuniu"
子序列可以通过在原串上删除任意个字符(包括0个字符和全部字符)得到。
为了防止答案过大，答案对1e9+7取模
示例1

输入

"niuniniu"

输出

3

说明

删除第4，5个字符可以得到"niuniu"
删除第5，6个字符可以得到"niuniu"
删除第6，7个字符可以得到"niuniu"

备注:
算法知识视频讲解
开通博客
头像 LQstoic
发表于 2021-10-15 19:05:05
关键:f[i][j]这个数组表示改造字符串前i个字符使其与niuniu这个字符串前j个相同的个数。则最终的结果就是f[n][6],即s前n个字符共可以改造几次得到niuniu这个字符串。 初始化 for(int i=0;i<=n;i++) { f[i][0] 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 降龙尊者
发表于 2020-08-26 11:26:18
参考 这篇csdn博客 dp数组 int[][] dp = new int[s.length][pattern.length] 含义 dp[i][j] 表示从 目标s[0:i +1] 中 序列pattern[0:j +1] 的 出现次数 递推公式 dp[i][j] = dp[i-1][j] 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Peterliang
发表于 2021-10-11 00:33:47
NC557 题解 | #好多牛牛# 题意分析 给出一个字符串，需要找出里面"niuniu""niuniu""niuniu"这个字序列的数量。子序列可以通过在原串上删除任意个字符(包括0个字符和全部字符)得到 思路分析 这里，我介绍两种空间优化的方法 解法一 动态规划 + 滚动数组 我们先定 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 May_HanaJung
发表于 2021-07-03 16:19:49
确定dp数组（dp table）以及下标的含义dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。 确定递推公式这一类问题，基本是要分析两种情况 s[i - 1] 与 t[j - 1]相等s[i - 1] 与 t[j - 1] 不相等当s[i - 1] 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 SandMonth
发表于 2021-09-14 19:54:59
好多牛牛 给出一个字符串S，牛牛想知道这个字符串有多少个子序列等于"niuniu"子序列可以通过在原串上删除任意个字符(包括0个字符和全部字符)得到。为了防止答案过大，答案对1e9+7取模 案例输入："niuniniu"返回值：3说明：删除第4，5个字符 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 xqxls
发表于 2021-08-17 12:27:04
题意整理 给定一个字符串S。 求S中有多少子序列等于"niuniu"。 方法一（动态规划） 1.解题思路 假设长度为i-1的字符串s包含N个长度为j的字符串t（"niuniu"）的子序列。如果s的第i个字符不等于t的第j个字符，那么当前状态必定等于前一个状 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 CroMarmot
发表于 2021-09-30 17:38:13
题意 长度为nnn的字符串中，有多少个子串为niuniu 其中 n≤105n\leq 10^{5}n≤105 对结果模1e9+71e9+71e9+7 算法 深度搜索 dfs(stringidx,niuniuidx) 深度搜索函数，接受当前搜索到的字符串的长度的下标，和niuniu当前匹配到的下标 每 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 摸鱼学大师
发表于 2021-08-11 17:23:26
思路： 题目的主要信息： 从字符串s的子序列中找到等于"niuniu"的子序列数 子序列即原串的删去任意个字符（包括0和全部） 字符串s长度默认不小于10，结果需取模1e9+7 方法一：动态规划具体做法：我们用表示以i-1为结尾的s子序列中出现以j-1为结尾的字符串t的个数， 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划 字符串
难度：
10条回答 4014浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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