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 都已经分组在一起。
约束：
提示：
- 请注意，分组在一起的 1 的数量是固定的。它是整个数组中 1 的数量。
- 拨打此号码总计。然后我们应该检查每个总大小的子数组（可能是环绕的），需要多少次交换才能使子数组全部为 1。
- 所需交换的次数是子数组中 0 的数量。
- 为了消除数组的循环特性，我们可以将原始数组追加到其自身上。然后，我们检查每个子数组的总长度。
- 如何避免每次都重新计算子数组中 0 的数量？滑动窗口技术可以提供帮助。
解决方案：
要解决这个问题，我们可以按照以下步骤操作：
-
计算 1 的总数：这将是我们需要组合在一起的 1 的数量。
-
扩展数组：为了处理循环性质，将数组追加到自身。
-
使用滑动窗口技术：在扩展数组上应用滑动窗口技术来找到所需的最小交换次数。
让我们用 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总数的初始窗口中0的数量。
-
滑动窗口：在扩展数组上滑动窗口。对于每个新位置，根据进入和离开窗口的元素更新 0 的计数。
-
查找最小值：跟踪遇到的最小 0 数量，这对应于所需的最小交换次数。
该解决方案通过将圆形数组转换为线性问题来有效地处理它，并使用滑动窗口技术来维持每个大小等于 1 总数的窗口中 0 的运行计数。
联系链接
如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！
如果您想要更多类似的有用内容，请随时关注我：
以上是将所有人组合在一起的最小交换 II的详细内容。更多信息请关注PHP中文网其他相关文章！
