如何减少内存使用，搜索序列中的第 k 个字符？

Question

问题陈述：

一位老师曾说过："Good writing is good writing is good writing." 因此，老师定义 f0= "Good writing is good writing is good writing." 为了让这句话更有趣，老师定义了 fn= "Good writing is good " +fn−1+ " writing is good " +fn−1+ " is good writing."对于所有 n≥1

例如f1是：

Good writing is good Good writing is good writing is good writing. writing is good Good writing is good writing is good writing. is good writing.

请注意，引号不是 f1 的一部分。

老师想问q个问题。每次她想找到 fn 的第 k 个字符。字符从 1 开始索引。如果 fn 包含少于 k 个字符，则输出 .

在所有测试中，

1≤q≤10

0≤n≤30

1≤k≤2³¹⁻¹

例如：

输入：

输出：

d
g
.

输入：

输出：

w

G

我的问题：

到目前为止我所做的只是创建一个数组来存储 f0 到 f31 的预计算字符串。

        String[] f = new String[31];
        f[0] = "Good writing is good writing is good writing.";
        f[1] = "Good writing is good Good writing is good writing is good writing. writing is good Good writing is good writing is good writing. is good writing.";
        for(int i = 2; i < 31; i++) {
            f[i] = "Good writing is good " + f[i-1] + " writing is good " + f[i-1] + " is good writing.";
        }

预先计算出最大值 31 后，我查询输入：

        while(q-->0) {
            int n = readInt();
            int k = readInt();
            System.out.println(f[n]);
            if(f[n].length() < k) {
                System.out.println(".");
            } else {
                System.out.println(f[n].charAt(k-1));
            }
        }

现在的问题是，当执行此操作时，我会收到 内存不足错误。这让我想到有一种更快更简单的方法来做这道题。我感觉有规律可循，但我可能错了。有什么想法吗？

Answer 1

一个想法是确定第 k 个字符在添加的部分中的位置。为此，除了第 k 个字符之外，我们可以使先前的调用 return 其结果的长度而不是结果本身。然后我们可以决定第 k 个落在部分中的哪个位置。以下代码也是 return 字符串，但仅用于演示目的。

您可以看到，在我们的函数 f(n, k) 中，如果我们确定第 k 个字符落在 f(n - 1) 的部分之一内，我们从 k 中减去长度前面的 section/s 并从 f(n - 1, k - length_of_prefix) 获得 kth 因为这就像在 f(n - 1) 中寻找（新的）第 k 个。我们根据需要递归地执行该搜索。

JavaScript代码：

// Returns [len_fn, kth, fn]
function f(n, k){
  const f_0 = "Good writing is good writing is good writing."
  const len_0 = f_0.length
  
  const str_1 = "Good writing is good "
  const str_2 = " writing is good "
  const str_3 = " is good writing."
  const len_1 = str_1.length
  const len_2 = str_2.length
  const len_3 = str_3.length
  
  if (n == 0)
    return [len_0, f_0[k-1], f_0]
  
  const [len_fn1, kth1, fn1] = f(n - 1)
  const fn = str_1 + fn1 + str_2 + fn1 + str_3
  
  const len_fn = len_1 + len_fn1 + len_2 + len_fn1 + len_3
  const pos_fn1_2 = len_1 + len_fn1 + len_2
  
  if (k <= len_1)
    return [len_fn, str_1[k-1], fn]
    
  // kth is in f(n - 1)
  else if (k <= len_1 + len_fn1){
    const kth = f(n - 1, k - len_1)[1]
    return [len_fn, kth, fn]
  }
  
  else if (k <= pos_fn1_2)
    return [len_fn, str_2[k-len_1-len_fn1-1], fn]
    
  // kth is in f(n - 1)
  else if (k <= pos_fn1_2 + len_fn1){
    const kth = f(n - 1, k - pos_fn1_2)[1]
    return [len_fn, kth, fn]
  }
    
  else
    return [len_fn, str_3[k-pos_fn1_2-len_fn1-1], fn]
}
   
var result = f(2, 253)
console.log(JSON.stringify(result))
console.log("")
console.log(JSON.stringify(
  result[2].split("").map((x, i) => [i + 1, x])))

如何减少内存使用，搜索序列中的第 k 个字符？

How to reduce memory use, searching for the kth character in a sequence?

memory

string

algorithm

out-of-memory