找出第 K 个字符 II

题目

找出第 K 个字符 II

---

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'。

示例 1:

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

输出： “a”

解释：

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

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

示例 2:

输入： 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 个字符。

题解

方法一:

思路

注意到word每操作一次，长度都会倍增。

不操作，长度为1
第1次操作，长度为2
第2次操作，长度为4
第3次操作，长度为8
第i次操作，长度为$2^i$

我们找到$2^i \ge k$的$i$

如果$k \le 2^i$，第i次操作无论是副本追加还是修改追加，都不会影响，因为k位置不在第i次追加的段中。

如果$k > 2^i$，在第i次修改前其位置在$k-2^{i-1}$，我们递归处理会得到第i-1次操作$k-2^{i-1}$位置的字符，然后如果第i次的修改追加，则将返回的结果字符+1。

复杂度$O(logk)$

代码

class Solution {
public:
    using ll = long long;
    char kthCharacter(long long k, vector<int>& operations) {
        function<char(ll,ll)> dfs = [&](ll x, ll lev) {
            if (lev == 0) return 'a';
            char t;
            if (x>(1LL<<lev-1)) {
                t = dfs(x-(1LL<<lev-1), lev-1);
                if (operations[lev-1]) t = (t-'a'+1)%26+'a';
            } else {
                t = dfs(x, lev-1);
            }
            return t;
        };
        ll p = 0;
        while ((1LL<<p) < k) p++;
        return dfs(k, p);
    }
};