Re: [閒聊] 每日leetcode
今天是第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
推
11/20 22:00,
1年前
, 1F
11/20 22:00, 1F
推
11/20 22:12,
1年前
, 2F
11/20 22:12, 2F
推
11/21 01:28,
1年前
, 3F
11/21 01:28, 3F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1133 之 1554 篇)：