首页 > 试题广场 >

好多牛牛

[编程题]好多牛牛
  • 热度指数: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"

备注:
  • 考虑通用的问题,给定一个字符串S和模式串T,求S中有多少个子序列=T。

  • 设dp[i+1][j+1]表示串S[0,i]中有多少个子序列=T[0,j]。那么状态转移方程为:
  • 若S[i] != T[j],那么dp[i+1][j+1] = dp[i][j+1] ,表示S[0,i-1]中T[0,j]出现的次数。
  • S[i] == T[j],那么dp[i+1][j+1] = dp[i][j+1] + dp[i][j],除了包含S[0,i-1]中T[0,j]出现的次数,由于S[i]==T[j],那么若S[0,i-1]==T[0,j-1],那么会有新的T[0,j]匹配,次数即dp[i][j]。
  • 注意到上述转移方程中,第一维中,dp[i+1]只和dp[i]有关,因此我们可以去掉第一维。那么状态转移方程变为:
  • 若S[i] != T[j],那么dp[j+1] = dp[j+1]
  • S[i] == T[j],那么dp[j+1] = dp[j+1] + dp[j]
  • 需要注意的是,这时候在枚举j时,需要逆序枚举,因为二维转移方程中,j+1依赖上一维的j和j+1,改为1维后,若正序更新j,那么若更新完dp[1],然后更新dp[2],若dp[2] = dp[2] + dp[1],这里需要的dp[1]是上一轮的dp[1],而正序更新会导致dp[1]已经更新过,那么显然是错误的。而逆序更新就没问题。
  • 下面是一维数组的版本。
  • const int mod = 1e9+7;
    const string pat = "niuniu";
    
    class Solution {
    public:
        /**
         * 好多牛牛
         * @param s string字符串
         * @return int整型
         */
        int solve(string& s) {
            // write code here
            int pLen = pat.size();
            vector<int> dp(pLen+1);
            dp[0] = 1;
            for(const auto& c:s){
                for(int j=pLen-1;j>=0;j--){
                    if(c==pat[j]){
                        dp[j+1] = (dp[j+1] + dp[j])%mod;
                    }
                }
            }
            return dp[pLen];
        }
    };
    


  • 当然,由于pat=“niuniu”比较短,我们也可以直接暴力写动态规划
    const int mod = 1e9+7;
    
    class Solution {
    public:
        /**
         * 好多牛牛
         * @param s string字符串
         * @return int整型
         */
        int solve(string& s) {
            // write code here
            int sLen = s.size();
            vector<int> dp(5);
            for(int i=0;i<sLen;i++){
                switch(s[i]){
                    case 'n': dp[0] = (dp[0]+1)%mod; dp[3] = (dp[3]+dp[2])%mod;break;
                    case 'i': dp[1] = (dp[0]+dp[1])%mod; dp[4] = (dp[3]+dp[4])%mod;break;
                    case 'u': dp[2] = (dp[1]+dp[2])%mod; dp[5] = (dp[4]+dp[5])%mod;break;
                    default: break;
                }
            }
            return dp[5];
        }
    };

编辑于 2020-10-09 16:11:34 回复(3)
class Solution {
public:
    /**
     * 好多牛牛
     * @param s string字符串 
     * @return int整型
     */
    int solve(string s) {
        string t = "niuniu";
        int M = 1e9+7, n=s.length(), m=t.length();
        long dp[n];
        memset(dp, 0, sizeof(dp));
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(s[i]==t[j]){
                    dp[j] += (j==0 ? 1 : dp[j-1]);
                    dp[j] %= M;
                }
        return dp[m-1];
    }
};

发表于 2020-06-29 09:01:46 回复(2)
我本来是这样写的。
    int solve(string s) {
        const int MOD = 1e9 + 7;
        string str = "niuniu";
        vector<vector<long long>> dp(s.size(),vector<long long>(str.size(),0));
        for(int i=0;i<s.size();i++){
            for(int j=0;j<str.size();j++){
                if(j == 0){
                    if(s[i] == str[j]){
                        dp[i][j] = 1;
                    }
                }else{
                    if(s[i] == str[j]){
                        for(int k=0;k<i;k++){
                            dp[i][j] += dp[k][j-1];
                            dp[i][j] %= MOD;
                        }
                    }
                }
            }
        }
        long long res = 0;
        for(int i=0;i<s.size();i++){
            res += dp[i][str.size()-1];
            res %= MOD;
        }
        return res;
    }
这样写发现超时了,看了别人的代码后,才发现不需要二维的dp,因为说给的字符串比较特殊,没有aa这种两个同样的字符相连的情况,所以可以不用记录原始字符串的结尾,代码改为了下面这样。

int solve(string s) {
    const int MOD = 1e9 + 7;
    string str = "niuniu";
    vector<long long> dp(str.size(),0);
    for(int i=0;i<s.size();i++){
        for(int j=0;j<str.size();j++){
            if(s[i] == str[j]){
                if(j == 0){
                    dp[j]++;
                    dp[j] %= MOD;
                }else{
                    dp[j] += dp[j-1];
                    dp[j] %= MOD;
                }
            }
        }
    }
    
    return dp[str.size()-1];
}



