首页 > 试题广场 >

小易的字典

[编程题]小易的字典
  • 热度指数:16067 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解

小易在学校中学习了关于字符串的理论, 于是他基于此完成了一个字典的项目。

小易的这个字典很奇特, 字典内的每个单词都包含n个'a'和m个'z', 并且所有单词按照字典序排列。

小易现在希望你能帮他找出第k个单词是什么。


输入描述:

输入包括一行三个整数n, m, k(1 <= n, m <= 100, 1 <= k <= 109), 以空格分割。



输出描述:
输出第k个字典中的字符串,如果无解,输出-1。
示例1

输入

2 2 6

输出

zzaa

说明

字典中的字符串依次为aazz azaz azza zaaz zaza zzaa
 var line = readline().split(' ');
    var n = parseInt(line[0]),
        m = parseInt(line[1]),
        k = parseInt(line[2]);
    var str = '';
    while(n && m){
        var cnt = 1;
        for(var i=0;i<n-1;i++){
            cnt *= n-1+m-i;
            cnt /= i+1;  //计算n-1+m个位置放n-1个a
            if(cnt > k) break; //防止越界。count>k就可以退出计算了
        }
        if(cnt >= k) {
            //说明首字母就是'a'
            str += 'a';
            n--;  //问题缩减为 n-1个a和m个z 中找第k个单词
        }else{
            str += 'z';
            m--;   //问题缩减为 n个a和m-1个z 中找第k-cnt个单词
            k -= cnt;
        }
    }
    //循环结束后,剩余子序列只存在"aa..aaa" 或 "zz..zzz"1种情况
    if(k!=1){
        print(-1);
    }else{
        while(n--){
            str += 'a';
        }
        while(m--){
            str += 'z';
        }
        print(str);
    }    


发表于 2018-10-04 20:34:22 回复(0)
  // 读取
  const input = readline().split(/\s/)
  const n = parseInt(input[0])
  const m = parseInt(input[1])
  const k = parseInt(input[2])

  let answer
  let queue = []
  let i = 0
  let aDone = false

  // 跳床
  function trampoline(f){
    var func = f;
    while (typeof func === 'function'){
      func = func();
    }
    return func;
  }

  // 递归
  // 先考虑a, 再考虑z
  function getItem (n, m, ret) {

    if (n === 0 && m === 0) {

      ++i

      if (i === k) {
        answer = ret
        aDone = true
        queue.length = 0
        return
      }

      if (queue.length > 0) {
        let _ret = queue.pop()
        let _m = queue.pop()
        let _n = queue.pop()
        return getItem.bind(null, _n, _m, _ret)
      }
    }

    if (n > 0 && m > 0) {

      queue.push(n, m - 1, ret.concat('z'))

      return getItem.bind(null, n - 1, m, ret.concat('a'))


    } else if (n > 0) {

      return getItem.bind(null, n - 1, m, ret.concat('a'))

    } else if (m > 0) {

      return getItem.bind(null, n, m - 1, ret.concat('z'))

    }

  }
  // 全排列 [aazz azaz azza zaaz zaza zzaa]
  // 递归改循环, 避免js内存溢出
  const getList = () => {

    // a开头
    trampoline(getItem.bind(null, n - 1, m, 'a'))

    // z开头
    !aDone && trampoline(getItem.bind(null, n, m - 1, 'z'))

  }

  // 查找 ? xxxx : -1
  getList()
  print(answer || -1)

1 40%, 超时
2 循环大数据时CPU超100%
3 谁能用js做出
100 100 Math.pow(10, 9)
或者说 100%的 大神 麻烦贴下代码, 先给您跪了

编辑于 2018-09-08 00:38:54 回复(0)