來自HackerEarth的以下邏輯或算法是什麼？

-1

黑客喜歡點東西，亞歷克斯也喜歡。亞歷克斯剛剛開始他的職業生涯，作爲黑客，發現了一個特殊的二進制數組一個 A（含小號和小號）。來自HackerEarth的以下邏輯或算法是什麼？

在一個操作中，他可以選擇數組中的任何兩個位置，並且可以交換它們的值。他必須執行恰好一個操作並且最大化僅包含 s 的子陣列的長度。

如亞歷克斯是在他的領域是新手，幫助他對於相同的，並且輸出僅包含1 小號 1S 子陣列的所需長度。

輸入格式：

第一行由一個整數 N中的，表示所述陣列中元件的數量。

第二行由N個空格分隔的整數組成，表示數組的元素。

輸出格式：

打印僅含小號 1S子陣列的所需長度。

輸入約束：

1 ≤ N ≤ 100 
1 ≤ N ≤ 1000 ≤ A[i] ≤ 1

輸入：

5 
1 1 1 0 1

輸出：

來源

2017-06-19 Arvind Ramadurai

它有點令人困惑，它首先提到了二進制字符串，然後給出了一個非二進制字符串的例子，但邏輯應該是相同的。嘗試找到最長的字符串，但請記住，只要字符串中有另一個1來代替它，就可以忽略單個非1值。 –

請您詳細說明一下嗎？非二進制的東西是我猜的錯字。我改變了它。 –

一般算法：

有一個變量，inSub，用於跟蹤的子串你正在看。它的值首先是-1，表示你沒有看到特定的子字符串atm。

遍歷字符串，直到找到1爲止。此1的索引將是inSub的新值。

也有一個變量hitZero（初始化爲False），它跟蹤當前子字符串是否遇到零。這是因爲一個零可以被一個零代替，假設整個列表中有另一個零。如果命中零並且hitZero爲False，則會變爲True。如果hitZero已爲True，則需要將子字符串的長度存儲在列表SubList中，inSub將設置爲-1，並且hitZero將再次爲False。

在這個結尾你將有一個子串長度列表。如果列表中有多個子字符串，答案將是最長的子字符串（因爲您可以從其他子字符串中取一個）。如果只有一個子字符串，則答案將是子字符串中最長的1個連續字符串。（已編輯）

來源

2017-06-19 14:51:54

是的，我明白了。但你是怎麼想到的呢？我只需要知道你的思維過程。我的意思是你是怎麼想出這個算法的。我只是一個平庸的人。非常感謝你btw。 :)如果輸入是1 1 1 0 1 1 1 0 0 1 –

我不知道如何正確解釋我的整個過程，它就像計算一個1的字符串，除了你必須考慮到能夠交換兩個數字。有很多方法可以編寫這個算法，這只是我腦子想出的一個方法。通過這個輸入，它會出現兩個子字符串，一個長度爲7，一個爲1.由於有多個子字符串，所以第一個字符的零可以替換，所以答案是7. –

請檢查編輯處底部：我意識到在像11011這樣的情況下，我的虛擬程序將返回4而不是2. –

讓我來解釋一下你可以用什麼思路來解決這個問題。

每當你看到一個問題時，試着想出一些測試用例。

對於這個特定的問題，下面提到的任何測試用例都可能是一個很好的起點。

Example 1:- 

Input: 
1 1 1 1 0 0 0 

Output 
4

在上述示例中，可以清楚地看到，沒有交換可能因此輸出將是4。

Example 2:- 

Input 
1 1 1 1 1 1 

Output 
6

在上述例子中也沒有交換是可能的，因爲有沒有由0分隔的子字符串，所以你的答案基本上等於整個字符串的長度。

Example 3:- 

Input 
1 1 1 0 0 0 1 1 1 1 

Output 
5

在上面的例子中，你可以看到一個一個交換從零目前其他琴絃附近的一個第一毗鄰的串會給你，你的回答。

所以現在你有三個很好的例子，涵蓋了大部分的角落案例。

看看下面的評論和以上的算法，以獲得如何解決這個問題的好看法。

感謝卡爾審查我的算法。

希望這會有所幫助！

來源

2017-06-19 16:48:20 zenwraight

像11101110001這樣的情況呢？ –

@CarlShiles好趕上....雅錯過了那個角落的情況下... – zenwraight

來自HackerEarth的以下邏輯或算法是什麼？

回答

相關問題