当前位置：首页 > article >正文

【LeetCode】每日一题 2024_10_19 使二进制数组全部等于 1 的最少操作次数 II（贪心）

article 2024/10/23 0:28:04

前言

每天和你一起刷 LeetCode 每日一题~

LeetCode 启动！

题目：使二进制数组全部等于 1 的最少操作次数 II

力扣每日一题刷新规律，昨天刷新了 I，那今天必定有 II。

代码与解题思路

今天的题目和昨天的非常像，只有一个地方做了改变：“将从下标 i 开始一直到数组末尾所有元素反转”，从 3 个数的反转变成了后续所有元素的反转（看着就像加复杂度的条件）

不过我还是打算直接从昨天总结的思路入手尝试：

func minOperations(nums []int) (ans int) {
    // 直接用昨天那道题的思路试试
    for i, v := range nums {
        if v == 0 {
            for j := i; j < len(nums); j++ { // 并将从下标 i 开始一直到数组末尾所有元素反转
                nums[j] ^= 1
            }
            ans++
        }
    }
    return ans
}

事实证明并没有这种好事 . . . 如果两道题都能用一模一样的解法完成，那就不用出 2 了。来想想看怎么优化，很明显，消耗时间最多的地方就是当 v == 0 之后进行的遍历模拟，如果可以的话，能不能只进行 ans++ 的操作呢？

0 反转之后会变成 1，1 反转之后会变成 0，也就是只要反转两次，那就没有任何变化，只反转 1 次，那曾经的 1 就是 0，0 就是 1，也许我们可以从这个思路入手：

func minOperations(nums []int) (ans int) {
    for _, v := range nums {
        // 当 ans 是偶数的时候，ans & 1 == 0
        // 当 ans 是奇数的时候，ans & 1 == 1
        // 只有在 v == ans 的情况才会计数
        if v == ans & 1 {
            ans++
        }
    }
    return ans
}