题目描述

Alice 和 Bob 正在玩一个游戏。最初，Alice 有一个字符串 word = "a"。

给定一个 正整数 k 和一个整数数组 operations，其中 operations[i] 表示第 i 次操作的类型。

现在 Bob 将要求 Alice 按顺序执行 所有 操作：

• 如果 operations[i] == 0，将 word 的一份 副本追加 到它自身。
• 如果 operations[i] == 1，将 word 中的每个字符 更改 为英文字母表中的 下一个 字符来生成一个新字符串，并将其 追加 到原始的 word。例如，对 "c" 进行操作生成 "cd"，对 "zb" 进行操作生成 "zbac"。

在执行所有操作后，返回 word 中第 k 个字符的值。

注意，在第二种类型的操作中，字符 'z' 可以变成 'a'。

样例

输入：k = 5, operations = [0,0,0]

输出："a"

解释：

最初，word == "a"。Alice 按以下方式执行三次操作：

将 "a" 附加到 "a"，word 变为 "aa"。
将 "aa" 附加到 "aa"，word 变为 "aaaa"。
将 "aaaa" 附加到 "aaaa"，word 变为 "aaaaaaaa"。

输入：k = 10, operations = [0,1,0,1]

输出："b"

解释：

最初，word == "a"。Alice 按以下方式执行四次操作：

将 "a" 附加到 "a"，word 变为 "aa"。
将 "bb" 附加到 "aa"，word 变为 "aabb"。
将 "aabb" 附加到 "aabb"，word 变为 "aabbaabb"。
将 "bbccbbcc" 附加到 "aabbaabb"，word 变为 "aabbaabbbbccbbcc"。

限制

• 1 <= k <= 10^14
• 1 <= operations.length <= 100
• operations[i] 可以是 0 或 1。
• 输入保证在执行所有操作后，word 至少有 k 个字符。

算法

(思维题) $O(\log k)$

1. 类似于 找出第 K 个字符 I 的思路，只不过在解递归的过程中，还需要通过 $operations$ 的值来判断答案是否加 $1$。

时间复杂度

• 最多遍历 $k$ 的所有二进制位一次，故时间复杂度为 $O(\log k)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

#define LL long long

class Solution {
public:
    char kthCharacter(LL k, vector<int>& operations) {
        --k;

        char ans = 'a';
        for (int i = 0; k; k >>= 1, i++) {
            if (!operations[i] || !(k & 1))
                continue;

            ++ans;
            if (ans > 'z')
                ans = 'a';
        }

        return ans;
    }
};