# # Leetcode 第273场周赛题解

## # Problem A - 反转两次的数字 (opens new window)

### # 方法一：观察

• 时间复杂度$\mathcal{O}(1)$
• 空间复杂度$\mathcal{O}(1)$

class Solution:
def isSameAfterReversals(self, num: int) -> bool:
return num == 0 or num % 10 != 0

1
2
3

## # Problem B - 执行所有后缀指令 (opens new window)

### # 方法一：模拟

• 时间复杂度$\mathcal{O}(N^2)$
• 空间复杂度$\mathcal{O}(N)$

class Solution:
def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:
d = {'L': (0, -1), 'R': (0, 1), 'U': (-1, 0), 'D': (1, 0)}
ans = []
for i in range(len(s)):
cmd = 0
r, c = startPos
for j in range(i, len(s)):
nr, nc = r + d[s[j]][0], c + d[s[j]][1]
if 0 <= nr < n and 0 <= nc < n:
r, c = nr, nc
cmd += 1
else:
break
ans.append(cmd)
return ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

## # Problem C - 相同元素的间隔之和 (opens new window)

### # 方法一：前缀和+单指针

• 时间复杂度$\mathcal{O}(N)$
• 空间复杂度$\mathcal{O}(N)$

class Solution:
def getDistances(self, arr: List[int]) -> List[int]:
d = collections.defaultdict(list)
for i, num in enumerate(arr):
d[num].append(i)

ans = [0] * len(arr)
for v in d.values():
m = len(v)
cval = sum(v) - v[0] * m
for i, pos in enumerate(v):
delta = v[i] - v[i - 1] if i >= 1 else 0
cval += i * delta - (m - i) * delta
ans[pos] = cval

return ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

## # Problem D -还原原数组 (opens new window)

### # 方法一：哈希表

• 时间复杂度$\mathcal{O}(N^2)$
• 空间复杂度$\mathcal{O}(N)$

class Solution:
def recoverArray(self, nums: List[int]) -> List[int]:
n = len(nums)
nums.sort()
keys = sorted(list(set(nums)))
for i in range(n - 2, n // 2 - 2, -1):
delta = nums[n - 1] - nums[i]
if delta == 0 or delta % 2 == 1:
continue
cnt = collections.Counter(nums)
ok = True
ans = []
for key in keys:
if cnt[key] == 0:
continue
if cnt[key + delta] < cnt[key]:
ok = False
break
cnt[key + delta] -= cnt[key]
ans += [key + delta // 2] * cnt[key]
cnt[key] = 0
if ok:
return ans
return []

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24