Solution to LeetCode 2038 Remove Colored Pieces if Both Neighbors are the Same Color and LeetCode 2069 Walking Robot Simulation II.
LeetCode 2038
Remove Colored Pieces if Both Neighbors are the Same Color (Medium) [link]
Note that when we meet AAAAA
, the number of deletion is 5-2 =3. Time complexity O(n).
class Solution:
def winnerOfGame(self, colors: str) -> bool:
freq = [0, 0]
cur, cnt = 'C', 0
for c in colors:
if c != cur:
cur = c
cnt = 1
else:
cnt += 1
if cnt >= 3:
freq[ord(cur) - ord('A')] += 1
return freq[0] > freq[1]
LeetCode 2069
Walking Robot Simulation II (Medium) [link]
Note that the robot only moves in the outer circle, so we can preprocess to store all the possible positions and the corresponding direction.
class Robot:
TO_DIR = {
0: "East",
1: "North",
2: "West",
3: "South",
}
def __init__(self, width: int, height: int):
self.moved = False
self.idx = 0
self.pos = list()
self.dirs = list()
pos_, dirs_ = self.pos, self.dirs
for i in range(width):
pos_.append((i, 0))
dirs_.append(0)
for i in range(1, height):
pos_.append((width - 1, i))
dirs_.append(1)
for i in range(width - 2, -1, -1):
pos_.append((i, height - 1))
dirs_.append(2)
for i in range(height - 2, 0, -1):
pos_.append((0, i))
dirs_.append(3)
dirs_[0] = 3
def move(self, num: int) -> None:
self.moved = True
self.idx = (self.idx + num) % len(self.pos)
def getPos(self) -> List[int]:
return list(self.pos[self.idx])
def getDir(self) -> str:
if not self.moved:
return "East"
return Robot.TO_DIR[self.dirs[self.idx]]