leetcode 2134.最少交换次数来组合所有的1 Ⅱ

2024-08-25 18:20

本文主要是介绍leetcode 2134.最少交换次数来组合所有的1 Ⅱ,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

题目描述

示例1:

示例2:

示例3:

提示:

解题思路

滑动窗口法

概念

应用场景及特点:

思路

代码

复杂度分析

优化解法

代码实现

Python语言:

C语言:

Go语言:

优化后的代码解释

优化后的复杂度分析


题目描述

交换定义为选中一个数组中的两个互不相同的位置并交换二者的值。
环形数组是一个数组,可以认为第一个元素和最后一个元素相邻
给你一个二进制环形数组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 次(利用数组的环形特性)。
无法在交换 0 次的情况下将数组中的所有 1 聚集在一起。
因此,需要的最少交换次数为 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 次。
无法在交换 0 次或 1 次的情况下将数组中的所有 1 聚集在一起。
因此,需要的最少交换次数为 2 。

示例3:

输入:nums = [1,1,0,0,1]
输出:0
解释:得益于数组的环形特性,所有的 1 已经聚集在一起。
因此,需要的最少交换次数为 0 。

提示:

  • 1 <= nums.length <= 105
  • nums[i] 为 0 或者 1

解题思路

滑动窗口法

概念

滑动窗口是一个在序列上移动的区间,通常由左右两个指针来界定这个区间的范围。通过移动指针来改变窗口的大小和位置,在窗口移动的过程中,根据问题的需求进行特定的计算和处理。

应用场景及特点

  1. 子数组 / 子串问题
  • 当需要在一个序列中找到满足特定条件的连续子数组或子串时,滑动窗口非常适用。例如,寻找和为特定值的连续子数组、含有特定字符的最长子串等。
  • 窗口的大小通常是动态变化的,根据问题的条件进行调整。
  1. 高效性
  • 相比于暴力枚举所有可能的子数组 / 子串,滑动窗口法通常能够在更短的时间内找到解。因为它利用了子数组 / 子串的连续性和窗口的滑动特性,避免了重复计算。
  1. 指针移动规则
  • 通常有两个指针,一个指向窗口的左端,一个指向窗口的右端。根据问题的具体要求,以特定的方式移动指针。
  • 例如,在寻找满足特定条件的最小子数组时,可能会先扩大窗口直到满足条件,然后再缩小窗口以找到最小的满足条件的窗口。

思路

  1. 统计 1 的总数
  • 首先计算数组 nums 中的 1 的总数,记为 k。因为我们需要把这些 1 聚集在一起,所以我们需要在数组中找到包含 k 个元素的连续子数组,使得该子数组中的 0 的数量最少。
  1. 扩展环形数组
  • 由于数组是环形的,我们可以将数组扩展一倍,即将数组 nums 复制一遍并连接到原数组后面,得到新的数组 nums_ext。这使得我们可以在新的数组中处理环形问题就像处理线性问题一样。
  1. 滑动窗口
  • 使用一个长度为 k 的滑动窗口,在 nums_ext 上滑动,统计每个窗口内的 0 的数量。
  • 记录所有窗口中 0 的最小数量,即为将 1 聚集在一起所需的最少交换次数。
  1. 输出结果
  • 计算结果为 0 的最小值,即为我们需要的最少交换次数。

代码

class Solution:def minSwaps(self, nums: List[int]) -> int:# 步骤1:统计1的总数k = sum(nums)n = len(nums)if k == 0 or k == n:return 0# 步骤2:扩展环形数组nums_ext = nums + nums# 步骤3:滑动窗口min_swaps = float('inf')current_zeros = 0# 初始化第一个窗口for i in range(k):if nums_ext[i] == 0:current_zeros += 1min_swaps = current_zeros# 滑动窗口遍历剩余部分for i in range(1, n):if nums_ext[i-1] == 0:current_zeros -= 1if nums_ext[i+k-1] == 0:current_zeros += 1min_swaps = min(min_swaps, current_zeros)return min_swaps

复杂度分析

  • 时间复杂度:O(n),因为我们需要遍历数组 nums_ext
  • 空间复杂度:O(n),因为我们构建了一个双倍长度的数组 nums_ext

