make-array-elements-equal-to-zero

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an integer array <code>nums</code>.

Start by selecting a starting position <code>curr</code> such that <code>nums[curr] == 0</code>, and choose a movement direction of&nbsp;either left or right.

After that, you repeat the following process:

<ul>
	<li>If <code>curr</code> is out of the range <code>[0, n - 1]</code>, this process ends.</li>
	<li>If <code>nums[curr] == 0</code>, move in the current direction by incrementing <code>curr</code> if you are moving right, or decrementing <code>curr</code> if you are moving left.</li>
	<li>Else if <code>nums[curr] &gt; 0</code>:
	<ul>
		<li>Decrement <code>nums[curr]</code> by 1.</li>
		<li>Reverse&nbsp;your movement direction (left becomes right and vice versa).</li>
		<li>Take a step in your new direction.</li>
	</ul>
	</li>
</ul>

A selection of the initial position <code>curr</code> and movement direction is considered valid if every element in <code>nums</code> becomes 0 by the end of the process.

Return the number of possible valid selections.

&nbsp;
Example 1:

<div class="example-block">
Input: nums = [1,0,2,0,3]

Output: 2

Explanation:

The only possible valid selections are the following:

<ul>
	<li>Choose <code>curr = 3</code>, and a movement direction to the left.

	<ul>
		<li><code>[1,0,2,0,3] -&gt; [1,0,2,0,3] -&gt; [1,0,1,0,3] -&gt; [1,0,1,0,3] -&gt; [1,0,1,0,2] -&gt; [1,0,1,0,2] -&gt; [1,0,0,0,2] -&gt; [1,0,0,0,2] -&gt; [1,0,0,0,1] -&gt; [1,0,0,0,1] -&gt; [1,0,0,0,1] -&gt; [1,0,0,0,1] -&gt; [0,0,0,0,1] -&gt; [0,0,0,0,1] -&gt; [0,0,0,0,1] -&gt; [0,0,0,0,1] -&gt; [0,0,0,0,0]</code>.</li>
	</ul>
	</li>
	<li>Choose <code>curr = 3</code>, and a movement direction to the right.
	<ul>
		<li><code>[1,0,2,0,3] -&gt; [1,0,2,0,3] -&gt; [1,0,2,0,2] -&gt; [1,0,2,0,2] -&gt; [1,0,1,0,2] -&gt; [1,0,1,0,2] -&gt; [1,0,1,0,1] -&gt; [1,0,1,0,1] -&gt; [1,0,0,0,1] -&gt; [1,0,0,0,1] -&gt; [1,0,0,0,0] -&gt; [1,0,0,0,0] -&gt; [1,0,0,0,0] -&gt; [1,0,0,0,0] -&gt; [0,0,0,0,0].</code></li>
	</ul>
	</li>
</ul>
</div>

Example 2:

<div class="example-block">
Input: nums = [2,3,4,0,4,1,0]

Output: 0

Explanation:

There are no possible valid selections.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 100</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 100</code></li>
	<li>There is at least one element <code>i</code> where <code>nums[i] == 0</code>.</li>
</ul>

countValidSelections

Make Array Elements Equal to Zero

Array

Prefix Sum

Simulation

给你一个整数数组&nbsp;<code>nums</code> 。

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

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

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

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

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

&nbsp;

示例 1：

<div class="example-block">
输入：nums = [1,0,2,0,3]

输出：2

解释：

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

<ul>
	<li>选择&nbsp;<code>curr = 3</code>&nbsp;并向左移动。

	<ul>
		<li><code>[1,0,2,0,3] -&gt; [1,0,2,0,3] -&gt; [1,0,1,0,3] -&gt; [1,0,1,0,3] -&gt; [1,0,1,0,2] -&gt; [1,0,1,0,2] -&gt; [1,0,0,0,2] -&gt; [1,0,0,0,2] -&gt; [1,0,0,0,1] -&gt; [1,0,0,0,1] -&gt; [1,0,0,0,1] -&gt; [1,0,0,0,1] -&gt; [0,0,0,0,1] -&gt; [0,0,0,0,1] -&gt; [0,0,0,0,1] -&gt; [0,0,0,0,1] -&gt; [0,0,0,0,0]</code>.</li>
	</ul>
	</li>
	<li>选择&nbsp;<code>curr = 3</code>&nbsp;并向右移动。
	<ul>
		<li><code>[1,0,2,0,3] -&gt; [1,0,2,0,3] -&gt; [1,0,2,0,2] -&gt; [1,0,2,0,2] -&gt; [1,0,1,0,2] -&gt; [1,0,1,0,2] -&gt; [1,0,1,0,1] -&gt; [1,0,1,0,1] -&gt; [1,0,0,0,1] -&gt; [1,0,0,0,1] -&gt; [1,0,0,0,0] -&gt; [1,0,0,0,0] -&gt; [1,0,0,0,0] -&gt; [1,0,0,0,0] -&gt; [0,0,0,0,0].</code></li>
	</ul>
	</li>
</ul>
</div>

示例 2：

<div class="example-block">
输入：nums = [2,3,4,0,4,1,0]

输出：0

解释：

不存在有效的选择方案。
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 100</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 100</code></li>
	<li>至少存在一个元素&nbsp;<code>i</code>&nbsp;满足&nbsp;<code>nums[i] == 0</code> 。</li>
</ul>