2914。讓二進(jìn)位字串變得漂亮的最少更改次數(shù)

難度：中

主題：字串

給你一個 0 索引 長度為偶數(shù)的二進(jìn)位字串 s。

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

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

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

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

範(fàn)例1：

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

範(fàn)例2：

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

範(fàn)例 3：

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

約束：

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

提示：

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

解：

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

以下是逐步解決方法：

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

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

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

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

<?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. 函數(shù)定義： 我們定義一個函數(shù) minChanges，它接受二進(jìn)位字串 s。

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

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

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

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

5. 回傳結(jié)果：最後，我們傳回所需變更的總數(shù)。

複雜：

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

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

聯(lián)絡(luò)連結(jié)

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

如果您想要更多類似的有用內(nèi)容，請隨時關(guān)注我：

• 領(lǐng)英
• GitHub

以上是使二進(jìn)位字串變得漂亮的最少更改次數(shù)的詳細(xì)內(nèi)容。更多資訊請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！