class Solution {
public:
char kthCharacter(int k) {
}
};
3304. 找出第 K 个字符 I
Alice 和 Bob 正在玩一个游戏。最初，Alice 有一个字符串 word = "a"。
给定一个正整数 k。
现在 Bob 会要求 Alice 执行以下操作 无限次 :
word 中的每个字符 更改 为英文字母表中的 下一个 字符来生成一个新字符串，并将其 追加 到原始的 word。例如，对 "c" 进行操作生成 "cd"，对 "zb" 进行操作生成 "zbac"。
在执行足够多的操作后， word 中 至少 存在 k 个字符，此时返回 word 中第 k 个字符的值。
注意，在操作中字符 'z' 可以变成 'a'。
示例 1:
输入：k = 5
输出："b"
解释：
最初，word = "a"。需要进行三次操作:
"b"，word 变为 "ab"。"bc"，word 变为 "abbc"。"bccd"，word 变为 "abbcbccd"。示例 2:
输入：k = 10
输出："c"
提示：
1 <= k <= 500相似题目
原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2024-10-01 15:14:34
func kthCharacter(k int) byte {
return byte('a' + bits.OnesCount(uint(k-1)))
}
func kthCharacter2(k int) byte {
k--
ans := byte('a')
for i := bits.Len(uint(k)) - 1; i >= 0; i-- {
if k >= 1<<i { // k 在右半边
ans++
k -= 1 << i
}
}
return ans
}
java 解法, 执行用时: 0 ms, 内存消耗: 40.2 MB, 提交时间: 2024-10-01 15:14:09
class Solution {
public char kthCharacter1(int k) {
k--;
char ans = 'a';
for (int i = 31 - Integer.numberOfLeadingZeros(k); i >= 0; i--) {
if (k >= (1 << i)) { // k 在右半边
ans++;
k -= (1 << i);
}
}
return ans;
}
public char kthCharacter(int k) {
return (char) ('a' + Integer.bitCount(k - 1));
}
}
cpp 解法, 执行用时: 4 ms, 内存消耗: 7.1 MB, 提交时间: 2024-10-01 15:13:39
class Solution {
public:
char kthCharacter1(long long k) {
k--;
char ans = 'a';
for (int i = __lg(k); i >= 0; i--) {
if (k >= (1 << i)) { // k 在右半边
ans++;
k -= (1 << i);
}
}
return ans;
}
char kthCharacter(long long k) {
return 'a' + __builtin_popcount(k - 1);
}
};
python3 解法, 执行用时: 41 ms, 内存消耗: 16.4 MB, 提交时间: 2024-10-01 15:13:05
class Solution:
def kthCharacter(self, k: int) -> str:
k -= 1
inc = 0
for i in range(k.bit_length() - 1, -1, -1):
if k >= 1 << i: # k 在右半边
inc += 1
k -= 1 << i
return ascii_lowercase[inc]
def kthCharacter2(self, k: int) -> str:
return ascii_lowercase[(k - 1).bit_count()]