5713. 字符串中不同整數(shù)的數(shù)目
https://leetcode-cn.com/problems/number-of-different-integers-in-a-string/
難度：簡(jiǎn)單
題目：
給你一個(gè)字符串 word ，該字符串由數(shù)字和小寫(xiě)英文字母組成遍尺。
請(qǐng)你用空格替換每個(gè)不是數(shù)字的字符截酷。例如，"a123bc34d8ef34" 將會(huì)變成 " 123 34 8 34" 乾戏。注意迂苛，剩下的這些整數(shù)為（相鄰彼此至少有一個(gè)空格隔開(kāi)）："123"、"34"鼓择、"8" 和 "34" 三幻。
返回對(duì) word 完成替換后形成的 不同 整數(shù)的數(shù)目。
只有當(dāng)兩個(gè)整數(shù)的 不含前導(dǎo)零 的十進(jìn)制表示不同呐能， 才認(rèn)為這兩個(gè)整數(shù)也不同念搬。
提示：
1 <= word.length <= 1000
word 由數(shù)字和小寫(xiě)英文字母組成
示例：
示例 1：
輸入：word = "a123bc34d8ef34"
輸出：3
解釋?zhuān)翰煌恼麛?shù)有 "123"、"34" 和 "8" 摆出。注意朗徊，"34" 只計(jì)數(shù)一次。
示例 2：
輸入：word = "leet1234code234"
輸出：2
示例 3：
輸入：word = "a1b01c001"
輸出：1
解釋?zhuān)?1"偎漫、"01" 和 "001" 視為同一個(gè)整數(shù)的十進(jìn)制表示爷恳，因?yàn)樵诒容^十進(jìn)制值時(shí)會(huì)忽略前導(dǎo)零的存在。
分析
作為周賽第一道簡(jiǎn)單題象踊，在字符串中截取數(shù)字舌仍，完成計(jì)數(shù)后返回，本身沒(méi)有太多難度通危，這里需要注意兩點(diǎn)：
- 重復(fù)的數(shù)字只記錄一次，那么使用set集合來(lái)計(jì)數(shù)比較方便灌曙。
- 前導(dǎo)0的數(shù)字需要忽略菊碟，通過(guò)這個(gè)條件我們可以使用棧來(lái)記錄臨時(shí)數(shù)字。當(dāng)數(shù)字入棧前判斷棧的長(zhǎng)度是否為1且值為0.
如果是這樣在刺，出棧0后再入棧逆害。這道題前10的選手好幾人因?yàn)檫@點(diǎn)都出現(xiàn)了提交錯(cuò)誤头镊，值得重視細(xì)節(jié)。
解題：
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. 替換字符串中的括號(hào)內(nèi)容
https://leetcode-cn.com/problems/evaluate-the-bracket-pairs-of-a-string/
難度：中等
題目：
給你一個(gè)字符串 s 魄幕，它包含一些括號(hào)對(duì)相艇，每個(gè)括號(hào)中包含一個(gè) 非空 的鍵。
比方說(shuō)纯陨，字符串 "(name)is(age)yearsold" 中坛芽，有 兩個(gè) 括號(hào)對(duì)，分別包含鍵 "name" 和 "age" 翼抠。
你知道許多鍵對(duì)應(yīng)的值咙轩，這些關(guān)系由二維字符串?dāng)?shù)組 knowledge 表示，其中 knowledge[i] = [keyi, valuei] 阴颖，表示鍵 keyi 對(duì)應(yīng)的值為 valuei 活喊。
你需要替換 所有 的括號(hào)對(duì)。當(dāng)你替換一個(gè)括號(hào)對(duì)量愧，且它包含的鍵為 keyi 時(shí)钾菊，你需要：
將 keyi 和括號(hào)用對(duì)應(yīng)的值 valuei 替換。
如果從 knowledge 中無(wú)法得知某個(gè)鍵對(duì)應(yīng)的值偎肃，你需要將 keyi 和括號(hào)用問(wèn)號(hào) "?" 替換（不需要引號(hào)）煞烫。
knowledge 中每個(gè)鍵最多只會(huì)出現(xiàn)一次。s 中不會(huì)有嵌套的括號(hào)软棺。
請(qǐng)你返回替換 所有 括號(hào)對(duì)后的結(jié)果字符串红竭。
提示：
1 <= s.length <= 105
0 <= knowledge.length <= 105
knowledge[i].length == 2
1 <= keyi.length, valuei.length <= 10
s 只包含小寫(xiě)英文字母和圓括號(hào) '(' 和 ')' 。
s 中每一個(gè)左圓括號(hào) '(' 都有對(duì)應(yīng)的右圓括號(hào) ')' 喘落。
s 中每對(duì)括號(hào)內(nèi)的鍵都不會(huì)為空茵宪。
s 中不會(huì)有嵌套括號(hào)對(duì)。
keyi 和 valuei 只包含小寫(xiě)英文字母瘦棋。
knowledge 中的 keyi 不會(huì)重復(fù)稀火。
示例：
示例 1：
輸入：s = "(name)is(age)yearsold", knowledge = [["name","bob"],["age","two"]]
輸出："bobistwoyearsold"
解釋?zhuān)?/p>
鍵 "name" 對(duì)應(yīng)的值為 "bob" ，所以將 "(name)" 替換為 "bob" 赌朋。
鍵 "age" 對(duì)應(yīng)的值為 "two" 凰狞，所以將 "(age)" 替換為 "two" 。
示例 2：
輸入：s = "hi(name)", knowledge = [["a","b"]]
輸出："hi?"
解釋?zhuān)?br> 由于不知道鍵 "name" 對(duì)應(yīng)的值沛慢，所以用 "?" 替換 "(name)" 赡若。
示例 3：
輸入：s = "(a)(a)(a)aaa", knowledge = [["a","yes"]]
輸出："yesyesyesaaa"
解釋?zhuān)?br>
相同的鍵在 s 中可能會(huì)出現(xiàn)多次。
鍵 "a" 對(duì)應(yīng)的值為 "yes" 团甲，所以將所有的 "(a)" 替換為 "yes" 逾冬。
注意，不在括號(hào)里的 "a" 不需要被替換。
示例 4：
輸入：s = "(a)(b)", knowledge = [["a","b"],["b","a"]]
輸出："ba"
分析
很奇怪這道題居然很多人會(huì)超時(shí)...
看到括號(hào)匹配身腻，優(yōu)先去考慮棧的操作
這道題的knowledge明顯可以被轉(zhuǎn)換成字典
然后根據(jù)左右括號(hào)产还，完成出入棧與key的判斷，輕松解題即可嘀趟！
解題：
class Solution:
def evaluate(self, s, knowledge):
# 轉(zhuǎn)換knowl為字典
paras = {i[0]: i[1] for i in knowledge}
stack = []
ret = ''
# 創(chuàng)建轉(zhuǎn)換標(biāo)識(shí)符
change = False
for i in s:
# 當(dāng)左括號(hào)將標(biāo)識(shí)符設(shè)置為T(mén)rue
if i == '(':
change = True
elif i == ')':
# 當(dāng)遇到右括號(hào)脐区，重置標(biāo)識(shí)符與stack并開(kāi)始判斷knowledge
change = False
ret += paras.get(''.join(stack), '?')
stack = []
else:
# change為False追加字符串，為T(mén)rue時(shí)append棧等待獲取key
if change:
stack.append(i)
else:
ret += i
return ret
1806. 還原排列的最少操作步數(shù)
https://leetcode-cn.com/problems/minimum-number-of-operations-to-reinitialize-a-permutation/
難度：中等
題目：
給你一個(gè)偶數(shù) n 她按，已知存在一個(gè)長(zhǎng)度為 n 的排列 perm 牛隅，其中 perm[i] == i（下標(biāo) 從 0 開(kāi)始 計(jì)數(shù)）。
一步操作中尤溜，你將創(chuàng)建一個(gè)新數(shù)組 arr 倔叼，對(duì)于每個(gè) i ：
如果 i % 2 == 0 ，那么 arr[i] = perm[i / 2]
如果 i % 2 == 1 宫莱，那么 arr[i] = perm[n / 2 + (i - 1) / 2]
然后將 arr 賦值給 perm 丈攒。
要想使 perm 回到排列初始值，至少需要執(zhí)行多少步操作授霸？返回最小的 非零 操作步數(shù)巡验。
示例：
示例 1：
輸入：n = 2
輸出：1
解釋?zhuān)鹤畛酰琾erm = [0,1]
第 1 步操作后碘耳，perm = [0,1]
所以显设，僅需執(zhí)行 1 步操作
示例 2：
輸入：n = 4
輸出：2
解釋?zhuān)鹤畛酰琾erm = [0,1,2,3]
第 1 步操作后辛辨，perm = [0,2,1,3]
第 2 步操作后捕捂，perm = [0,1,2,3]
所以，僅需執(zhí)行 2 步操作
示例 3：
輸入：n = 6
輸出：4
分析
這道題卡了很久斗搞，一直在想有什么變換的規(guī)律指攒，最終還是放棄了
剛開(kāi)始使用遞歸整個(gè)數(shù)組遍歷，獲取數(shù)組的變更僻焚，代碼量比較多
但算是通過(guò)了...
下午看到一個(gè)大佬的解題允悦，自慚形穢，分享給大家虑啤。
其實(shí)規(guī)律就是那么簡(jiǎn)單隙弛，只是一個(gè)半小時(shí)時(shí)間太短沒(méi)時(shí)間考慮啊...
解題1：
列表復(fù)制，遞歸判斷列表內(nèi)容是否相等
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
歡迎關(guān)注我的公眾號(hào): 清風(fēng)Python
我的個(gè)人博客：https://qingfengpython.cn
