Posted on 2023-09-27 17:41
Uriel 閱讀(50)
評論(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