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

题目描述

定义若一个字符串的每个字符均为’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
    输入: 
    s="10101"
    k=2
    输出:
    2
    解释:
    1. 修改 [1,2] ==> "11001"
    2. 修改 [2,3] ==> "11111"
  • 示例 2:

    1
    2
    3
    4
    5
    6
    7
    8
    输入: 
    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
文章作者: Spaceack
文章链接: http://spaceack.com/2020/09/05/2020-09-05-%E8%B6%85%E7%BA%A7%E7%A0%81%E5%8A%9B%E5%9C%A8%E7%BA%BF%E7%BC%96%E7%A8%8B%E5%A4%A7%E8%B5%9B%E5%88%9D%E8%B5%9B%E7%AC%AC3%E5%9C%BA-%E5%AE%8C%E7%BE%8E%E5%AD%97%E7%AC%A6%E4%B8%B2/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 丸子家的小云吞
支付宝打赏
微信打赏