class Solution {
public:
char kthCharacter(long long k, vector<int>& operations) {
}
};
3307. 找出第 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 <= 10141 <= operations.length <= 100operations[i] 可以是 0 或 1。word 至少有 k 个字符。相似题目
原站题解
java 解法, 执行用时: 1 ms, 内存消耗: 42.1 MB, 提交时间: 2024-10-13 23:48:26
class Solution {
public char kthCharacter(long k, int[] operations) {
// 从 k-1 的二进制长度减一开始，详细解释见下文
return f(k, operations, 63 - Long.numberOfLeadingZeros(k - 1));
}
private char f(long k, int[] operations, int i) {
if (i < 0) {
return 'a';
}
int op = operations[i];
if (k <= (1L << i)) { // k 在左半边
return f(k, operations, i - 1);
}
// k 在右半边
char ans = f(k - (1L << i), operations, i - 1);
return (char) ('a' + (ans - 'a' + op) % 26);
}
public char kthCharacter2(long k, int[] operations) {
int inc = 0;
for (int i = 63 - Long.numberOfLeadingZeros(k - 1); i >= 0; i--) {
if (k > (1L << i)) { // k 在右半边
inc += operations[i];
k -= (1L << i);
}
}
return (char) ('a' + inc % 26);
}
}
golang 解法, 执行用时: 3 ms, 内存消耗: 2.7 MB, 提交时间: 2024-10-13 23:47:53
func kthCharacter(k int64, operations []int) byte {
k--
inc := 0
for i, op := range operations[:bits.Len64(uint64(k))] {
if k>>i&1 > 0 {
inc += op
}
}
return 'a' + byte(inc%26)
}
func kthCharacter2(k int64, operations []int) byte {
inc := 0
for i := bits.Len64(uint64(k-1)) - 1; i >= 0; i-- {
if k > 1<<i { // k 在右半边
inc += operations[i]
k -= 1 << i
}
}
return 'a' + byte(inc%26)
}
func kthCharacter3(k int64, operations []int) byte {
n := len(operations)
if n == 0 {
return 'a'
}
n-- // 注意这里减一了
op := operations[n]
operations = operations[:n]
if n >= 63 || k <= 1<<n { // k 在左半边
return kthCharacter(k, operations)
}
// k 在右半边
ans := kthCharacter(k-1<<n, operations)
return 'a' + (ans-'a'+byte(op))%26
}
python3 解法, 执行用时: 34 ms, 内存消耗: 16.4 MB, 提交时间: 2024-10-13 23:47:12
class Solution:
def kthCharacter(self, k: int, operations: List[int]) -> str:
if not operations:
return 'a'
op = operations.pop()
# 注意 pop 之后 operations 的长度减少了 1，所以下面写的是 1<<n 而不是 1<<(n-1)
m = 1 << len(operations)
if k <= m: # k 在左半边
return self.kthCharacter(k, operations)
# k 在右半边
ans = self.kthCharacter(k - m, operations)
return ascii_lowercase[(ord(ans) - ord('a') + op) % 26]
# 迭代
def kthCharacter2(self, k: int, operations: List[int]) -> str:
inc = 0
for i in range((k - 1).bit_length() - 1, -1, -1):
if k > 1 << i: # k 在右半边
inc += operations[i]
k -= 1 << i
return ascii_lowercase[inc % 26]
# 迭代写法二
def kthCharacter3(self, k: int, operations: List[int]) -> str:
k -= 1
len_k = k.bit_length()
inc = sum(op for i, op in enumerate(operations[:len_k]) if k >> i & 1)
return ascii_lowercase[inc % 26]
# 迭代写法三
def kthCharacter4(self, k: int, operations: List[int]) -> str:
k -= 1
len_k = k.bit_length()
inc = sum(k >> i & op for i, op in enumerate(operations[:len_k]))
return ascii_lowercase[inc % 26]