https://leetcode.com/problems/minimum-changes-to-make-alternating-binary-string/
题目比较简单,只有 010101... 或者 101010... 两个方案 最开始我的解法是:
func minOperations(s string) int {
count1 := 0
// 010101...
for i := 0; i < len(s); i++ {
if int(s[i] - '0') != i % 2 {
count1++
}
}
count2 := 0
// 10101010...
for i := 0; i < len(s); i++ {
if int(s[i] - '0') != (i+1) % 2 {
count2++
}
}
return min(count1, count2)
}
后来发现更简单一点的
func minOperations(s string) int {
count1 := 0
// 010101...
for i := 0; i < len(s); i++ {
if int(s[i] - '0') != i % 2 {
count1++
}
}
return min(count1, len(s)-count1)
}
我的疑问是如何用数学证明这两种方案加起来刚好是 s 的长度。
1
misdake 2021-04-08 12:53:15 +08:00
如果 S ^ A = 010101...
那 S ^ ~A = 101010... A 和~A 互补,两个数中 1 的数量总和就是长度。 |