我正在查看 LeetCode 問題2134。將所有 1 組合在一起的最小交換數 II：
交換被定義為在陣列中占據兩個不同的位置并交換其中的值。
回圈陣列被定義為我們認為第一個元素和最后一個元素相鄰的陣列。
給定一個二進制回圈陣列
nums，回傳將陣列中的所有元素組合到任意位置所需的最小交換次數。1
我正在嘗試研究其他人如何提出自己的解決方案。我遇到了這個特定的，但我不明白其中的邏輯：
class Solution {
public int minSwaps(int[] nums) {
// number of ones
int cntones=Arrays.stream(nums).sum();
// worst case answer
int rslt=nums.length;
// position lft and figure better value for min/rslt
int holes = 0;
for(int i=0;i<cntones;i ) {
if(nums[i]==0)
holes ;
}
// better value for rslt from lft to rgt
// up to index of cntones.
rslt = Math.min(rslt, holes);
// they have a test case with one element
// and that trips up if you dont do modulo
int rgt=cntones % nums.length;
for(int lft=0;lft<nums.length;lft ) {
rslt=Math.min(rslt,holes);
if(nums[lft]!=nums[rgt])
if(nums[rgt]==1)
holes--;
else
holes ;
rgt=(rgt 1)%nums.length;
}
return rslt;
}
}
為什么最壞的情況是輸入陣列的長度？我在想等等，最壞的情況不是像 [0,1,0,1,0,1...] 那樣 0 和 1 交替出現嗎？能給我舉個例子？
我想在某些情況下，#of 孔可能是一種可能的解決方案，從視窗的固定長度（總 1 的數量）中計算 0，但因為我不了解最壞的情況，
rslt從問題 #1 開始，下面的行樹樁我也是。// better value for rslt from lft to rgt // up to index of cntones. rslt = Math.min(rslt, holes);關于下面的模數，我認為
cntones永遠不會大于nums.length，而這會一直導致 0？我正在考慮一個元素的情況，您必須檢查一個元素是 0 還是 1。下面的行如何覆寫該邊緣情況？// they have a test case with one element // and that trips up if you dont do modulo int rgt=cntones % nums.length;由于#1~#3，最后一個 for 回圈對我來說毫無意義......
uj5u.com熱心網友回復：
為什么最壞的情況是輸入陣列的長度？
首先請注意，交換僅在將 0 與 1 交換時才有用。其次，第二次交換相同的數字是沒有意義的，因為這種雙重交換的結果可以通過單次交換來實作。所以我們可以說交換次數的上限是 0 位數或 1 位數（以最少的為準）。事實上，這是一個高估，因為至少有一個 1 位數應該能夠保持不動。但是，讓我們暫時忽略它。為了達到最壞的情況，應該有 1 和 0 一樣多的數字，所以我們的長度是最壞情況的一半。當然，通過使用大于該值的值（如長度）進行初始化，我們沒有害處。
交替數字的例子可以通過保持這些 1 位的一半不移動，并在它們之間的孔中移動剩余的 1 位來解決。所以這意味著我們有很多交換，大約等于陣列長度的四分之一。
下面的線也難倒我。
rslt = Math.min(rslt, holes);
正如你所說，有一個視窗在圓形陣列上移動，這代表了所有 1 位應該結束的最終情況。因此，它設定了要努力的目標。顯然，不需要交換已經在該視窗內的 1 位數字。該視窗內的每個 0 位都必須與當前位于該視窗外的 1 位進行交換。這樣做會到達目標，因此到達特定目標視窗的交換次數等于該視窗內的孔數（0 位）。
由于對每個可能的視窗都進行了該練習，因此我們有興趣找到視窗的最佳位置，即孔（交換）數量最小的位置。這就是這行代碼正在做的事情。rslt是“到目前為止”的最小值，holes是我們當前視窗的新值。如果那是更少，那么rslt應該更新到它。這就是本宣告中發生的情況。
關于下面的模數，我認為
cntones永遠不會大于nums.length，而這會一直導致 0？我正在考慮一個元素的情況，您必須檢查一個元素是 0 還是 1。下面的行如何覆寫該邊緣情況？int rgt=cntones % nums.length;
該模僅適用于cntones等于的情況。你是對的，它永遠不會超過它。但是它相等的情況是可能的（當輸入只有1位時）。并且將用作索引，它不應該等于陣列中未定義的插槽。nums.lengthrgtnums.length
由于#1~#3，最后一個 for 回圈對我來說毫無意義......
從上面的細節應該很清楚了。該回圈一次移動一個視窗，并保持變數holes增量更新。當然，我們本可以決定從頭開始計算每個視窗的孔數，但這會浪費時間。當我們從一個視窗移動到下一個視窗時，我們只在左邊失去一個數字，在右邊增加一個數字，所以我們可以用這些資訊更新并知道當前視窗holes中有多少洞——開始的那個在并運行（回圈）到。如果我們在左邊失去的數字與我們在右邊獲得的數字相同，我們顯然沒有改變洞的數量。在它們不同的地方，與前一個視窗相比，我們要么贏要么輸一個洞。lftrgt
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/489529.html
下一篇：在C 中使用堆疊洗掉相等的數字