Posted on 2023-09-27 17:41
Uriel 阅读(25)
评论(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