將所有人組合在一起的最小交換 II

2134。將所有 1 組合在一起的最小交換 II

中

交換 被定義為在陣列中取得兩個不同的 位置並交換其中的值。

圓形數組被定義為一個數組，其中我們認為第一個元素和最後一個元素相鄰。

給定一個二進位循環陣列nums，傳回將陣列中存在的所有1在任何位置分組在一起所需的最小交換次數。

範例1：

• 輸入： nums = [0,1,0,1,1,0,0]
• 輸出： 1
• 解釋： 以下是將所有 1 分組在一起的幾種方法：
  • [0,0,1,1,1,0,0] 使用 1 次交換。
  • [0,1,1,1,0,0,0] 使用 1 次交換。
  • [1,1,0,0,0,0,1] 使用 2 次交換（使用陣列的循環屬性）。
  • 無法將所有 1 和 0 交換分組在一起。
  • 因此，所需的最小交換次數為 1。

範例2：

• 輸入： nums = [0,1,1,1,0,0,1,1,0]
• 輸出： 2
• 解釋： 以下是將所有 1 分組在一起的幾種方法：
  • [1,1,1,0,0,0,0,1,1] 使用 2 次交換（使用陣列的循環屬性）。
  • [1,1,1,1,1,0,0,0,0] 使用 2 次交換。
  • 無法將所有 1 與 0 或 1 個交換分組在一起。
  • 因此，所需的最小交換次數為 2。

範例 3：

• 輸入： nums = [1,1,0,0,1]
• 輸出： 0
• 解釋： 由於陣列的循環特性，所有 1 都已經分組在一起。
  • 因此，所需的最小交換次數為 0。

約束：

• 1 5
• nums[i] 為 0 或 1。

提示：

1. 請注意，分組在一起的 1 的數量是固定的。它是整個數組中 1 的數量。
2. 撥打此號碼總計。然後我們應該檢查每個總大小的子數組（可能是環繞的），需要多少次交換才能使子數組全部為 1。
3. 所需交換的次數是子數組中 0 的數量。
4. 為了消除陣列的循環特性，我們可以將原始陣列追加到其自身上。然後，我們檢查每個子數組的總長度。
5. 如何避免每次都重新計算子數組中 0 的數量？滑動視窗技術可以提供幫助。

解：

要解決這個問題，我們可以按照以下步驟操作：

1. 計算 1 的總數：這將是我們需要組合在一起的 1 的數量。
2. 擴充數組：為了處理循環性質，將陣列追加到自身。
3. 使用滑動視窗技術：在擴充數組上應用滑動視窗技術來找出所需的最小交換次數。

讓我們用 PHP 實作這個解：2134。將所有 1 組合在一起的最小交換次數 II

<?php // Example usage
$nums1 = [0,1,0,1,1,0,0];
$nums2 = [0,1,1,1,0,0,1,1,0];
$nums3 = [1,1,0,0,1];

echo minSwaps($nums1) . "\n"; // Output: 1
echo minSwaps($nums2) . "\n"; // Output: 2
echo minSwaps($nums3) . "\n"; // Output: 0

?>

解釋：

1. 統計1的總數：計算原數組中1的總數
2. 擴充數組：將原始數組與其自身連接起來以處理循環性質。
3. 初始視窗：統計大小等於1總數的初始視窗中0的數量。
4. 滑動視窗：在擴充數組上滑動視窗。對於每個新位置，根據進入和離開視窗的元素更新 0 的計數。
5. 找出最小值：追蹤遇到的最小 0 數量，這對應於所需的最小交換次數。

此解決方案透過將圓形陣列轉換為線性問題來有效地處理它，並使用滑動視窗技術來維持每個大小等於 1 總數的視窗中 0 的運行計數。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是將所有人組合在一起的最小交換 II的詳細內容。更多資訊請關注PHP中文網其他相關文章！