Re: [閒聊] 每日leetcode
今天的每日寫過了
改寫別題
1234. Replace the Substring for Balanced String
先算出Q、W、E、R各自的數量
再算已經平衡的組數、還沒平衡的組數
接著把Q、W、E、R各自的數量 - 已經平衡的組數
如果 > 0那就是多餘的字母，可以替換成別的字母
接著就用slinding window找出長度最短且含有多於字母的子字串
golang code :
func balancedString(s string) int {
n := len(s)
rec := make([]int, 4)
start, ans := 0, n+1
for i := 0; i < n; i++ {
idx := findIdx(s[i])
rec[idx]++
}
curBalanceNum := min(rec[0], rec[1], rec[2], rec[3])
unBalanceNum := n/4 - curBalanceNum
if unBalanceNum == 0 {
return 0
}
need, cnt, curNum := make([]int, 4), 0, []int{0, 0, 0, 0}
for i := 0; i < 4; i++ {
need[i] = max(0, rec[i]-curBalanceNum-unBalanceNum)
if need[i] == 0 {
cnt++
}
}
for i := 0; i < n; i++ {
idx := findIdx(s[i])
curNum[idx]++
if need[idx] != 0 && curNum[idx] == need[idx] {
cnt++
}
for cnt == 4 {
ans = min(ans, i-start+1)
idx = findIdx(s[start])
curNum[idx]--
if need[idx] != 0 && curNum[idx] < need[idx] {
cnt--
}
start++
}
}
return ans
}
func findIdx(n byte) int {
if n == 'Q' {
return 0
} else if n == 'W' {
return 1
} else if n == 'E' {
return 2
} else {
return 3
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.121.235.241 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1752495520.A.0A2.html
推
07/14 20:59,
4月前
, 1F
07/14 20:59, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1465 之 1548 篇)：