leetcode 1758

yujianwjj 1月前 21

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 22天前
    引用 2
    如果 S ^ A = 010101...
    那 S ^ ~A = 101010...
    A 和~A 互补,两个数中 1 的数量总和就是长度。
  • 游客
    3
返回