定义若一个字符串的每个字符均为’1’,则该字符串称为完美字符串。给定一个只由’0’和’1’组成的字符串s和一个整数k。你可以对字符串进行任意次以下操作
选择字符串的一个区间长度不超过k的区间[l, r],将区间内的所有’0’修改成’1’,将区间内所有的’1’修改成’0’。
你最少需要多少次操作,可以将字符串s修改成一个完美字符串
1<=len(s)<=100,000 1<=k<=100,000
示例 1:
输入:
s="10101"
k=2
输出:
2
解释:
1. 修改 [1,2] ==> "11001"
2. 修改 [2,3] ==> "11111"
示例 2:
输入:
s="00000"
k=3
输出:
2
解释:
1. 修改 [0,2] ==> "11100"
2. 修改 [3,4] ==> "11111"
来源:九章算法
解题思路
简单的模拟,要注意边界条件,一次通过。
题解1:
执行用时:402
class Solution:
"""
@param s: string need to be transformed
@param k: minimum char can be transformed in one operation
@return: minimum times of transforming all char into '1'
"""
def perfectString(self, s, k):
# Write your code here.
result = 0
s_len = len(s)
s_list = list(s)
for index, s in enumerate(s_list):
if s == 1:
continue
if s == '0':
start_at = index
end_at = index
if end_at+1 <= s_len:
while s_list[end_at] == '0' and end_at - start_at < k:
end_at = end_at + 1
if end_at > s_len -1:
break
for x in range(start_at, end_at):
s_list[x] = '1'
result = result + 1
return result