1529. 灯泡开关 IV #

问题描述#

房间中有 n 个灯泡，编号从 0 到 n-1 ，自左向右排成一行。最开始的时候，所有的灯泡都是关着的。

请你设法使得灯泡的开关状态和 target 描述的状态一致，其中 target[i] 等于 1 第 i 个灯泡是开着的，等于 0 意味着第 i 个灯是关着的。

有一个开关可以用于翻转灯泡的状态，翻转操作定义如下：

选择当前配置下的任意一个灯泡（下标为 i ）

翻转下标从 i 到 n-1 的每个灯泡

翻转时，如果灯泡的状态为 0 就变为 1，为 1 就变为 0 。

返回达成 target 描述的状态所需的最少翻转次数。

示例 1：
输入：target = "10111"
输出：3
解释：初始配置 "00000".
从第 3 个灯泡（下标为 2）开始翻转 "00000" -> "00111"
从第 1 个灯泡（下标为 0）开始翻转 "00111" -> "11000"
从第 2 个灯泡（下标为 1）开始翻转 "11000" -> "10111"
至少需要翻转 3 次才能达成 target 描述的状态
示例 2：
输入：target = "101"
输出：3
解释："000" -> "111" -> "100" -> "101".
示例 3：
输入：target = "00000"
输出：0
示例 4：
输入：target = "001011101"
输出：5
提示：

1 <= target.length <= 10^5

target[i] == '0' 或者 target[i] == '1'

解题思路#

初始为 flag="0"，遍历 target 中的每一个状态，如果与 flag 不等，结果加 1，并将 flag 更改为这个状态。

如对于测例：

1	`target = "001011101"`

初始 \(\text{ans}=0，s=000000000\)，

\(i=0\)，\(\text{target}=\boxed{0}01011101,s=\boxed{0}00000000\) \(\Rightarrow\) \(\text{target}[0]=s[0]\)，continue
\(i=1\)，\(\text{target}=0\boxed{0}1011101,s=0\boxed{0}0000000\) \(\Rightarrow\) \(\text{target}[1]=s[1]\)，continue
\(i=2\)，\(\text{target}=00\boxed{1}011101,s=00\boxed{0}000000\) \(\Rightarrow\) \(\text{target}[2]\ne s[2]\) \(\Rightarrow\) \(s=001111111,\text{ans}=1\)
\(i=3\)，\(\text{target}=001\boxed{0}11101,s=001\boxed{1}11111\) \(\Rightarrow\) \(\text{target}[3]\ne s[3]\) \(\Rightarrow\) \(s=001000000,\text{ans}=2\)
\(i=4\)，\(\text{target}=0010\boxed{1}1101,s=0010\boxed{0}0000\) \(\Rightarrow\) \(\text{target}[4]\ne s[4]\) \(\Rightarrow\) \(s=001011111,\text{ans}=3\)
\(i=5\)，\(\text{target}=00101\boxed{1}101,s=00101\boxed{1}111\) \(\Rightarrow\) \(\text{target}[5]=s[5]\)，continue
\(i=6\)，\(\text{target}=001011\boxed{1}01,s=001011\boxed{1}11\) \(\Rightarrow\) \(\text{target}[6]=s[6]\)，continue
\(i=7\)，\(\text{target}=0010111\boxed{0}1,s=0010111\boxed{1}1\) \(\Rightarrow\) \(\text{target}[7]\ne s[7]\) \(\Rightarrow\) \(s=001011100,\text{ans}=4\)
\(i=8\)，\(\text{target}=00101110\boxed{1},s=00101110\boxed{0}\) \(\Rightarrow\) \(\text{target}[8]\ne s[8]\) \(\Rightarrow\) \(s=001011101,\text{ans}=5\)

因为每次只与 \(s\) 的当前状态有关，所以只用一个变量表示就行。

class Solution:
    def minFlips(self, target: str) -> int:
        ans, flag = 0, "0"
        for x in target:
            if x != flag:
                flag = x
                ans += 1
        return ans

测试数据

solution = Solution()

target = "10111"
assert solution.minFlips(target) == 3

target = "101"
assert solution.minFlips(target) == 3

target = "00000"
assert solution.minFlips(target) == 0

target = "001011101"
assert solution.minFlips(target) == 5

print("PASS")

1529. 灯泡开关 IV#

问题描述#

解题思路#

1529. 灯泡开关 IV #