iT邦幫忙

2022 iThome 鐵人賽

DAY 19
0
自我挑戰組

leetcode 30天 不中斷解題挑戰系列 第 19

Day19 leetcode隨機挑題 (Greedy、Sliding Window)

  • 分享至 

  • xImage
  •  

首先是 424. Longest Repeating Character Replacement (medium)
https://leetcode.com/problems/longest-repeating-character-replacement/

這題會給予一個字串s跟一個正整數k,正整數k代表可以替換的字母數量,要找出當字串s被替換k個字母時,最多可以多長。

老實說這題滿麻煩的,第一次寫的時候近乎翻車。
想法:

  1. 要建立一個方便計算字母數量的東西defaultdict()最為方便
  2. 迭代字串s,建立兩指標,L指左R指右。
  3. 建立一變數計算選取的單位數
  4. 計算L與R選取範圍內的最多字母是誰,若選取範圍扣掉此字母數量小於k代表可以繼續抓。
  5. 若沒有的話代表選取的字母過多,L開始往右移。
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/

相同顏色的氣球不可以碰在一起,除此之外,刪除氣球需要花費一些時間,要計算出最小時間。

寫這題時要注意題目敘述,我原本以為氣球不會遞移,導致說寫出來的東西根本不對==

那會遞移的話其實就很簡單

  1. 迭代氣球
  2. 找出有相同顏色的範圍
  3. 計算出這區間的總時間
  4. 留下時間要花最久的,其他拿走
  5. 結束
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

以上為今天的練習,感謝觀看


上一篇
Day18 leetcode Weekly Contest 313
下一篇
Day20 leetcode隨機挑題 (Stack、Two Pointer、String)
系列文
leetcode 30天 不中斷解題挑戰30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言