Leetcode 2914. Minimum Number of Changes to Make Binary String Beautiful
- Leetcode 2914. Minimum Number of Changes to Make Binary String Beautiful
- 1. 解题思路
- 2. 代码实现
- 题目链接：2914. Minimum Number of Changes to Make Binary String Beautiful
1. 解题思路
这一题思路很简单，就是一个贪婪算法。
显然，从头往后考察每一个字符，如果它与前一个字符不相同，那么我们必然只有两个选择：
- 如果前面刚好为偶数个字符，那么直接在此处截断即可；
- 如果前面为奇数个字符，那么必然要将这个字符反转，此时同样可以在此处截断，因为不会影响后续结果。
这么一来，事实上贪婪算法的结果就必然是最小结果，我们直接给出答案即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def minChanges(self, s: str) -> int:
ans = 0
pre, cnt = "", 0
for ch in s:
if ch == pre:
cnt += 1
else:
if cnt % 2 == 0:
pre = ch
cnt = 1
else:
ans += 1
cnt = 0
return ans
提交代码评测得到：耗时72ms，占用内存17.3MB。