Easy
题目描述
给你一个整数数组 nums。
首先选择一个起始位置 curr，使得 nums[curr] == 0，并选择一个移动方向（向左或向右）。
之后，重复以下过程：
- 如果
curr超出了范围[0, n - 1]，则过程结束。 - 如果
nums[curr] == 0，则朝当前方向移动，即如果向右移动则curr递增，如果向左移动则curr递减。 - 否则如果
nums[curr] > 0：- 将
nums[curr]减 1。 - 反转移动方向（左变右，右变左）。
- 朝新方向移动一步。
- 将
如果在过程结束时数组 nums 中的每个元素都变为 0，则认为初始位置 curr 和移动方向的选择是有效的。
返回可能的有效选择数量。
示例 1：
输入：nums = [1,0,2,0,3]
输出：2
示例 2：
输入：nums = [2,3,4,0,4,1,0]
输出：0
约束条件：
1 <= nums.length <= 1000 <= nums[i] <= 100- 至少存在一个元素
i使得nums[i] == 0
解题思路
解题思路
这是一个模拟题，需要按照题目描述的规则来模拟整个过程。
核心思路：
- 找到所有值为 0 的位置作为可能的起始点
- 对每个起始点，尝试向左和向右两个方向
- 模拟移动过程：
- 遇到 0 则继续当前方向移动
- 遇到正数则减 1，反转方向，然后移动
- 超出边界则结束
- 检查最终是否所有元素都变为 0
模拟过程的细节：
- 当前位置为 0 时，直接按当前方向移动到下一位置
- 当前位置为正数时，先减 1，再反转方向，最后移动
- 需要避免无限循环，可以设置最大步数限制
时间复杂度优化： 由于数组长度最大 100，每个元素最大 100，理论上最多需要 100 × 100 = 10,000 步就能结束，可以安全地进行暴力模拟。
这道题的关键是正确理解题意并准确实现模拟逻辑，特别要注意方向反转的时机。
代码实现
class Solution {
public:
int countValidSelections(vector<int>& nums) {
int n = nums.size();
int validCount = 0;
// 尝试每个值为0的位置作为起始点
for (int start = 0; start < n; start++) {
if (nums[start] != 0) continue;
// 尝试向左和向右两个方向
for (int direction : {-1, 1}) {
vector<int> temp = nums;
int curr = start;
int dir = direction;
bool valid = true;
int steps = 0;
const int MAX_STEPS = 10000;
while (steps < MAX_STEPS) {
steps++;
if (curr < 0 || curr >= n) {
break;
}
if (temp[curr] == 0) {
curr += dir;
} else {
temp[curr]--;
dir = -dir;
curr += dir;
}
}
// 检查是否所有元素都变为0
bool allZero = true;
for (int x : temp) {
if (x != 0) {
allZero = false;
break;
}
}
if (allZero) {
validCount++;
}
}
}
return validCount;
}
};
class Solution:
def countValidSelections(self, nums: List[int]) -> int:
n = len(nums)
valid_count = 0
# 尝试每个值为0的位置作为起始点
for start in range(n):
if nums[start] != 0:
continue
# 尝试向左和向右两个方向
for direction in [-1, 1]:
temp = nums[:]
curr = start
dir = direction
steps = 0
MAX_STEPS = 10000
while steps < MAX_STEPS:
steps += 1
if curr < 0 or curr >= n:
break
if temp[curr] == 0:
curr += dir
else:
temp[curr] -= 1
dir = -dir
curr += dir
# 检查是否所有元素都变为0
if all(x == 0 for x in temp):
valid_count += 1
return valid_count
public class Solution {
public int CountValidSelections(int[] nums) {
int n = nums.Length;
int validCount = 0;
// 尝试每个值为0的位置作为起始点
for (int start = 0; start < n; start++) {
if (nums[start] != 0) continue;
// 尝试向左和向右两个方向
foreach (int direction in new int[] {-1, 1}) {
int[] temp = new int[n];
Array.Copy(nums, temp, n);
int curr = start;
int dir = direction;
int steps = 0;
const int MAX_STEPS = 10000;
while (steps < MAX_STEPS) {
steps++;
if (curr < 0 || curr >= n) {
break;
}
if (temp[curr] == 0) {
curr += dir;
} else {
temp[curr]--;
dir = -dir;
curr += dir;
}
}
// 检查是否所有元素都变为0
bool allZero = true;
for (int i = 0; i < n; i++) {
if (temp[i] != 0) {
allZero = false;
break;
}
}
if (allZero) {
validCount++;
}
}
}
return validCount;
}
}
/**
* @param {number[]} nums
* @return {number}
*/
var countValidSelections = function(nums) {
let count = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] === 0) {
// Try moving left
if (simulate([...nums], i, -1)) count++;
// Try moving right
if (simulate([...nums], i, 1)) count++;
}
}
return count;
};
function simulate(nums, curr, direction) {
while (curr >= 0 && curr < nums.length) {
if (nums[curr] === 0) {
curr += direction;
} else {
nums[curr]--;
direction *= -1;
curr += direction;
}
}
return nums.every(num => num === 0);
}
复杂度分析
| 复杂度类型 | 复杂度 |
|---|---|
| 时间复杂度 | O(n × S) |
| 空间复杂度 | O(n) |
其中 n 是数组长度，S 是模拟步数的上界。在最坏情况下，S ≈ n × max(nums[i])，由于约束条件 n ≤ 100，nums[i] ≤ 100，所以 S ≤ 10,000，实际时间复杂度约为 O(n²)。