没有新消息
更多内容
0 条评论
暂无评论,快来写下您的评论
问题来自于
福大大
#福大大架构师每日一题#2023-09-30:用go语言,给你一个整数数组 nums 和一个整数 k 。 nums 仅包含
2023-09-30:用go语言,给你一个整数数组 nums 和一个整数 k 。 nums 仅包含 0 和 1, 每一次移动,你可以选择 相邻 两个数字并将它们交换。 请你返回使 nums 中包含 k 个 连续 1 的 最少 交换次数。 输入:nums = [1,0,0,1,0,1], k = 2。 输出:1。
2283
阅读
10
回答
@2024 职Q 智联招聘
合作商务邮箱:sbyh@zhaopin.com.cn
友情链接
HR圈内招聘/ 同道问答/ 人资知识社区
51社保/ X职场/ HR Bar/ 中人网/ 研招网
京ICP备17067871号 合字B2-20210134
京公网安备 11010502030147号
人力资源许可证:1101052003273号
网上有害信息举报专区
违法不良信息举报电话:400-885-9898
关爱未成年举报热线:400-885-9898-7
朝阳区人力资源与社会保障局 监督电话: 57596212,65090445
#福大大架构师每日一题#2023-09-30:用go语言,给你一个整数数组 nums 和一个整数 k 。 nums 仅包含
这道题目可以通过滑动窗口和前缀和的方法来解决。 首先,我们计算出数组 nums 中 1 的个数,以及 0 的个数。然后,我们可以使用滑动窗口来找出所有长度为 k 的子数组中 1 的个数。对于每个子数组,我们记录下 1 的个数与该子数组的起始位置,并将这些信息存储在哈希表中。 接下来,我们遍历数组 nums,使用前缀和的方法来计算出每个位置左侧 1 的个数。对于每个位置,我们可以在哈希表中查找距离该位置最近的右侧 1 的位置,并计算两个位置之间的距离。这个距离就是需要交换的最少次数,因为我们可以将当前位置左侧的 1 和右侧的 1 进行交换。 下面是 Go 语言的实现: ```go func minSwaps(nums []int, k int) int { ones := make([]int, len(nums)) for i, num := range nums { if num == 1 { ones[i] = ones[i-1] + 1 } } prefixSum := make([]int, len(nums)+1) for i := 1; i <= len(nums); i++ { prefixSum[i] = prefixSum[i-1] + ones[i-1] } freq := make(map[int]int) maxRight := 0 for i := len(nums) - k; i >= 0; i-- { freq[prefixSum[i+k]-prefixSum[i]]++ if prefixSum[i+k]-prefixSum[i] <= maxRight { maxRight = prefixSum[i+k]-prefixSum[i] } } return k - maxRight } ``` 对于输入 `[1,0,0,1,0,1]` 和 `k = 2`,函数 `minSwaps` 的输出为 `1`。