2024-10-13:用 go 语言,给定一个二进制数组 nums,长度为 n, 目标是让 Alice 通过最少的行动次数从 nums 中拾取 k 个 1。 Alice 可以选择任何索引 aliceIndex
2024-10-13:用 go 语言,给定一个二进制数组 nums,长度为 n,
目标是让 Alice 通过最少的行动次数从 nums 中拾取 k 个 1。
Alice 可以选择任何索引 aliceIndex,如果对应的 nums[aliceIndex] 是 1,Alice 会拾取一个 1 并将其设为 0。
之后,Alice 可以选择以下两种行动之一:
将一个 0 变为 1(最多执行 maxChanges 次),或交换相邻的两个数(一个是 1,一个是 0)。
返回拾取 k 个 1 所需的最少行动次数。
输入:nums = [1,1,0,0,0,1,1,0,0,1], k = 3, maxChanges = 1。
输出:3。
解释:如果游戏开始时 Alice 在 aliceIndex == 1 的位置上,按照以下步骤执行每个动作,他可以利用 3 次行动拾取 3 个 1 :
游戏开始时 Alice 拾取了一个 1 ,nums[1] 变成了 0。此时 nums 变为 [1,0,0,0,0,1,1,0,0,1] 。
选择 j == 2 并执行第一种类型的动作。nums 变为 [1,0,1,0,0,1,1,0,0,1]
选择 x == 2 和 y == 1 ,并执行第二种类型的动作。nums 变为 [1,1,0,0,0,1,1,0,0,1] 。由于 y == aliceIndex,Alice 拾取了一个 1 ,nums 变为 [1,0,0,0,0,1,1,0,0,1] 。
选择 x == 0 和 y == 1 ,并执行第二种类型的动作。nums 变为 [0,1,0,0,0,1,1,0,0,1] 。由于 y == aliceIndex,Alice 拾取了一个 1 ,nums 变为 [0,0,0,0,0,1,1,0,0,1] 。
请注意,Alice 也可能执行其他的 3 次行动序列达成拾取 3 个 1 。
答案 2024-10-13:
题目来自 leetcode3086。
大体步骤如下:
1.首先定义了一个辅助函数 f(i) 用来计算索引 i 周围的数之和(包括自身)。
2.在主函数 minimumMoves 中,采用双指针的方法来实现解题的逻辑。
3.初始化左右指针 left, right 为 0,-1,左右两侧和左右两侧计数和求和 leftCount, rightCount, leftSum, rightSum 都初始化为 0。
4.定义变量 res 为 int64 类型的最大值 math.MaxInt64。
5.遍历数组 nums 中每个元素,依次判断条件:
如果 f(i) + maxChanges 大于等于 k,则执行下面的逻辑。
比较 k 和 f(i) 的大小,选择取的数为 k 还是 f(i)。
如果 k 小于等于 maxChanges,则继续遍历下一个数。
6.进入双指针逻辑的循环:
循环直到右指针 right 指向的位置和左指针 left 之间的距离小于等于左指针和 i 之间的距离,且左右两侧数量之和小于 k。
若右指针指向的数为 1,则将右侧计数、和增加。
7.接下来在一个 while 循环内调整左右指针位置,使得左右两侧数量之和不超过 k。
8.对于每一次循环,计算当前情况下拾取 k 个 1 所需的最少行动次数,并更新 res。
9.最后在循环中,对左右计数、和进行一系列调整。
10.返回 res 作为最终结果。
总的时间复杂度:
整体是两个循环的嵌套,外部循环遍历数组中的每个元素,内部循环是双指针逻辑,所以时间复杂度是 O(n^2)。
总的额外空间复杂度:
只使用了一些常量级别的额外空间来存储几个变量,所以额外空间复杂度是 O(1)。
Go 完整代码如下:
版权声明: 本文为 InfoQ 作者【福大大架构师每日一题】的原创文章。
原文链接:【http://xie.infoq.cn/article/f7cd6d858ace071696a00e714】。
本文遵守【CC-BY 4.0】协议,转载请保留原文出处及本版权声明。
评论