题目描述

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

给定一个 正整数 k。

现在 Bob 会要求 Alice 执行以下操作 无限次:

• 将 word 中的每个字符 更改 为英文字母表中的 下一个 字符来生成一个新字符串，并将其 追加 到原始的 word。

例如，对 "c" 进行操作生成 "cd"，对 "zb" 进行操作生成 "zbac"。

在执行足够多的操作后，word 中 至少 存在 k 个字符，此时返回 word 中第 k 个字符的值。

注意，在操作中字符 'z' 可以变成 'a'。

样例

输入：k = 5

输出："b"

解释：

最初，word = "a"。需要进行三次操作:

生成的字符串是 "b"，word 变为 "ab"。
生成的字符串是 "bc"，word 变为 "abbc"。
生成的字符串是 "bccd"，word 变为 "abbcbccd"。

输入：k = 10

输出："c"

限制

• 1 <= k <= 500

算法

(思维题) $O(1)$

1. 注意到，字符串的生成规则是递归式的。
2. 每次将字符串一分为二，判断第 $k$ 个字符属于左半部分还是右半部分。初始化答案为 a。
3. 如果属于左半部分，则继续对左半部分字符串进行判断。
4. 如果属于右半部分，则将其减去左半部分的长度，然后令答案增加 $1$。
5. 最终发现，这样解递归的操作得到的累加值，等于 $k-1$ 二进制中 $1$ 的个数。

时间复杂度

• 直接用函数求出二进制中 $1$ 的个数，故时间复杂度为 $O(1)$。

空间复杂度

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

C++ 代码

class Solution {
public:
    char kthCharacter(int k) {
        return 'a' + __builtin_popcount(k - 1);
    }
};