输入 k 仅限于介于 1 及 92 ，因此，要计算序列字符串，只需要前92个字符。但是，字符串的开头会因每个不同的原因而改变 x[i] 价值前十一名 x[i] 值字符串取决于的完整值 x[i-1] 及 x[i-2] ，但在11号之后 x[i] 值的第一个字符串 x[i-2] 已足够长，因此 x[i-1] 不再重要了，因为它在结果的末尾被连接起来。价值 x[i-1] 及 x[i-2] 对于较大的指数，可如下所示：

x[i-1] = 1111111...1111111 + xxxxxxxxxx
x[i-2] = 2222222...2222222 + yyyyyyyyyy
x[i] = 2222222...2222222 + yyyyyyyyyy + 1111111...1111111 + xxxxxxxxxx

假设 111...111 / 222...222 部分（当然不是实际的字符）有92个字符长，那么你就不需要剩下的东西了 xx... 及 yyyyy... 在那之后，你再也无法用有限的时间接触到他们了 k 不管怎样，都要珍惜。所以对于你的问题，这个序列

x[i] = 2222222...2222222 + yyyyyyyyyy + 1111111...1111111 + xxxxxxxxxx

与

x[i] = 2222222...2222222

足够高 i .
现在剩下的问题是计算/选择 111..111 或 222...222 应该在计算以下内容时使用 x[24] 甚至 x[80] . 最有可能是一个奇数/偶数的检查，在这里你会写下：“什么时候？” n 是平的，用 x[10] ，否则使用 x[11] .".
⑨）检查是否存在任何“一个关闭”错误，92个字符的阈值可能不在索引中 11 .

有一种解决方案适用于任何情况 k 那是一个 int 并且不包含昂贵的串联操作，具有 O(1) 记忆与 O(log(k)) 时间1。

前缀和奇偶校验

此算法使用@progman在其答案中的观察结果，即如果 a < b 及 a 及 b 那么，你有相同的平价吗 x[a] 是的前缀 x[b] （这是从以下事实归纳得出的结论： x[n-2] 是的前缀 x[n] ). 这意味着我们不需要计算 n 序列中的项目，我们只需要找到 j ，我将其定义为 x[j] 大于 k ，及 j 具有与相同的奇偶性 n .
例如，如果 n = 12345 及 k = 1 ，那么我们只需要计算 x[3] = 101 因为我们知道 x[3] 是的前缀 x[12345] 作为 3 及 12345 他们俩都很奇怪。所以答案是 0 .

进入o（1）内存

用于避免存储长的0和1序列的方法如下：

不需要计算x

首先注意单词的长度 x[n] 等于 fib[n] 哪里 fib 是斐波那契序列。因此，与其计算中的字符串 x 和索引到 x[n] 看看是否返回 1 或 0 ，该方法使用以下事实： x[n] = x[n-2] + x[n-1] . 你可以算出 x[n][k] 是 x[n-2] 或 x[n-1] 通过比较 k 长到 x[n-2] （其中 x[n-2] 是 fib[n-2] ). 经过比较，我们知道 x[n][k] 等于 x[n-2][k] 或 x[n-1][k-fib[n-2]] . 然后，我们重复这个过程 n 着手 n-1 或 n-2 视情况而定，以及 k 保持不变或设置为 k-fib[n-2] 视情况而定。重复此操作直到 n == 0 或 n == 1 ，在哪一点上 k 将 0 所以 x[n][k] 要么等于 x[0][0] = 0 或 x[1][0] = 1 ，顾名思义。

不需要储存谎言 x 仅在计算中不需要 fib ，这避免了存储长的数字序列，但是我们肯定需要存储所有的斐波那契数，直到 fib[j] 为了执行上一段中定义的步骤？不，我们没有！这是因为我们首先发现 j ，只保留 fib[i-1] 及 fib[i] 在记忆中。然后我们重新排列方程，找到 fib[n-2] = fib[n] - fib[n-1] ，并使用它回溯斐波那契序列以查找 x[n][k] .

实施

我已经解释了算法，下面是一个java实现：
首先，我们定义一个 Fib 类封装斐波那契序列，保持代码整洁(如果需要保留一个文件，可以将其移动到内部类。）

class Fib {
    private long a = 0;
    private long b = 1;
    private int index = 0;

    void advance() {
        long sum = a + b;
        a = b;
        b = sum;
        index++;
    }

    void backtrack() {
        long diff = b - a;
        b = a;
        a = diff;
        index--;
    }

    long getPreviousValue() {
        return a;
    }

    long getCurrentValue() {
        return b;
    }

    int getIndex() {
        return index;
    }
}

然后，实际算法：

public class Main {
    public static int fibNK(int n, int k) {
        Fib fib = new Fib();
        // if n is odd, go to the next fib so that fib.getIndex() is 1
        // this ensures that n and fib.getIndex() are either both even or both odd
        if (n % 2 == 1) {
            fib.advance();
        }
        // find the first fibonacci number greater than k that is still even/odd
        while (k >= fib.getCurrentValue()) {
            // x+2 is even if x is even, so advance twice
            fib.advance();
            fib.advance();
        }
        // now to find character k of the word:

        // if we're looking at the first or second fibonacci word, "0" or "1",
        // then the character at index k must be 0 or 1
        while (fib.getIndex() > 1) {
            // only fib[i] and fib[i-1] are stored, but fib[i-2] is needed, so backtrack
            fib.backtrack();
            // we are trying to find fibWord[i][k]
            // fibWord[i][k] = fibWord[i-2] + fibWord[i-1]
            // if k >= fibWord[i-2].length, then the target character is in the second part of the word, fibWord[i-1]
            if (k >= fib.getPreviousValue()) {
                // specifically, if k >= fib[i-2], then fibWord[i][k]==fibWord[i-1][k-fibWord[i-2].length]
                k -= fib.getPreviousValue();
            } else {
                // otherwise, fibWord[i][k]==fibWord[i-2][k], so another backtrack is needed
                fib.backtrack();
            }
        }
        // return either 0 or 1
        return fib.getIndex();
    }

    public static void main(String[] args) {
        // test the algorithm by using to print the first few words in `x`, one letter at a time
        Fib fib = new Fib();

        for (int n = 0; n < 8; n++) {
            for (int k = 0; k < fib.getCurrentValue(); k++) {
                System.out.print(fibNK(n, k));
            }
            System.out.println();
            fib.advance();
        }
    }
}

回家还是回家

这个 O(log(k)) 时间复杂性意味着它运行得非常快，即使是非常大的时间 k 价值观如果你想要 k 大于 Integer.MAX_VALUE （相当于 n 大于 45 )你可以改变 k 到 long 但在计算斐波那契数时，这可能会导致溢出错误，因此需要将一些变量更改为 BigInteger s、 虽然这会稍微增加时间和空间的复杂性。
1斐波那契序列具有指数下界，因此 x[n] 大于 (3/2)**n ，意思是 O(log(k)) 需要计算斐波那契数才能找到一个大于 k . 然后，第二阶段执行相同数量的“回溯”操作以返回到目标 x[0] 或 x[1] ，这是额外的费用 O(log(k)) 时间，导致 O(log(k)) 总计