将所有人组合在一起的最小交换 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中文网其他相关文章！