边界上的蚂蚁

标签: 数组前缀和模拟

难度: Easy

边界上有一只蚂蚁，它有时向左走，有时向右走。

给你一个非零整数数组 nums 。蚂蚁会按顺序读取 nums 中的元素，从第一个元素开始直到结束。每一步，蚂蚁会根据当前元素的值移动：

如果 nums[i] < 0 ，向左移动 -nums[i]单位。
如果 nums[i] > 0 ，向右移动 nums[i]单位。

返回蚂蚁返回到边界上的次数。

注意：

边界两侧有无限的空间。
只有在蚂蚁移动了 |nums[i]| 单位后才检查它是否位于边界上。换句话说，如果蚂蚁只是在移动过程中穿过了边界，则不会计算在内。

示例 1：

输入：nums = [2,3,-5]
输出：1
解释：第 1 步后，蚂蚁距边界右侧 2 单位远。
第 2 步后，蚂蚁距边界右侧 5 单位远。
第 3 步后，蚂蚁位于边界上。
所以答案是 1 。

示例 2：

输入：nums = [3,2,-3,-4]
输出：0
解释：第 1 步后，蚂蚁距边界右侧 3 单位远。
第 2 步后，蚂蚁距边界右侧 5 单位远。
第 3 步后，蚂蚁距边界右侧 2 单位远。
第 4 步后，蚂蚁距边界左侧 2 单位远。
蚂蚁从未返回到边界上，所以答案是 0 。

提示：

1 <= nums.length <= 100
-10 <= nums[i] <= 10
nums[i] != 0

Submission

运行时间: 21 ms

内存: 16.0 MB

class Solution:
    def returnToBoundaryCount(self, nums: List[int]) -> int:
        x=0
        k=0
        for i in range(len(nums)):
            # if nums[i]>0:
            #    x=x+nums[i] 
            # else:
            x=x+nums[i]
            if x==0:
                k+=1

        return k

Explain

该题解通过模拟蚂蚁的行进来计算蚂蚁返回到边界的次数。初始化蚂蚁的位置为0（表示边界位置）。遍历数组nums中的每个元素，根据元素的正负值更新蚂蚁的位置（向右或向左移动相应的单位数）。在每次更新位置后，检查蚂蚁是否返回到了边界（位置为0）。如果是，则计数器增加。最终返回计数器的值，即为蚂蚁返回到边界的总次数。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def returnToBoundaryCount(self, nums: List[int]) -> int:
        x = 0  # 蚂蚁的当前位置
        k = 0  # 返回边界的次数
        for i in range(len(nums)):
            x = x + nums[i]  # 更新蚂蚁的位置
            if x == 0:  # 检查是否返回到边界
                k += 1  # 如果是，则计数器增加
        return k  # 返回蚂蚁返回到边界的总次数

Explore

在算法的设计中，初始位置即为边界，但通常考虑的是在遍历操作数组之后的动态变化以及其对状态的影响。计数开始于蚂蚁的移动之后，因为题目关注的是通过数组的操作使得蚂蚁如何从初始状态变化后返回到边界。如果需要计算初始状态作为一次返回，可以在循环开始前初始化计数器为1，但这取决于题目的具体要求。

是的，当前算法只检查每次更新位置后的状态，而不跟踪蚂蚁在达到下一个位置之前的具体路径。如果nums数组中的元素足够大，可能导致蚂蚁在两次位置更新之间多次穿越边界，但这些情况不会被当前算法捕捉。要解决这个问题，需要实现一个更细致的模拟，跟踪每一步的具体移动，或者在每次大步移动中分解成多个小步骤来判断是否穿越了边界。

并非数组中的每个元素都必然导致蚂蚁返回到边界。蚂蚁是否返回边界取决于当前位置和元素的具体值。特定的数值或数值组合，如使总移动量恰好抵消之前的累积移动，才会导致蚂蚁返回边界。例如，如果蚂蚁向右移动了5步，随后的元素需要是-5才能使蚂蚁返回到原始边界。