使二進位字串變得漂亮的最少更改次數

2914。讓二進位字串變得漂亮的最少更改次數

難度：中

主題：字串

給你一個 0 索引 長度為偶數的二進位字串 s。

如果可以將字串分成一個或多個子字串，例如：，那麼它就是美麗的

• 每個子字串都有一個偶數長度。
• 每個子字串包含僅 1 或僅0。

您可以將 s 中的任意字元變更為 0 或 1。

回傳使字串漂亮所需的最小更改次數。

範例1：

• 輸入： s = "1001"
• 輸出： 2
• 解釋： 我們將 s[1] 改為 1，將 s[3] 改為 0，得到字串「1100」。
  • 可以看出字串「1100」很漂亮，因為我們可以將它分割成「11|00」。
  • 可以證明2是使字串變得漂亮所需的最少改變次數。

範例2：

• 輸入： s = "10"
• 輸出： 1
• 解釋： 我們將 s[1] 改為 1 以取得字串「11」。
  • 可以看出字串「11」很漂亮，因為我們可以將它分割成「11」。
  • 可以證明1是讓字串變得漂亮所需的最少改變次數。

範例 3：

• 輸入： s = "0000"
• 輸出： 0
• 說明：我們不需要做任何更改，因為字串「0000」已經很漂亮了。

約束：

• 2 5
• s 的長度為偶數。
• s[i] 為“0”或“1”。

提示：

1. 對於任何有效的分區，由於每個部分都由偶數個相同的字元組成，因此我們可以進一步將每個部分劃分為正好為 2 的長度。
2. 注意到第一個提示後，我們可以將整個字串分解為大小為 2 的不相交區塊，並找到使這些區塊變得漂亮所需的最少更改數量。

解：

我們需要確保二進位字串 s 中的每一對字元要么是“00”，要么是“11”。如果一對不屬於這兩種模式之一，我們將需要更改其中一個字元以使其匹配。

以下是逐步解決方法：

1. 將字串分成區塊：由於長度為 2 的區塊可以形成漂亮的字串，因此我們可以以 2 為步長迭代該字串。

2. 計數變化：對於每個 2 個字元的區塊，我們需要確定多數字元（0 或 1）。我們將更改區塊中的少數字元以匹配多數字元。

3. 計算最小更改：對於每個區塊，如果兩個字元不同，我們將需要 1 次更改；如果相同，則無需更改。

讓我們用 PHP 實作這個解：2914。讓二進位字串變得漂亮的最少更改次數

<?php
/**
 * @param String $s
 * @return Integer
 */
function minChanges($s) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage
echo minChanges("1001"); // Output: 2
echo minChanges("10");   // Output: 1
echo minChanges("0000"); // Output: 0
?>

解釋：

1. 函數定義： 我們定義一個函數 minChanges，它接受二進位字串 s。

2. 初始化：我們初始化變數 $changes 來追蹤所需的變更數量。

3. 迭代字串：我們循環遍歷字串，每次遞增 2 以檢查每個兩個字元的區塊：

   • $first 是目前位置的字元。
   • $second 是下一個位置的字元。

4. 檢查變更：如果目前區塊中的字元不同，我們將 $changes 計數器增加 1。

5. 回傳結果：最後，我們傳回所需變更的總數。

複雜：

• 時間複雜度：O(n)，其中n是字串的長度，就像我們一樣迭代字串一次。
• 空間複雜度：O(1)，因為我們使用恆定數量的額外空間。

此解的運行時間複雜度為 O(n)，其中 n 是字串的長度，使其對於給定的限制非常有效。

聯絡連結

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

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

• 領英
• GitHub

以上是使二進位字串變得漂亮的最少更改次數的詳細內容。更多資訊請關注PHP中文網其他相關文章！