1529. Minimum Suffix Flips

题目信息

题号:

1529

难度:

Medium

主题:

二进制字符串、贪心、后缀翻转

原题:

LeetCode 1529

重点:

初始字符串全为 0;一次操作选择下标并翻转该位置到末尾的全部位,求得到目标串的最少次数

题目重述

给定二进制目标字符串 target。初始有一个与它等长且全部为 0 的字符串。

一次操作选择任意下标 i,把从 i 到末尾的每个字符同时翻转,即 0 变 1、1 变 0。请返回变成 target 所需的最少操作次数。

1 <= target.length <= 10^5,target 只包含 0 和 1。

自建示例

每次目标位发生变化都需要新的后缀翻转:

输入:target = "101"
输出:3
解释:000 -> 111 -> 100 -> 101,共三次操作。

目标全为零时无需操作:

输入:target = "000"
输出:0
解释:初始字符串已经等于目标。