超级码力初赛第三场完美字符串

Spaceack 收录于算法

2020-09-05 约 443 字预计阅读 1 分钟

题目描述

定义若一个字符串的每个字符均为'1'，则该字符串称为完美字符串。给定一个只由'0’和'1’组成的字符串s和一个整数k。你可以对字符串进行任意次以下操作

选择字符串的一个区间长度不超过k的区间[l, r]，将区间内的所有'0’修改成'1'，将区间内所有的'1’修改成'0'。

你最少需要多少次操作，可以将字符串s修改成一个完美字符串

1<=len(s)<=100,000 1<=k<=100,000

示例

示例 1:

1
2
3
4
5
6
7
8
9


输入: 
s="10101"
k=2
输出: 
2
解释: 
1. 修改 [1,2] ==> "11001"
2. 修改 [2,3] ==> "11111"

示例 2:

1
2
3
4
5
6
7
8
9


输入: 
s="00000"
k=3
输出: 
2
解释:
1. 修改 [0,2] ==> "11100"
2. 修改 [3,4] ==> "11111"

来源：九章算法

解题思路

简单的模拟，要注意边界条件，一次通过。

题解1:

执行用时：402

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


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

目录

超级码力初赛第三场 完美字符串

题目描述

示例

超级码力初赛第三场完美字符串