登录[Python3/Java/C++/Go/TypeScript] 一题一解：递推（清晰题解）
方法一：递推
由于每次操作后，字符串的长度都会翻倍，因此，如果进行 $i$ 次操作，字符串的长度将会是 $2^i$。
我们可以模拟这个过程，找到第一个大于等于 $k$ 的字符串长度 $n$。
接下来，我们再往回推，分情况讨论：
- 如果 $k \gt n / 2$，说明 $k$ 在后半部分，如果此时 $\textit{operations}[i - 1] = 1$，说明 $k$ 所在的字符是由前半部分的字符加上 $1$ 得到的，我们加上 $1$。然后我们更新 $k$ 为 $k - n / 2$。
- 如果 $k \le n / 2$，说明 $k$ 在前半部分，不会受到 $\textit{operations}[i - 1]$ 的影响。
- 接下来，我们更新 $n$ 为 $n / 2$，继续往前推，直到 $n = 1$。
最后，我们将得到的数字对 $26$ 取模，加上 'a' 的 ASCII 码，即可得到答案。
###python
class Solution:
def kthCharacter(self, k: int, operations: List[int]) -> str:
n, i = 1, 0
while n < k:
n *= 2
i += 1
d = 0
while n > 1:
if k > n // 2:
k -= n // 2
d += operations[i - 1]
n //= 2
i -= 1
return chr(d % 26 + ord("a"))
###java
class Solution {
public char kthCharacter(long k, int[] operations) {
long n = 1;
int i = 0;
while (n < k) {
n *= 2;
++i;
}
int d = 0;
while (n > 1) {
if (k > n / 2) {
k -= n / 2;
d += operations[i - 1];
}
n /= 2;
--i;
}
return (char) ('a' + (d % 26));
}
}
###cpp
class Solution {
public:
char kthCharacter(long long k, vector<int>& operations) {
long long n = 1;
int i = 0;
while (n < k) {
n *= 2;
++i;
}
int d = 0;
while (n > 1) {
if (k > n / 2) {
k -= n / 2;
d += operations[i - 1];
}
n /= 2;
--i;
}
return 'a' + (d % 26);
}
};
###go
func kthCharacter(k int64, operations []int) byte {
n := int64(1)
i := 0
for n < k {
n *= 2
i++
}
d := 0
for n > 1 {
if k > n/2 {
k -= n / 2
d += operations[i-1]
}
n /= 2
i--
}
return byte('a' + (d % 26))
}
###ts
function kthCharacter(k: number, operations: number[]): string {
let n = 1;
let i = 0;
while (n < k) {
n *= 2;
i++;
}
let d = 0;
while (n > 1) {
if (k > n / 2) {
k -= n / 2;
d += operations[i - 1];
}
n /= 2;
i--;
}
return String.fromCharCode('a'.charCodeAt(0) + (d % 26));
}
###rust
impl Solution {
pub fn kth_character(mut k: i64, operations: Vec<i32>) -> char {
let mut n = 1i64;
let mut i = 0;
while n < k {
n *= 2;
i += 1;
}
let mut d = 0;
while n > 1 {
if k > n / 2 {
k -= n / 2;
d += operations[i - 1] as i64;
}
n /= 2;
i -= 1;
}
((b'a' + (d % 26) as u8) as char)
}
}
###cs
public class Solution {
public char KthCharacter(long k, int[] operations) {
long n = 1;
int i = 0;
while (n < k) {
n *= 2;
++i;
}
int d = 0;
while (n > 1) {
if (k > n / 2) {
k -= n / 2;
d += operations[i - 1];
}
n /= 2;
--i;
}
return (char)('a' + (d % 26));
}
}
###php
class Solution {
/**
* @param Integer $k
* @param Integer[] $operations
* @return String
*/
function kthCharacter($k, $operations) {
$n = 1;
$i = 0;
while ($n < $k) {
$n *= 2;
++$i;
}
$d = 0;
while ($n > 1) {
if ($k > $n / 2) {
$k -= $n / 2;
$d += $operations[$i - 1];
}
$n /= 2;
--$i;
}
return chr(ord('a') + ($d % 26));
}
}
时间复杂度 $O(\log k)$，空间复杂度 $O(1)$。
有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~
