当前位置：首页 > article >正文

【从零开始的LeetCode-算法】3354. 使数组元素等于零

article 2024/11/24 0:16:18

给你一个整数数组 nums 。

开始时，选择一个满足 nums[curr] == 0 的起始位置 curr ，并选择一个移动方向：向左或者向右。

此后，你需要重复下面的过程：

如果 curr 超过范围 [0, n - 1] ，过程结束。
如果 nums[curr] == 0 ，沿当前方向继续移动：如果向右移，则递增 curr ；如果向左移，则递减 curr 。
如果 nums[curr] > 0:
- 将 nums[curr] 减 1 。
- 反转移动方向（向左变向右，反之亦然）。
- 沿新方向移动一步。

如果在结束整个过程后，nums 中的所有元素都变为 0 ，则认为选出的初始位置和移动方向有效。

返回可能的有效选择方案数目。

示例 1：

输入：nums = [1,0,2,0,3]

输出：2

解释：

可能的有效选择方案如下：

选择 curr = 3 并向左移动。
[1,0,2,0,3] -> [1,0,2,0,3] -> [1,0,1,0,3] -> [1,0,1,0,3] -> [1,0,1,0,2] -> [1,0,1,0,2] -> [1,0,0,0,2] -> [1,0,0,0,2] -> [1,0,0,0,1] -> [1,0,0,0,1] -> [1,0,0,0,1] -> [1,0,0,0,1] -> [0,0,0,0,1] -> [0,0,0,0,1] -> [0,0,0,0,1] -> [0,0,0,0,1] -> [0,0,0,0,0].
选择 curr = 3 并向右移动。
[1,0,2,0,3] -> [1,0,2,0,3] -> [1,0,2,0,2] -> [1,0,2,0,2] -> [1,0,1,0,2] -> [1,0,1,0,2] -> [1,0,1,0,1] -> [1,0,1,0,1] -> [1,0,0,0,1] -> [1,0,0,0,1] -> [1,0,0,0,0] -> [1,0,0,0,0] -> [1,0,0,0,0] -> [1,0,0,0,0] -> [0,0,0,0,0].

示例 2：

输入：nums = [2,3,4,0,4,1,0]

输出：0

解释：

不存在有效的选择方案。

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 100
至少存在一个元素 i 满足 nums[i] == 0 。

我的解答

class Solution {
    public int countValidSelections(int[] nums) {
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        /**
         * 由示例可知，满足条件的curr左右两边差值必须小于等于1
         * 等于0，即curr左右两边的值相等时，向左向右就可
         * 等于1，即curr左右两边的值相差为1时，仅能先向值大的方向开始移动
         */
        int res = 0,pre = 0;
        for(int num : nums){
            if(num > 0){
                pre += num;
                if(pre * 2 > sum + 1) break;
            }else if(pre * 2 == sum){
                res += 2;
            }else if(Math.abs(pre * 2 - sum) == 1){
                res++;
            }
        }
        return res;
    }
}