2938. 区分黑球与白球

区分黑球与白球

解法一: 双指针

go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func minimumSteps(s string) int64 {
n := len(s)
bytes := []byte(s)
left := n - 1
right := n - 1
ans := int64(0)
for {
for right >= 0 && bytes[right] == '1' {
right--
}
left = min(left, right-1)
for left >= 0 && bytes[left] == '0' {
left--
}
if left < 0 {
break
}
bytes[left], bytes[right] = bytes[right], bytes[left]
ans += int64(right - left)
}
return ans
}

解法二: 逆向思维

go
1
2
3
4
5
6
7
8
9
10
11
12
func minimumSteps(s string) int64 {
ans := int64(0)
sum := 0
for _, ch := range s {
if ch == '1' {
sum++
} else {
ans += int64(sum)
}
}
return ans
}
作者

wuhunyu

发布于

2024-06-06

更新于

2025-01-15

许可协议