LeetCode Weekly Contest 156

事实证明生一肚子气切比赛没有什么好下场

1207. Unique Number of Occurrences

求问数组中数字的出现次数是不是唯一的。

思路:Counter

1
2
3
4
class Solution:
def uniqueOccurrences(self, arr: List[int]) -> bool:
c = collections.Counter(arr)
return len(c.keys()) == len(set(c.values()))

1208. Get Equal Substrings Within Budget

两个字符串,修改一个字符的cost为对应ASCII差值的绝对值,问总cost不超过maxCost的最长子串。

思路:二分或双指针

详解:比赛没想到双指针,二分也写了半天

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
costs = list(map(lambda x: abs(ord(x[0]) - ord(x[1])), zip(s, t)))
pre_costs = [0] * len(costs)
for i, c in enumerate(costs):
pre_costs[i] = (pre_costs[i-1] if i>0 else 0) + c
ans = 0
def sumlr(a, l, r):
if l > r:
return 0
if l == 0:
return a[r]
return a[r] - a[l-1]
for i, c in enumerate(pre_costs):
l, r = i, len(pre_costs) - 1
while l < r - 1:
mid = (l + r) // 2
if sumlr(pre_costs, i, mid) <= maxCost:
l = mid + 1
else:
r = mid
if r < len(pre_costs):
while sumlr(pre_costs, i, r) > maxCost: r -= 1
ans = max(ans, r - i + 1)
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def equalSubstring(self, S, T, maxCost):
N = len(S)
A = [abs(ord(S[i]) - ord(T[i])) for i in xrange(N)]
left = 0
windowsum = 0
ans = 0
for right, x in enumerate(A):
windowsum += x
while windowsum > maxCost and left < N:
windowsum -= A[left]
left += 1
cand = right - left + 1
if cand > ans: ans = cand
return ans

1209. Remove All Adjacent Duplicates in String II

出现长度为k的同一个字符组成的字符串就删掉,问最后剩下的字符串。

思路:栈模拟。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def removeDuplicates(self, s: str, k: int) -> str:
str_stack = []
for i, ch in enumerate(s):
temp_str = str_stack.pop() if str_stack else ""
if temp_str and ch != temp_str[-1]:
str_stack.append(temp_str)
temp_str = ""
temp_str += ch
if len(temp_str) != k:
str_stack.append(temp_str)
return "".join(str_stack)

1210. Minimum Moves to Reach Target with Rotations

蛇可以顺逆时针旋转,往右往下移动,问迷宫最短路。

思路:BFS模拟。

吐槽:一开始不知道顺时针旋转后也可以向右移动,导致WA死。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import heapq
def bfs(mp):
n = len(mp[0])
init_pos = ((0, 0), (0, 1))
target_pos = ((n-1, n-2), (n-1, n-1))
Q = [(0, init_pos, 0)]
vis = set()
def inrange(xy, xy0, mp):
n = len(mp[0])
x, y = xy
x0, y0 = xy0
if not (0 <= x < n and 0 <= y < n and 0 <= x0 < n and 0 <= y0 < n):
return False
if mp[x][y] == 1 or mp[x0][y0] == 1:
return False
return True
while Q:
moves, cur_pos, cur_dir = heapq.heappop(Q)
if (cur_pos, cur_dir) in vis:
continue
vis.add((cur_pos, cur_dir))
if cur_pos == target_pos:
return moves
(x, y), (x0, y0) = cur_pos
# move right
if inrange((x, y+1), (x0, y0+1), mp) and (((x, y+1), (x0, y0+1)), cur_dir) not in vis:
heapq.heappush(Q, (moves+1, ((x, y+1), (x0, y0+1)), cur_dir))
# move down
if inrange((x+1, y), (x0+1, y0), mp) and (((x+1, y), (x0+1, y0)), cur_dir) not in vis:
heapq.heappush(Q, (moves+1, ((x+1, y), (x0+1, y0)), cur_dir))
if cur_dir == 0:
# rotate clockwise
if inrange((x+1, y), (x0+1, y0), mp) and (((x, y), (x+1, y)), 1) not in vis:
heapq.heappush(Q, (moves+1, ((x, y), (x+1, y)), 1))
else:
# rotate counterclockwise
if inrange((x, y+1), (x0, y0+1), mp) and (((x, y), (x, y+1)), 0) not in vis:
heapq.heappush(Q, (moves+1, ((x, y), (x, y+1)), 0))
return -1

class Solution:
def minimumMoves(self, grid) -> int:
return bfs(grid)