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. 對于任何有效的分區(qū)，由于每個部分都由偶數個相同的字符組成，因此我們可以進一步將每個部分劃分為恰好為 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. 迭代字符串：我們循環(huán)遍歷字符串，每次遞增 2 以檢查每個兩個字符的塊：

   • $first 是當前位置的字符。
   • $second 是下一個位置的字符。

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

5. 返回結果：最后，我們返回所需更改的總數。

復雜：

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

此解決方案的運行時間復雜度為 O(n)，其中 n 是字符串的長度，使其對于給定的約束非常有效。

聯系鏈接

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

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

• 領英
• GitHub

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