Re: [閒聊] 每日leetcode

[JIWP (神楽めあ的錢包)]

今天是第365天寫每日

一年了 有夠快

2516. Take K of Each Character From Left and Right

有一個長度為n的字串s是由a、b、c組成的

每一分鐘可以從最左邊或是最右邊拿走一個字母

請問最少要幾分鐘才可以每個字母最少拿到k個?

思路 :

就sliding window + hash table

先假設L=0、R=n

將L往右拿字母一直到滿足題目要求的條件

接著開始將L往左

只要L往左後沒有滿足條件

就將R往左一直到重新滿足條件

中間就一直維護最短長度就好

這樣就可以得到答案了

golang code :

func takeCharacters(s string, k int) int {
        if k==0{
        return 0
    }
    n, l, cnt, rec := len(s), 0, 0, [3]int{}
        r := n
        for l < n {
                idx := int(s[l] - 'a')
                rec[idx]++
                if rec[idx] == k {
                        cnt++
                }
                if cnt == 3 {
                        break
                }
                l++
        }
        if l == n {
                return -1
        }
        ans := l + 1
        for l > -1 {
                idx := int(s[l] - 'a')
                rec[idx]--
                l--
                if rec[idx] < k {
                        cnt--
                }
                for cnt < 3 {
                        r--
                        idx1 := int(s[r] - 'a')
                        rec[idx1]++
                        if rec[idx1] == k {
                                cnt++
                        }
                }
                ans = min(ans, n-(r-l-1))
        }
        return ans
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.255.203 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1732111152.A.832.html
推 sustainer123: 大師
推 oin1104: 大師
推 dont: 大師