使二进制字符串变得漂亮的最少更改次数

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中文网其他相关文章！