最少交换次数组合所有的 1 II – 解题思路代码分析

题目描述

本题目要求我们找到一个环形二进制数组中,通过最少的交换次数把所有的 1 聚集在一起的方法。数组的环形特性意味着第一个元素最后一个元素相邻的。我们需要考虑数组的这种特殊结构找到最优解。

示例分析

解题思路

解决这个问题核心思想是使用滑动窗口技术。首先统计数组中 1 的数量,这将决定我们滑动窗口大小然后我们遍历个数两次考虑环形结构),统计窗口内 0 的数量,这个数量就是需要交换的次数。我们寻找最小这个交换次数作为答案

答案代码分析

class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        n = len(nums)
        win_size = nums.count(1)
        if win_size == 0:
            return 0

        round_cnt = 0
        first_win_ridx = win_size - 1
        ans = 10 ** 5  # 初始化一个大数作为初始答案
        left = right = 0
        win_zero_num = 0
        win_ele_num = 1

        while round_cnt < 2:
            if nums[right] == 0:
                win_zero_num += 1

            if win_ele_num == win_size:
                ans = min(ans, win_zero_num)
                if nums[left] == 0:
                    win_zero_num -= 1
                left += 1
                left %= n  # 考虑环形数组特性
                win_ele_num -= 1

            right += 1
            right %= n  # 考虑环形数组特性
            if right == first_win_ridx:
                round_cnt += 1

            win_ele_num += 1
        return ans

原文地址:https://blog.csdn.net/weixin_73108148/article/details/134768952

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_36222.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注