javascript - 算法找到 DA,B(n) 的第 n 个字符

Question

这是我的问题的描述。对于任意两个字符串变量 A 和 B，我们将 FA,B 定义为序列 (A,B,AB,BAB,ABBAB,...)，其中每一项都是前两项的串联。

此外，我们定义 DA,B(n) 为 FA,B 第一项中至少包含 n 位的第 n 位。

示例:

设 A="1415", B="8979"。 n = 10 我们希望找到 DA,B(n)，比方说。

FA,B的前几项是:

“1415”

“8979”

“14158979”

“897914158979”

“9”是答案

写一个算法找出DA,B(n)的第n个字符

写解决方案时需要完成这些事情。

1. 返回类型应该是一个字符串。
2. getNthPosition("1415","8979",10) 应该等于 9
3. getNthPosition("abc","435d",100) 应该等于 b
4. 答案应该对任何给定的输入有效

第 1 和 2 个要求已完成，但我不知道如何执行第 3 个要求。任何建议。谢谢。

这是我的代码:

function getNthPosition(a,b,n) {
let output = '';  
 var tot2,ans;

  tot2 = b + a;
  ans = b+a+b; 

  for(var i = 0; i<=ans.length - 1; i++){


    output += ans[i].split("").sort().join('');


    output += "";
  }

  var nNumber = ans[n - 1];

  return nNumber;

}

console.log(getNthPosition("1415","8979",10));

Answer 1

您可以使用在每次迭代中推送到的字符串数组，以便您可以从数组的 length - 2 和 length - 1 中检索字符串到连接在一起构建下一个:

function getNthPosition(a, b, n) {
  const strs = [a, b];
  // input is 1-indexed, get a variable that's 0-indexed:
  const targetIndex = n - 1;
  while (strs[strs.length - 1].length < targetIndex) {
    const newStr = strs[strs.length - 2] + strs[strs.length - 1];
    strs.push(newStr);
  }
  const last = strs.pop();
  return last[targetIndex];
}

console.log(getNthPosition("1415", "8979", 10));
console.log(getNthPosition("abc", "435d", 100));