小易在学校中学习了关于字符串的理论, 于是他基于此完成了一个字典的项目。
小易的这个字典很奇特, 字典内的每个单词都包含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%的 大神 麻烦贴下代码, 先给您跪了