在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

回答

相關問題