在二进制字符串数学谜题 [英] mathematical puzzle on binary string

问题描述

我一直在给定长度为n的二进制串，我需要找到业务的最低数量来执行这样的字符串不包含超过k个连续相同的字符。

I have been given a binary string of length n and i need to find the minimum numbers of operations to perform such that string does not contain more than k consecutive equal characters.

样的操作，只有我才能执行的翻转绳子的第i个字符。翻转一个字符意味着改变一个'1'到'0'或'0'变为'1'。

Only kind of operation I am allowed to perform is to flip any ith character of the string. flipping a character means changing a '1' to '0' or a '0' to '1'.

例如：

如果n = 4，K = 1，并串= 1001

if n = 4 , k = 1 and string = 1001

，然后回答：

字符串= 1010和最低运营= 2

string = 1010 and minimum operations = 2

我还需要找到新的字符串。

I need to also find the new string.

谁能告诉我一个高效的算法求解问题的考虑N'LT = 10 ^ 5

can anyone tell me an efficient algorithm for solving problem considering n <=10^5

推荐答案

还有一个方法：

if k>1:
    if k+1 matching characters are found:
        if a[k+1]==a[k+2]:
            flip a[k+1]
        else if a[k+1]!=a[k+2]:
            flip a[k]

对于k = 1，你可以做到这一点！ 在这里，翻转装置，从1到0，反之亦然

for k=1 you can do it! Here flipping means from 1 to 0 and vice-versa

这篇关于在二进制字符串数学谜题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！