首先是 424. Longest Repeating Character Replacement (medium)
https://leetcode.com/problems/longest-repeating-character-replacement/
這題會給予一個字串s跟一個正整數k,正整數k代表可以替換的字母數量,要找出當字串s被替換k個字母時,最多可以多長。
老實說這題滿麻煩的,第一次寫的時候近乎翻車。
想法:
class Solution:
#可以把k個字元替換成其他字元
def characterReplacement(self, s: str, k: int) -> int:
sL = len(s)
tempD = defaultdict(int)#用來儲存被選取範圍內的
L = 0
ans = 0
for R in range(sL):
tempD[s[R]] += 1
count = R-L+1#目前選取到的單位數量
if count - max(tempD.values())<=k:#如果選取的區域的最多元素超過一半的話
ans = max(ans,count)#就有機會是答案
else:#因為選到的區域已經夠大了,主要目的就是找到下一個最多元素,因此左邊可以開始向右移
tempD[s[L]] -= 1
if tempD[s[L]] == 0:
tempD.pop(s[L])
L+=1
# print(tempD)
return ans
再來是 299. Bulls and Cows (medium)
就1A2B(一個簡單的小遊戲)
class Solution:
#阿就1A2B
#1. 數字的總數
#2. 數字位置
def getHint(self, secret: str, guess: str) -> str:
sL = defaultdict(set)#secret 儲存數字的位置用
gL = defaultdict(set)#guess 儲存數字的位置用
for i in range(len(secret)):
sL[secret[i]].add(i)
for i in range(len(guess)):
gL[guess[i]].add(i)
print(sL)
print(gL)
A,B =0,0
for i in gL:
tempA,tempB = 0,0
if i in sL:
tempG = gL[i]
tempS = sL[i]
tempB = len(gL[i]) if len(sL[i]) > len(gL[i]) else len(sL[i]) #B
tempA = len(tempG & tempS) #A
A+=tempA
B+=tempB-tempA
# print(f"{A}A{B}B")
return f"{A}A{B}B"
一開始寫複雜了,後來思考了一下,可以更加輕鬆一點
zip之後直接比較就好
def getHint(self, secret: str, guess: str) -> str:
sB, gB = defaultdict(int), defaultdict(int)
A, B = 0, 0
for s, g in zip(secret, guess):
if s == g:
A += 1
else:
sB[s] += 1
gB[g] += 1
for i in sB:
if i in gB:
B += min(sB[i], gB[i])
return f"{A}A{B}B"
再來是 1578. Minimum Time to Make Rope Colorful (medium)
https://leetcode.com/problems/minimum-time-to-make-rope-colorful/
相同顏色的氣球不可以碰在一起,除此之外,刪除氣球需要花費一些時間,要計算出最小時間。
寫這題時要注意題目敘述,我原本以為氣球不會遞移,導致說寫出來的東西根本不對==
那會遞移的話其實就很簡單
class Solution:
#要找出重復的地方
#3個以上的重複要有些許技巧進行計算
#幹他媽我誤會了,原來氣球會往前遞移
def minCost(self, colors: str, neededTime: List[int]) -> int:
cLs = len(colors)
if cLs == len(set(colors)):
return 0
flag = 0
i=1
ans = 0
while i < cLs:
temp = {i-1}
while i<cLs and colors[i] == colors[i-1]:
temp.add(i)
i+=1
flag = 1
#沒有同顏色,開始比較
if flag:
temp = list(temp)
# ans+=min(sum(neededTime[j] for j in temp[:-1]),sum(neededTime[j] for j in temp[1:]))
temptemp = [neededTime[j] for j in temp]
sT = sum(temptemp)
mT = max(temptemp)
ans+=sT-mT
flag = 0
i+=1
# print(ans)
return ans
以上為今天的練習,感謝觀看