首页 > 试题广场 >

五八文字碰碰消

[编程题]五八文字碰碰消
  • 热度指数：338 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解


  帮帮同学在设计一个文字碰碰消游戏，规定"五"和"八"形成"五八"组合碰到一起即会消除，("八五" 不会消除)。

  例如 "五八", "五八五八", "五五八八"。说明: "五五八八" 是内层的"五八"碰在一起消除后，外层的"五八"会碰在一起消除。

  帮帮同学想知道n个"五"和"八"组成的字符串中，有多少种组合可以满足消除为空字符串。

  现为帮帮同学设计一个方法，输入整数n，表示"五"和"八"的数量，返回n个"五"和n个"八"组成的字符串中，满足消除为空字符串的组合数。

示例1

输入

2

输出

2

说明

满足的组合  [ '五五八八', '五八五八' ]

示例2

输入

3

输出

5

说明

满足的组合  [ '五五五八八八', '五五八五八八', '五五八八五八', '五八五五八八', '五八五八五八' ]

备注:
 "五五八八" 是内层的"五八"碰在一起消除后，外层的"五八"会碰在一起消除。 
算法知识视频讲解
添加回答
努力学习前端ing^_^头像 努力学习前端ing^_^ 

// 参考：**的22-括号生成 
// 思路：使用回溯记录数量，五看成左括号，八看成右括号
// 不符合的条件的直接剪枝 

/**
 * 输入整数n，返回可消除为空字符串的的n组"五八"字符串数量。
 * @param n int整型 
 * @return int整型
 */
function getTargetNumber(n) {
  let res = 0;
  backtracing(n, n);
  return res;

  function backtracing(fi, ei) {
    if (fi == 0 && ei == 0) {
      res++;
      return;
    }
    if (fi > 0) {
      backtracing(fi - 1, ei);
    }
    // 保证八比五少
    if (ei > fi) {
      backtracing(fi, ei - 1);
    }
  }
}

module.exports = {
  getTargetNumber: getTargetNumber,
};





编辑于 2022-08-02 11:00:20 回复(0)
JavaScript
__offer收割机__头像 __offer收割机__ 
functiongetTargetNumber( n ) {  
    let h = 1
    for (let i = 2; i <= n; i++) {
        h = h * (4 * i - 2) / (i + 1)
    }
    return h
}
时间复杂度O(n)
空间复杂度O(1)
详情可查 --> 卡特兰数
编辑于 2022-03-23 16:34:49 回复(1)
JavaScript
牛客401682954号头像 牛客401682954号 
function getTargetNumber(n) {
    //对外封装只保留可传入参数n
  function nsum(x, n) {
        //n为层数，累加开始的底数，x为顶数，由上层递归累加过程中传入
    if (n === 0)
      return 1
        //如果层数为0，则返回1作为递归终点
    var s = 0
    for (var i = n; i <= x; i++) {
      s = s + nsum(i, n - 1)
    }
    return s
  }
  return nsum(n, n)
}
我们假定初始的n个“五”“八”排序为：“……五五五八八八……”，“五”都在左，“八”在右。
第一步：现将第一个“八”不断左移，即“……五五八五八八……”=>“五八五五……五五八八……”，易得共n种排序，即：
第二步：现在将第一个八回退第二个八左移一格，即“……五五八八五八……”，重复第一步，易得，共n-1种排序。
第三步：重复第二步，将第二个八移动到最前“五八五八……五八……”，易得，共n + n-1 + n-2 + n-3 ……n-(n-2)种排序，停留在n-2而不是n-1的原因是因为第二个八前面至少有两个五，即：
第四步：通过不断递推可得，最终排序种类为：

注意到，底数为层数，顶数为上一次累加得输入量，分别作为递归得两个输入量，写出代码如上。
发表于 2022-03-16 13:04:02 回复(0)
南方的雨天头像 南方的雨天
/**
 * 输入整数n，返回可消除为空字符串的的n组"五八"字符串数量。
 * @param n int整型 
 * @return int整型
 */
function getTargetNumber( n ) {
    // write code here
    let num = 0;
    dfs("",n,n);
    function dfs(str,left,right) {
    if(left == 0 && right == 0) {
        num++;
        return;
    }
    if(left < right) {
        return;
    }
    if(left > 0) {
        dfs(str + "五",left - 1,right)
    }
     if(right > 0) {
        dfs(str + "八",left,right - 1)
    }
}
    return num;
}
  
module.exports = {
    getTargetNumber : getTargetNumber
};
发表于 2022-03-30 21:47:26 回复(0)
牛客312383949号头像 牛客312383949号
functiongetTargetNumber( n ) {
    // write code here
    let res=0
    functionfun(init,go){
        if(init<0)return
        if(go>2*n)return
        if(go=== 2* n ){
            if(init===0)res++
        }
        go+=1
        fun(init+1,go)
        fun(init-1,go)
    }
    fun(0,0)
    returnres
}
module.exports = {
    getTargetNumber : getTargetNumber
};
发表于 2022-03-02 14:28:36 回复(4)
提交观点

问题信息

上传者：小小
难度：
5条回答 1236浏览

热门推荐

通过挑战的用户

相关试题

五八文字碰碰消

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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