将所有人组合在一起的最小交换 II

WBOY
发布: 2024-08-06 02:08:12
原创
392 人浏览过

inimum Swaps to Group All s Together 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中文网其他相关文章!

来源:dev.to
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责声明 Sitemap
PHP中文网:公益在线PHP培训,帮助PHP学习者快速成长!