在0/1

ALGO问题阵列最小化最大continious子阵列

的0/1二进制数组给定
在一个操作我可以翻转阵列的任何数组[索引]即0-> 1或1-> 0 这样的目标是通过使用atmost k以最小化的continious 1或0的最大lenth翻转

例如，如果11111如果阵列且k = 1，最好是使阵列11011
和最小化的值最大连续1或0的值为2

为111110111111且k = 3个ANS是2

我试图蛮力（通过尝试各种位置翻转），但其效率不高

我认为贪婪，但不能弄清楚到底
可以请你帮我的算法中，为O（n）或类似在0/1

来源

2017-03-09 V_K

一个解决方案可以通过读取每个位，以和记录每个连续组1的尺寸到列表A中设计

一旦完成填充，则可以按照由下面的伪代码叙述了算法：

result = N 
for i = 1 to N 
    flips_needed = 0 
    for a in A: 
     flips_needed += <number of flips needed to make sure largest group remaining in a is of size i> 
    if k >= flips_needed: 
     result = flips_needed 
     break 
return result

N是位在整个初始序列的数目。

上述算法通过将1组分成至多为i的大小。每当这样做需要< = k，我们有我们正在寻找的结果，因为我从1开始上升。（即当我们发现flips_needed < = k，我们知道1的组是尽可能小的）

来源

2017-03-10 06:05:37 ilim

回答

相关问题