Simulate the whole process
880. Decoded String at Index
My ugly code works by naively simulating the whole process.
class Solution:
def decodeAtIndex(self, S: str, K: int) -> str:
ss, dd = [], []
turn = 'str'
this_one = ''
for s in S:
if turn =='str':
if s.isdigit():
ss.append(this_one)
turn = 'dig'
this_one = ''
this_one+=s
else:
this_one += s
else:
if not s.isdigit():
dd.append(int(this_one))
turn = 'str'
this_one = ''
this_one+=s
else:
this_one += s
if this_one:
if turn == 'dig':
dd.append(int(this_one))
else:
ss.append(this_one)
idxes = [0]
if not dd:return S[K-1]
dd.append(1)
def update_dd(d):
res = 1
for ch in d:
res *= int(ch)
return res
dd = [update_dd(str(d)) for d in dd]
for i, s in enumerate(ss):
idxes.append((idxes[-1]+len(s))*dd[i])
idx = bisect.bisect_left(idxes, K)
while True:
total_len = idxes[idx]//dd[idx-1]
K = ((K-1)%total_len) + 1
if total_len-K+1<=len(ss[idx-1]):
return ss[idx-1][-(total_len-K+1)]
else:
idx -= 1874. Walking Robot Simulation
class Solution:
def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
obstacles = {(i,j) for i, j in obstacles}
dirs = [(0,1),(1,0),(0,-1),(-1,0)]
d = 0
r, c =0, 0
pos = []
for com in commands:
if com==-1:
d+=1
elif com==-2:
d-=1
else:
di, dj = dirs[d%4]
for k in range(com):
r += di
c += dj
if (r,c) in obstacles:
r -= di
c -= dj
break
pos.append((r, c))
if not pos:return 0
x,y = max(pos, key = lambda x:x[0]**2+x[1]**2)
return x**2+y**25294. Maximum Candies You Can Get from Boxes
Simulate the whole process by maintaining a set contains available boxes and a set contains available keys.
Explore if we have openable boxes.
Stop when no more boxes can be opened.
Here is the code (860ms)
class Solution:
def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
if not initialBoxes:return 0
boxes = set(initialBoxes)
keyss = set([i for i,s in enumerate(status) if s==1])
res = 0
while boxes & keyss:
common = boxes & keyss
for i in common:
keyss.remove(i)
boxes.remove(i)
res += candies[i]
keyss |= set(keys[i])
boxes |= set(containedBoxes[i])
return resUsing set.update is slightly faster (840 ms).
class Solution:
def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
if not initialBoxes:return 0
boxes = set(initialBoxes)
keyss = set([i for i,s in enumerate(status) if s==1])
res = 0
while boxes & keyss:
common = boxes & keyss
for i in common:
keyss.remove(i)
boxes.remove(i)
res += candies[i]
keyss.update(keys[i])
boxes.update(containedBoxes[i])
return resThe reason that update is faster than union might be:
“union() or | will create a new set that contains all the elements from the sets we provide”
“set.update is basically an equivalent of in-place set union operation. “
Reference:
https://www.pythoncheatsheet.org/blog/python-sets-what-why-how/
https://stackoverflow.com/questions/28845284/add-vs-update-in-set-operations-in-python
1297. Maximum Number of Occurrences of a Substring
https://leetcode.com/problems/maximum-number-of-occurrences-of-a-substring/
I got stuck on this problem by using the prefix and always got TLE. Finally, I came up with a naive way and it works.
Naively put every valid substring into a dictionary.
verify each string to see whether it has a less unique symbol than the threshold.
Search from the most frequent string and return immediately when found.
Naive considering minSize and maxSize (2600 ms), complexity O(nk)
class Solution:
def maxFreq(self, s: str, maxLetters: int, a: int, b: int) -> int:
cnt = collections.defaultdict(int)
for i in range(len(s)-a+1):
for j in range(i+a-1, i+b):
if j<=len(s)-1:cnt[s[i:j+1]]+=1
key_val = sorted(cnt.items(), key = lambda x:x[1] )
while key_val:
a, v = key_val.pop()
if len(set(a))<=maxLetters:return v
return 0As suggested here,
https://leetcode.com/problems/maximum-number-of-occurrences-of-a-substring/discuss/457618/Python-solution-we-don't-need-maxSize-do-we
we can only care about the minSize.
Only care minSize (84ms) Complexity O(n)
class Solution:
def maxFreq(self, s: str, maxLetters: int, a: int, b: int) -> int:
cnt = collections.defaultdict(int)
for i in range(len(s)-a+1):
cnt[s[i:i+a]]+=1
for a, v in sorted(cnt.items(), key = lambda x:x[1], reverse=True):
if len(set(a))<=maxLetters:return v
return 0838. Push Dominoes
https://leetcode.com/problems/push-dominoes/
class Solution:
def pushDominoes(self, dominoes: str) -> str:
while True:
new_dominoes = dominoes.replace('R.L', 'S')
new_dominoes = new_dominoes.replace('.L','LL').replace('R.','RR')
if new_dominoes == dominoes:break
dominoes = new_dominoes
return dominoes.replace('S', 'R.L')54. Spiral Matrix
https://leetcode.com/problems/spiral-matrix/
Go right, down, left and up until no action can be taken.
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix or not matrix[0]:return []
moving_direction = {'r':(0,1),'d':(1,0),'l':(0,-1),'u':(-1,0)}
res = []
i,j, k = 0, 0, 0
res = [matrix[0][0]]
R, C = len(matrix), len(matrix[0])
seen = {(0,0)}
while True:
move = 'rdlu'[k%4]
di,dj = moving_direction[move]
r, c = i+di, j+dj
if 0<=r<R and 0<=c<C and (r,c) not in seen:
i, j = r, c
res.append(matrix[r][c])
seen.add((r,c))
else:
k += 1
move = 'rdlu'[k%4]
di,dj = moving_direction[move]
r, c = i+di, j+dj
if 0<=r<R and 0<=c<C and (r,c) not in seen:
i, j = r, c
res.append(matrix[r][c])
seen.add((r,c))
else:
break
return res
