# # Leetcode 第234场周赛题解

## # Problem A - 字符串中不同整数的数目 (opens new window)

### # 方法一：模拟

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

class Solution:
def numDifferentIntegers(self, word: str) -> int:
nums = set()
l = 0
while l < len(word):
if word[l].isnumeric():
r = l
while r + 1 < len(word) and word[r + 1].isnumeric():
r += 1
l = r + 1
else:
l += 1
return len(nums)

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

### # 方法二：正则表达式

class Solution:
def numDifferentIntegers(self, word: str) -> int:
return len(set(map(int, filter(lambda x: len(x) > 0, re.split(r'[a-z]+', word)))))

1
2
3

class Solution:
def numDifferentIntegers(self, word: str) -> int:
return len(set(map(int, re.findall(r'\d+', word))))

1
2
3

## # Problem B - 还原排列的最少操作步数 (opens new window)

### # 方法一：模拟

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

class Solution:
def reinitializePermutation(self, n: int) -> int:
perm = [i for i in range(n)]
orig = list(perm)
ops = 0
while True:
ops += 1
perm = [perm[i // 2] if i % 2 == 0 else perm[n // 2 + (i - 1) // 2] for i in range(n)]
if perm == orig:
break
return ops

1
2
3
4
5
6
7
8
9
10
11

### # 方法二：模拟1的位置

$1$的当前位置为$pos$，将变换规则反向，我们可以知道：

• 如果$pos<\dfrac{N}{2}$，则$pos\rightarrow 2pos$
• 否则，$pos\rightarrow 2(pos-\dfrac{N}{2})+1$

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

class Solution:
def reinitializePermutation(self, n: int) -> int:
pos = 1
ops = 0
while True:
ops += 1
if pos < n // 2:
pos <<= 1
else:
pos = 1 + ((pos - n // 2) << 1)
if pos == 1:
break
return ops

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

## # Problem C - 替换字符串中的括号内容 (opens new window)

### # 方法一：模拟

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

class Solution:
def evaluate(self, s: str, knowledge: List[List[str]]) -> str:
d = dict()
for key, val in knowledge:
d[key] = val
ans = []
l = 0
while l < len(s):
if s[l] == '(':
r = l + 1
while s[r] != ')':
r += 1
key = s[l+1:r]
if key in d:
ans.append(d[key])
else:
ans.append('?')
l = r + 1
else:
ans.append(s[l])
l += 1
return ''.join(ans)

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

### # 方法二：正则表达式

class Solution:
def evaluate(self, s: str, knowledge: List[List[str]]) -> str:
d = collections.defaultdict(lambda: '?')
for key, val in knowledge:
d[key] = val
return re.sub(r'$$([a-z]+)$$', lambda x: d[x.group(1)], s)

1
2
3
4
5
6

## # Problem D - 好因子的最大数目 (opens new window)

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

MOD = 1000000007

class Solution:
def maxNiceDivisors(self, n: int) -> int:
if n <= 3:
return n
if n % 3 == 1:
return 4 * pow(3, (n - 4) // 3, MOD) % MOD
elif n % 3 == 2:
return 2 * pow(3, n // 3, MOD) % MOD
else:
return pow(3, n // 3, MOD)

1
2
3
4
5
6
7
8
9
10
11
12