5713. 字符串中不同整数的数目
给你一个字符串 word ，该字符串由数字和小写英文字母组成。
请你用空格替换每个不是数字的字符。例如，"a123bc34d8ef34" 将会变成 " 123 34 8 34" 。注意，剩下的这些整数间至少要用一个空格隔开："123"、"34"、"8" 和 "34" 。
返回对 word 完成替换后形成的 不同 整数的数目。
如果两个整数的 不含前导零 的十进制表示不同，则认为这两个整数也不同。
示例 1：
输入：word = "a123bc34d8ef34"输出：3解释：不同的整数有 "123"、"34" 和 "8" 。注意，"34" 只计数一次。
示例 2：
输入：word = "leet1234code234"
输出：2
示例 3：
输入：word = "a1b01c001"
输出：1
解释："1"、"01" 和 "001" 视为同一个整数的十进制表示，因为在比较十进制值时会忽略前导零的存在。
提示：
1 <= word.length <= 1000word由数字和小写英文字母组成
题解
先用正则将字符串中的字母替换成空格，再进行拆分，最后将数字存入字典即可
class Solution:
def numDifferentIntegers(self, word: str) -> int:
D=dict()
for s in re.split(r'[a-z]+',word):
if s != '':
D[int(s)]=1
return len(D)
1806. 还原排列的最少操作步数
给你一个偶数 n ，已知存在一个长度为 n 的排列 perm ，其中 perm[i] == i（下标 从 0 开始 计数）。
一步操作中，你将创建一个新数组 arr ，对于每个 i ：
- 如果
i % 2 == 0，那么arr[i] = perm[i / 2] - 如果
i % 2 == 1，那么arr[i] = perm[n / 2 + (i - 1) / 2]
然后将 arr 赋值给 perm 。
要想使 perm 回到排列初始值，至少需要执行多少步操作？返回最小的 非零 操作步数。
示例 1：
输入：n = 2
输出：1
解释：最初，perm = [0,1]
第 1 步操作后，perm = [0,1]
所以，仅需执行 1 步操作
示例 2：
输入：n = 4
输出：2
解释：最初，perm = [0,1,2,3]
第 1 步操作后，perm = [0,2,1,3]
第 2 步操作后，perm = [0,1,2,3]
所以，仅需执行 2 步操作
示例 3：
输入：n = 6
输出：4
提示：
2 <= n <= 1000n是一个偶数
题解
对于 n=10 的情况，先观察数组的变化
n=10
perm=list(range(n))
arr=[0]*n
print(perm)
for _ in range(8):
for i in range(n):
if i%2==0:
arr[i]= perm[i // 2]
else:
arr[i] = perm[n // 2 + (i - 1) // 2]
perm=arr.copy()
print(arr)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 5, 1, 6, 2, 7, 3, 8, 4, 9]
[0, 7, 5, 3, 1, 8, 6, 4, 2, 9]
[0, 8, 7, 6, 5, 4, 3, 2, 1, 9]
[0, 4, 8, 3, 7, 2, 6, 1, 5, 9]
[0, 2, 4, 6, 8, 1, 3, 5, 7, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 5, 1, 6, 2, 7, 3, 8, 4, 9]
[0, 7, 5, 3, 1, 8, 6, 4, 2, 9]
暂时没有找到规律，再看结果的变化
for n in range(2,30,2):
perm=list(range(n))
L=perm.copy()
arr=[0]*n
for k in range(100):
for i in range(n):
if i%2==0:
arr[i]= perm[i // 2]
else:
arr[i] = perm[n // 2 + (i - 1) // 2]
perm=arr.copy()
if arr==L:
print(n,k+1)
break
2 1
4 2
6 4
8 3
10 6
12 10
14 12
16 4
18 8
20 18
22 6
24 11
26 20
28 18
左边是 n， 右边是结果，这些数字中也没有发现什么规律。
只好再返回去看，0 和9 的位置其实都没有动，我们可以猜测只要1 归位了，其他数字也会归位。假设 1 的当前位置为 i ，那么其变化规律为：
- 若
2*i ≤ (n-1)，则i —> 2*i - 若
2*i > (n-1)，则i —> 2*i-(n-1)
总结起来就是 i —> 2*i % (n-1)
其实这个问题等价于找到最小的 k，使得 #card=math&code=2%5Ek%5Cequiv%201%5Cquad%20%5Cmathrm%7Bmod%7D%20%5Cleft%28%20n-1%20%5Cright%29)
数学上似乎没有直接的公式求解，所以只能模拟了：
class Solution:
def reinitializePermutation(self, n: int) -> int:
i=1
k=0
while i!=1 or k==0:
k+=1
if 2*i<n:
i=2*i
else:
i=2*i-(n-1)
return k
5714. 替换字符串中的括号内容
给你一个字符串 s ，它包含一些括号对，每个括号中包含一个 非空 的键。
- 比方说，字符串
"(name)is(age)yearsold"中，有 两个 括号对，分别包含键"name"和"age"。
你知道许多键对_应的值，这些关系由二维字符串数组 knowledge 表示，其中 knowledge[i] = [key_i , valuei] ，表示键 key_i 对应的值为 value_i 。
你需要替换 所有 的括号对。当你替换一个括号对，且它包含的键为 key_i 时，你需要：
- 将
key_i和括号用对应的值value_i替换。 - 如果从
knowledge中无法得知某个键对应的值，你需要将key_i和括号用问号"?"替换（不需要引号）。
knowledge 中每个键最多只会出现一次。s 中不会有嵌套的括号。
请你返回替换 所有 括号对后的结果字符串。
示例 1：
输入：s = "(name)is(age)yearsold", knowledge = [["name","bob"],["age","two"]]
输出："bobistwoyearsold"
解释：
键 "name" 对应的值为 "bob" ，所以将 "(name)" 替换为 "bob" 。
键 "age" 对应的值为 "two" ，所以将 "(age)" 替换为 "two" 。
示例 2：
输入：s = "hi(name)", knowledge = [["a","b"]]
输出："hi?"
解释：由于不知道键 "name" 对应的值，所以用 "?" 替换 "(name)" 。
示例 3：
输入：s = "(a)(a)(a)aaa", knowledge = [["a","yes"]]
输出："yesyesyesaaa"
解释：相同的键在 s 中可能会出现多次。
键 "a" 对应的值为 "yes" ，所以将所有的 "(a)" 替换为 "yes" 。
注意，不在括号里的 "a" 不需要被替换。
示例 4：
输入：s = "(a)(b)", knowledge = [["a","b"],["b","a"]]
输出："ba"
提示：
1 <= s.length <= 10^50 <= knowledge.length <= 10^5knowledge[i].length == 21 <= key_i.length, value_i.length <= 10s只包含小写英文字母和圆括号'('和')'。s中每一个左圆括号'('都有对应的右圆括号')'。s中每对括号内的键都不会为空。s中不会有嵌套括号对。keyi和value_i只包含小写英文字母。knowledge中的key_i不会重复。
题解
直接使用正则表达式替换即可
class Solution:
def evaluate(self, s: str, knowledge: List[List[str]]) -> str:
D = dict()
for key, val in knowledge:
D[key] = val
def f(matched):
s = matched.group(1)
if s in D:
return D[s]
else:
return '?'
return re.sub(r'\((.*?)\)', f, s)
5716. 好因子的最大数目
给你一个正整数 primeFactors 。你需要构造一个正整数 n ，它满足以下条件：
n质因数（质因数需要考虑重复的情况）的数目 不超过primeFactors个。n好因子的数目最大化。如果n的一个因子可以被n的每一个质因数整除，我们称这个因子是 好因子 。比方说，如果n = 12，那么它的质因数为[2,2,3]，那么6和12是好因子，但3和4不是。
请你返回 n 的好因子的数目。由于答案可能会很大，请返回答案对 10^9 + 7 取余 的结果。
请注意，一个质数的定义是大于 1 ，且不能被分解为两个小于该数的自然数相乘。一个数 n 的质因子是将 n 分解为若干个质因子，且它们的乘积为 n 。
示例 1：
输入：primeFactors = 5
输出：6
解释：200 是一个可行的 n 。
它有 5 个质因子：[2,2,2,5,5] ，且有 6 个好因子：[10,20,40,50,100,200] 。
不存在别的 n 有至多 5 个质因子，且同时有更多的好因子。
示例 2：
输入：primeFactors = 8
输出：18
提示：
1 <= primeFactors <= 10^9
题解
本质上就是将 primeFactors 拆成多个数之和，使得这些数的乘积最大。
我们假设拆成 n 个数 ，有
，由均值不等式可知：
也就是说这些数相等时，乘积取最大值，即 ，于是有：
%20%3Dx_1x_2%5Ccdots%20x_n%3D%5Cleft(%20%5Cfrac%7BM%7D%7Bn%7D%20%5Cright)%20%5En%0A#card=math&code=f%5Cleft%28%20n%20%5Cright%29%20%3Dx_1x_2%5Ccdots%20x_n%3D%5Cleft%28%20%5Cfrac%7BM%7D%7Bn%7D%20%5Cright%29%20%5En%0A)
%20%5En%5Cleft(%20%5Clog%20%5Cfrac%7BM%7D%7Bn%7D-1%20%5Cright)%C2%A0%0A#card=math&code=y%5E%7B%5Cprime%7D%3D%5Cleft%28%20%5Cfrac%7BM%7D%7Bn%7D%20%5Cright%29%20%5En%5Cleft%28%20%5Clog%20%5Cfrac%7BM%7D%7Bn%7D-1%20%5Cright%29%C2%A0%0A)
也就是说当 时，乘积取到最大值。
但由于 n 为整数， 也应该为整数，所以只能取最接近
的数，也就是3。
也就是说，拆分出越多的3，结果大概会更大。%20%3D%5Cmax_i%20%5Cleft%5C%7B%20f%5Cleft(%20M-i%20%5Cright)%20%5Ccdot%20i%20%5Cright%5C%7D%C2%A0%0A#card=math&code=f%5Cleft%28%20M%20%5Cright%29%20%3D%5Cmax_i%20%5Cleft%5C%7B%20f%5Cleft%28%20M-i%20%5Cright%29%20%5Ccdot%20i%20%5Cright%5C%7D%C2%A0%0A)
我们再分析拆分的因子 会有哪些情况：
- 此时
不会是最优的，因为
%20%5E2#card=math&code=x%3C%5Cleft%28%20%5Cfrac%7Bx%7D%7B2%7D%20%5Cright%29%20%5E2)
- 所以将
和
乘积会更大
- 此时
- 可以视为拆分成
- 可以视为拆分成
- 明显不是最优解
也就是说，最终拆分出来的因子 只可能为 2 或 3，而其中 3 要尽可能越多越好。
所以求解方案如下：
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)
注意如果直接求幂的话，可能会超时，这时可以用快速幂优化：
def quick_pow(a=3, n=1, MOD=1000000007):
res = 1
pow2 = a
while n >= 1:
if n & 1:
res = res * pow2 % MOD
pow2 = pow2 * pow2 % MOD
n = n >> 1
return res
若有收获，就点个赞吧
0 人点赞