发表于 2020-06-05 14:35:49 回复(0)
class Solution {
public:
    int solve(string s) 
    {
        int count[6] = { 0,0,0,0,0,0 };  //分别记录已遍历序列中"n","ni","niu","niun","niuni","niuniu"的个数
        for (int i = 0; i < s.size(); ++i)
        {
            switch (s[i])
            {
            case 'n':++count[0]; count[3] += count[2];
                count[0] %= 1000000007;
                count[3] %= 1000000007;
                break;             //当前字符是'n'时,"n"与"niun"数量改变
            case 'i':count[1] += count[0]; count[4] += count[3]; 
                count[1] %= 1000000007;
                count[4] %= 1000000007;
                break;             //当前字符是'i'时,"ni"与"niuni"数量改变
            case 'u':count[2] += count[1]; count[5] += count[4]; 
                count[2] %= 1000000007;
                count[5] %= 1000000007;
                break;             //当前字符是'u'时,"niu"与"niuniu"数量改变
            } 
        }
        return count[5];
    }
};

发表于 2020-04-26 11:27:50 回复(0)
memset(f, 0, sizeof(f));
f[0] = 1;
string a = "*niuniu";
for(int i = 1; i <= s.size(); i++){
    for(int j = 1; j <= 6; j++){
        if(s[i-1] == a[j]){
            f[j] += f[j-1];
            f[j] %= MOD;
        }
    }
}
return f[6];
规律可以看这个
1 1 1 1 1 1 1 1 1 1 *
1 1 1 2 2 3 3 3 0 0 n
0 1 1 1 3 3 6 6 0 0 i 
0 0 1 1 1 1 1 7 0 0 u
0 0 0 1 1 2 2 2 0 0 n
0 0 0 0 1 1 3 3 0 0 i
0 0 0 0 0 0 0 3 0 0 u
n i u n i n i u



发表于 2020-04-21 17:09:33 回复(0)
class Solution:
    def solve(self , s ):
        # write code here
        t='niuniu'
        d=[[0]*(len(t)+1) for _ in range(len(s)+1)]
        for i in range(len(s)+1):
            d[i][0]=1
        for i in range(1,len(s)+1):
            for j in range(1,len(t)+1):
                if s[i-1]==t[j-1]:
                    d[i][j]=d[i-1][j-1]+d[i-1][j]
                else:
                    d[i][j]=d[i-1][j]
        return d[-1][-1]

如果输入的最后一个字符和模式串最后一个字符匹配,则匹配个数等于输入字符去掉最后一个字符,即(niunini)匹配到的(niuni)个数加上(niunini)能匹配到的(niuniu)个数
发表于 2021-04-08 04:01:00 回复(0)

匹配的子串数目(动态规划)

  • 令dp数组为主串s的长度为i的前缀s[0, i]中和模式串pat("niuniu")任意长度前缀匹配的数目

  • 那么状态转移方程即为

    • dp[j] += dp[j - 1] if s[i] == pat[j]

    • 其中当j = 0时,dp[0] += 1, 不妨在dp[0]的前面插入一个1, 以使代码更加整洁

      int solve(string s) {
          // write code here
          int n = s.size();
          if(n < 6) return 0;
          string pat = "niuniu";
          size_t plen = pat.size();
      
          vector<int> dp(plen + 1, 0);
          dp[0] = 1;
          for(int i = 0; i < n; ++i)
          {
              for(int j = 0; j < plen; ++j)
              {
                  if(s[i] == pat[j])
                  dp[j + 1] += dp[j];
                  dp[j + 1] %= 1000000007;
              }
          }
      
          return dp[plen];
      }
发表于 2020-08-10 10:10:24 回复(0)
import java.util.*;


public class Solution {
    /**
     * 好多牛牛
     * @param s string字符串
     * @return int整型
     */
    public int solve (String s) {
        String niu = "niuniu";
        int n = s.length();
        int m = niu.length();
        int mo = 1000000007;
        int[] dp = new int[m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(s.charAt(i) == niu.charAt(j)){
                    dp[j] += (j==0 ? 1 : dp[j-1]);
                    dp[j] %= mo;
                }
            }
        }

        return dp[m-1];
    }
}

发表于 2020-08-08 17:37:39 回复(0)
public class Solution {
    /**
     * 好多牛牛
     * @param s string字符串 
     * @return int整型
     */
    public int solve (String s) {
        // write code here
        int M = 1000000007;
        String t = "niuniu";
        int m = s.length();
        int n = t.length();
        int[][] dp = new int[n+1][m+1];
        for(int j = 0; j <= m;j++){
            dp[0][j] = 1;
        }
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=m;j++){
                if(s.charAt(j-1) == t.charAt(i-1)){
                    dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
                    dp[i][j] %= M;
                }else{
                    dp[i][j] = dp[i][j-1] % M;
                }
            }
        }
        return dp[n][m]%M;
    }
}

发表于 2020-07-29 13:04:28 回复(0)
动态规划,re表示到字符串i时到每个位置的能出现的个数,当出现当前位置时,要上一位的个数加上上一次迭代得出这次的个数
class Solution:
    def solve(self, s):
        re = [0 for _ in range(6)]
        for i in s:
            if i == 'n':
                re[0] = (re[0] + 1) % (1e9 + 7)
                re[3] = (re[2] + re[3]) % (1e9 + 7)
            if i == 'i':
                re[1] = (re[0] + re[1]) % (1e9 + 7)
                re[4] = (re[3] + re[4]) % (1e9 + 7)
            if i == 'u':
                re[2] = (re[1] + re[2]) % (1e9 + 7)
                re[5] = (re[4] + re[5]) % (1e9 + 7)
        return re[5]

发表于 2020-06-29 10:55:18 回复(0)