Leetcode 3307. Find the K-th Character in String Game II
- Leetcode 3307. Find the K-th Character in String Game II
- 1. 解题思路
- 2. 代码实现
- 题目链接：3307. Find the K-th Character in String Game II
1. 解题思路
这道题的话显然每次操作都会使字符串长度double，然后我们只需要看看第几次操作之后字符串长度会不少于 k k k，然后看一下其中各个操作会给当前字符位置带来多少位移即可。
显然，对于任何一次操作，只有当操作为1，且目标位置位于操作后的后半段时，才会产生一个字符位移。
因此，我们通过二分的方法逐步对操作进行还原即可得到最终的位移个数，从而即可得到目标位置下的最终字符。
2. 代码实现
给出python代码实现如下：
class Solution:
def kthCharacter(self, k: int, operations: List[int]) -> str:
op, n = 0, 1
while n < k:
n = n * 2
op += 1
n = n // 2
op -= 1
delta, idx = 0, k
while idx > 1:
if operations[op] == 1 and idx > n:
delta += 1
if idx > n:
idx -= n
n = n // 2
op -= 1
return chr(delta % 26 + ord('a'))
提交代码评测得到：耗时41ms，占用内存16.6MB。