yfcmf做网站,全球互联网十大网站,简易app软件,wordpress做教育网站文章目录1. 题目2. 解题1. 题目
交换 定义为选中一个数组中的两个 互不相同 的位置并交换二者的值。
环形 数组是一个数组#xff0c;可以认为 第一个 元素和 最后一个 元素 相邻 。
给你一个 二进制环形 数组 nums #xff0c;返回在 任意位置 将数组中的所有 1 聚集在一…
文章目录1. 题目2. 解题1. 题目
交换 定义为选中一个数组中的两个 互不相同 的位置并交换二者的值。
环形 数组是一个数组可以认为 第一个 元素和 最后一个 元素 相邻 。
给你一个 二进制环形 数组 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 10^5
nums[i] 为 0 或者 1来源力扣LeetCode 链接https://leetcode-cn.com/problems/minimum-swaps-to-group-all-1s-together-ii 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
class Solution:def minSwaps(self, nums: List[int]) - int:s sum(nums) # 1 的个数if s0:return 0nums nums*2 # 拼接原数组window sum(nums[:s-1]) # 滑窗的和ans len(nums)for r in range(s-1, len(nums)):window nums[r] # 右端点加入ans min(ans, s-window) # 还差几个 1 就要挪动几次window - nums[r-s1] # 左端点出去return ans228 ms 18.8 MB Python3 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
