5713. 字符串中不同整数的数目
https://leetcode-cn.com/problems/number-of-different-integers-in-a-string/
难度：简单
题目：
给你一个字符串 word ，该字符串由数字和小写英文字母组成。
请你用空格替换每个不是数字的字符。例如，"a123bc34d8ef34" 将会变成 " 123 34 8 34" 。注意，剩下的这些整数为（相邻彼此至少有一个空格隔开）："123"、"34"、"8" 和 "34" 。
返回对 word 完成替换后形成的 不同 整数的数目。
只有当两个整数的 不含前导零 的十进制表示不同， 才认为这两个整数也不同。
提示：
1 <= word.length <= 1000
word 由数字和小写英文字母组成
示例：
示例 1：
输入：word = "a123bc34d8ef34"
输出：3
解释：不同的整数有 "123"、"34" 和 "8" 。注意，"34" 只计数一次。
示例 2：
输入：word = "leet1234code234"
输出：2
示例 3：
输入：word = "a1b01c001"
输出：1
解释："1"、"01" 和 "001" 视为同一个整数的十进制表示，因为在比较十进制值时会忽略前导零的存在。
分析
作为周赛第一道简单题，在字符串中截取数字，完成计数后返回，本身没有太多难度，这里需要注意两点：
- 重复的数字只记录一次，那么使用set集合来计数比较方便。
- 前导0的数字需要忽略，通过这个条件我们可以使用栈来记录临时数字。当数字入栈前判断栈的长度是否为1且值为0.
如果是这样，出栈0后再入栈。这道题前10的选手好几人因为这点都出现了提交错误，值得重视细节。
解题：
class Solution:
def numDifferentIntegers(self, word):
ret = set()
stack = []
for i in word:
if i.isdigit():
if len(stack) == 1 and stack[-1] == '0':
stack.pop()
stack.append(i)
else:
if stack:
ret.add(''.join(stack))
stack = []
if stack:
ret.add(''.join(stack))
return len(ret)
5714. 替换字符串中的括号内容
https://leetcode-cn.com/problems/evaluate-the-bracket-pairs-of-a-string/
难度：中等
题目：
给你一个字符串 s ，它包含一些括号对，每个括号中包含一个 非空 的键。
比方说，字符串 "(name)is(age)yearsold" 中，有 两个 括号对，分别包含键 "name" 和 "age" 。
你知道许多键对应的值，这些关系由二维字符串数组 knowledge 表示，其中 knowledge[i] = [keyi, valuei] ，表示键 keyi 对应的值为 valuei 。
你需要替换 所有 的括号对。当你替换一个括号对，且它包含的键为 keyi 时，你需要：
将 keyi 和括号用对应的值 valuei 替换。
如果从 knowledge 中无法得知某个键对应的值，你需要将 keyi 和括号用问号 "?" 替换（不需要引号）。
knowledge 中每个键最多只会出现一次。s 中不会有嵌套的括号。
请你返回替换 所有 括号对后的结果字符串。
提示：
1 <= s.length <= 105
0 <= knowledge.length <= 105
knowledge[i].length == 2
1 <= keyi.length, valuei.length <= 10
s 只包含小写英文字母和圆括号 '(' 和 ')' 。
s 中每一个左圆括号 '(' 都有对应的右圆括号 ')' 。
s 中每对括号内的键都不会为空。
s 中不会有嵌套括号对。
keyi 和 valuei 只包含小写英文字母。
knowledge 中的 keyi 不会重复。
示例：
示例 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"
分析
很奇怪这道题居然很多人会超时...
看到括号匹配，优先去考虑栈的操作
这道题的knowledge明显可以被转换成字典
然后根据左右括号，完成出入栈与key的判断，轻松解题即可！
解题：
class Solution:
def evaluate(self, s, knowledge):
# 转换knowl为字典
paras = {i[0]: i[1] for i in knowledge}
stack = []
ret = ''
# 创建转换标识符
change = False
for i in s:
# 当左括号将标识符设置为True
if i == '(':
change = True
elif i == ')':
# 当遇到右括号，重置标识符与stack并开始判断knowledge
change = False
ret += paras.get(''.join(stack), '?')
stack = []
else:
# change为False追加字符串，为True时append栈等待获取key
if change:
stack.append(i)
else:
ret += i
return ret
1806. 还原排列的最少操作步数
https://leetcode-cn.com/problems/minimum-number-of-operations-to-reinitialize-a-permutation/
难度：中等
题目：
给你一个偶数 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
分析
这道题卡了很久，一直在想有什么变换的规律，最终还是放弃了
刚开始使用递归整个数组遍历，获取数组的变更，代码量比较多
但算是通过了...
下午看到一个大佬的解题，自惭形秽，分享给大家。
其实规律就是那么简单，只是一个半小时时间太短没时间考虑啊...
解题1：
列表复制，递归判断列表内容是否相等
from copy import copy
class Solution:
def __init__(self):
self.n = 0
self.perm = []
self.count = 0
def change(self, perm):
arr = copy(perm)
for i in range(self.n):
if i % 2 == 0:
arr[i] = perm[i // 2]
else:
arr[i] = perm[self.n // 2 + (i - 1) // 2]
print(arr)
self.count += 1
if arr == self.perm:
return self.count
else:
return self.change(arr)
def reinitializePermutation(self, n: int) -> int:
self.n = n
self.perm = [i for i in range(self.n)]
return self.change(self.perm)
解题2：
class Solution:
def reinitializePermutation(self, n: int) -> int:
count = 1
origin = [i for i in range(n)]
arr = origin[::2]+origin[1::2]
while origin != arr:
arr = arr[::2]+arr[1::2]
count += 1
return count
欢迎关注我的公众号: 清风Python
我的个人博客：https://qingfengpython.cn
