小易在学校中学习了关于字符串的理论, 于是他基于此完成了一个字典的项目。
小易的这个字典很奇特, 字典内的每个单词都包含n个'a'和m个'z', 并且所有单词按照字典序排列。
小易现在希望你能帮他找出第k个单词是什么。
小易在学校中学习了关于字符串的理论, 于是他基于此完成了一个字典的项目。
小易的这个字典很奇特, 字典内的每个单词都包含n个'a'和m个'z', 并且所有单词按照字典序排列。
小易现在希望你能帮他找出第k个单词是什么。
输入包括一行三个整数n, m, k(1 <= n, m <= 100, 1 <= k <= 109), 以空格分割。
输出第k个字典中的字符串,如果无解,输出-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); }
// 读取
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%的 大神 麻烦贴下代码, 先给您跪了