V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
yujianwjj
V2EX  ›  LeetCode

leetcode 1758

  •  
  •   yujianwjj · 2021-04-08 12:35:41 +08:00 · 1962 次点击
    这是一个创建于 1323 天前的主题,其中的信息可能已经有所发展或是发生改变。

    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 条回复    2021-04-08 12:53:15 +08:00
    misdake
        1
    misdake  
       2021-04-08 12:53:15 +08:00
    如果 S ^ A = 010101...
    那 S ^ ~A = 101010...
    A 和~A 互补,两个数中 1 的数量总和就是长度。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3049 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 12:59 · PVG 20:59 · LAX 04:59 · JFK 07:59
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.