README.md

comments	difficulty	edit_url	rating	source	tags
true	中等	https://github.com/doocs/leetcode/edit/main/solution/3200-3299/3228.Maximum%20Number%20of%20Operations%20to%20Move%20Ones%20to%20the%20End/README.md	1593	第 407 场周赛 Q3	贪心 字符串 计数

3228. 将 1 移动到末尾的最大操作次数

English Version

题目描述

给你一个 二进制字符串 s。

你可以对这个字符串执行 任意次 下述操作：

• 选择字符串中的任一下标 i（ i + 1 < s.length ），该下标满足 s[i] == '1' 且 s[i + 1] == '0'。
• 将字符 s[i] 向 右移 直到它到达字符串的末端或另一个 '1'。例如，对于 s = "010010"，如果我们选择 i = 1，结果字符串将会是 s = "000110"。

返回你能执行的 最大 操作次数。

 

示例 1：

输入： s = "1001101"

输出： 4

解释：

可以执行以下操作：

• 选择下标 i = 0。结果字符串为 s = "0011101"。
• 选择下标 i = 4。结果字符串为 s = "0011011"。
• 选择下标 i = 3。结果字符串为 s = "0010111"。
• 选择下标 i = 2。结果字符串为 s = "0001111"。

示例 2：

输入： s = "00111"

输出： 0

 

提示：

• 1 <= s.length <= 105
• s[i] 为 '0' 或 '1'。

解法

方法一：贪心

我们用一个变量 $\textit{ans}$ 记录答案，用一个变量 $\textit{cnt}$ 记录当前的 $1$ 的个数。

然后我们遍历字符串 $s$，如果当前字符是 $1$，则 $\textit{cnt}$ 加一，否则如果存在前一个字符，且前一个字符是 $1$，那么前面的 $\textit{cnt}$ 个 $1$ 可以往后移动，答案加上 $\textit{cnt}$。

最后返回答案即可。

时间复杂度 $O(n)$，其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $O(1)$。

Python3

class Solution:
    def maxOperations(self, s: str) -> int:
        ans = cnt = 0
        for i, c in enumerate(s):
            if c == "1":
                cnt += 1
            elif i and s[i - 1] == "1":
                ans += cnt
        return ans

Java

class Solution {
    public int maxOperations(String s) {
        int ans = 0, cnt = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            if (s.charAt(i) == '1') {
                ++cnt;
            } else if (i > 0 && s.charAt(i - 1) == '1') {
                ans += cnt;
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int maxOperations(string s) {
        int ans = 0, cnt = 0;
        int n = s.size();
        for (int i = 0; i < n; ++i) {
            if (s[i] == '1') {
                ++cnt;
            } else if (i && s[i - 1] == '1') {
                ans += cnt;
            }
        }
        return ans;
    }
};

Go

func maxOperations(s string) (ans int) {
	cnt := 0
	for i, c := range s {
		if c == '1' {
			cnt++
		} else if i > 0 && s[i-1] == '1' {
			ans += cnt
		}
	}
	return
}

TypeScript

function maxOperations(s: string): number {
    let [ans, cnt] = [0, 0];
    const n = s.length;
    for (let i = 0; i < n; ++i) {
        if (s[i] === '1') {
            ++cnt;
        } else if (i && s[i - 1] === '1') {
            ans += cnt;
        }
    }
    return ans;
}