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" 视为同一个整数的十进制表示，因为在比较十进制值时会忽略前导零的存在。

分析：

作为周赛第一道简单题，在字符串中截取数字，完成计数后返回，本身没有太多难度，这里需要注意两点：

1. 重复的数字只记录一次，那么使用set集合来计数比较方便。
2. 前导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