优化解法

  • 计算 1 的总数:首先统计数组中 1 的数量 k,我们仍然需要这个值来确定滑动窗口的大小。
  • 滑动窗口:直接在原数组 nums 上进行滑动窗口操作。由于数组是环形的,当滑动窗口超出数组长度时,可以使用取模操作来访问数组中的元素。
  • 跟踪最小的 0 的数量:跟踪窗口中 0 的最小数量,这将对应最少的交换次数。

代码实现

Python语言:

class Solution:def minSwaps(self, nums: List[int]) -> int:k = sum(nums)  # 计算1的总数n = len(nums)if k == 0 or k == n:return 0# 初始窗口内的0的数量current_zeros = sum(1 for i in range(k) if nums[i] == 0)min_swaps = current_zeros# 滑动窗口遍历数组,利用环形特性for i in range(1, n):# 移出窗口的元素if nums[i - 1] == 0:current_zeros -= 1# 加入窗口的元素if nums[(i + k - 1) % n] == 0:current_zeros += 1# 更新最小交换次数min_swaps = min(min_swaps, current_zeros)return min_swaps

C语言:

#include <stdio.h>int minSwaps(int nums[], int n) {int k = 0;for (int i = 0; i < n; i++) {k += nums[i];}if (k == 0 || k == n) {return 0;}int current_zeros = 0;for (int i = 0; i < k; i++) {if (nums[i] == 0) {current_zeros++;}}int min_swaps = current_zeros;for (int i = 1; i < n; i++) {if (nums[i - 1] == 0) {current_zeros--;}if (nums[(i + k - 1) % n] == 0) {current_zeros++;}if (current_zeros < min_swaps) {min_swaps = current_zeros;}}return min_swaps;
}int main() {int nums[] = {1, 0, 1, 0, 1, 0, 0, 1};int n = sizeof(nums) / sizeof(nums[0]);int result = minSwaps(nums, n);printf("Minimum swaps required: %d\n", result);return 0;
}

Go语言:

package mainimport ("fmt"
)func minSwaps(nums []int) int {k := 0n := len(nums)for _, num := range nums {k += num}if k == 0 || k == n {return 0}currentZeros := 0for i := 0; i < k; i++ {if nums[i] == 0 {currentZeros++}}minSwaps := currentZerosfor i := 1; i < n; i++ {if nums[i-1] == 0 {currentZeros--}if nums[(i+k-1)%n] == 0 {currentZeros++}if currentZeros < minSwaps {minSwaps = currentZeros}}return minSwaps
}func main() {nums := []int{1, 0, 1, 0, 1, 0, 0, 1}result := minSwaps(nums)fmt.Println("Minimum swaps required:", result)
}

优化后的代码解释

  • 滑动窗口:在原数组上直接滑动窗口,而不需要构造扩展数组。
  • 环形数组的处理:使用 (i + k - 1) % n 的取模运算来访问数组的后续元素,这样可以有效处理数组的环形特性。

优化后的复杂度分析

  • 时间复杂度:O(n),我们只需遍历数组一次。
  • 空间复杂度:O(1),因为没有使用额外的空间。

这篇关于leetcode 2134.最少交换次数来组合所有的1 Ⅱ的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1106306

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

hdu4869(逆元+求组合数)

//输入n,m,n表示翻牌的次数,m表示牌的数目,求经过n次操作后共有几种状态#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#includ

hdu 3065 AC自动机 匹配串编号以及出现次数

题意: 仍旧是天朝语题。 Input 第一行,一个整数N(1<=N<=1000),表示病毒特征码的个数。 接下来N行,每行表示一个病毒特征码,特征码字符串长度在1—50之间,并且只包含“英文大写字符”。任意两个病毒特征码,不会完全相同。 在这之后一行,表示“万恶之源”网站源码,源码字符串长度在2000000之内。字符串中字符都是ASCII码可见字符(不包括回车)。

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

【JavaScript】LeetCode:16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i,右指针j,从头遍历数组,若j指针指向的元素不在set中,则加入该元素,否则更新结果res,删除集合中i指针指向的元素,进入下一轮循环。 /*** @param