Posted on 2023-09-27 17:41
Uriel 阅读(24)
评论(0) 编辑 收藏 引用 所属分类:
数学 、
闲来无事重切Leet Code
给出一列字符串，里面由字符和数字2-9组成，遇到字符就加入stack，遇到数字（设为d），就把到目前为止的字符stack重复d-1次，问最后的结果字符串第k为是什么字符
如果把整个结果字符串都记录下来会MLE，所以只要倒推第k位对应第一次出现时的位置，输出那个字符
1 #880
2 #Runtime: 20 ms Beats 12.50%)
3 #Memory: 13.5 MB (Beats 29.17%)
4
5 class Solution(object):
6 def decodeAtIndex(self, s, k):
7 """
8 :type s: str
9 :type k: int
10 :rtype: str
11 """
12 l = 0
13 for ch in s:
14 if ch.isdigit():
15 l *= int(ch)
16 else:
17 l += 1
18 for i in range(len(s) - 1, -1, -1):
19 if s[i].isdigit():
20 l //= int(s[i])
21 k %= l
22 else:
23 if l == k or k == 0:
24 return s[i]
25 l -= 1