3354. 使数组元素等于零

news/2024/11/19 10:00:38/

3354、leetcode.cn/problems/make-array-elements-equal-to-zero/description/" rel="nofollow">[简单] 使数组元素等于零

1、题目描述

给你一个整数数组 nums 。

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

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

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

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

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

2、解题思路

问题描述：
- 从一个初始位置 curr 开始，选择方向（左或右），按题目要求依次处理元素。
- 如果结束时 nums 所有元素为 0，则此方案有效。
- 我们需要统计满足条件的方案数目。
核心逻辑：
- 遍历所有满足 nums[curr] == 0 的起始位置 curr。
- 针对每个起始位置，尝试两种移动方向（左、右），模拟过程并验证是否满足条件。
- 使用辅助数组 temp 保存当前模拟的状态，避免修改原始数组。
模拟移动：
- 如果当前位置值是 0，继续沿当前方向移动。
- 如果当前位置值是 >0：
  - 减少当前值 1。
  - 反转方向。
  - 移动一步。
- 如果当前位置越界（curr < 0 或 curr >= n），结束模拟。
优化点：
- 尽量减少不必要的模拟操作。
- 当发现某个状态无法满足条件时立即终止。

3、代码实现

class Solution {
public:int countValidSelections(vector<int>& nums) {int n = nums.size();int result = 0;// 遍历所有可能的起始位置for (int start = 0; start < n; ++start) {if (nums[start] != 0)continue;// 两个方向：1 表示向右，-1 表示向左for (int direction : {1, -1}) {vector<int> temp = nums; // 临时数组用于模拟int curr = start;bool valid = true;while (curr >= 0 && curr < n) {if (temp[curr] == 0) {// 当前位置为 0，继续移动curr += direction;} else if (temp[curr] > 0) {// 当前位置值 > 0temp[curr]--;           // 减少当前值direction = -direction; // 反转方向curr += direction;      // 移动一步} else {// 理论上不会出现这种情况valid = false;break;}}// 如果数组所有元素都变为 0，则该方案有效if (valid && all_of(temp.begin(), temp.end(), [](int x) { return x == 0; })) {result++;}}}return result;}
};