minimum-deletions-to-make-array-sharp

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

The XOR of two integers is zero exactly when they are equal. Therefore, adjacent retained elements must have different values.

Keep exactly one element from each maximal run of equal values. The number of deletions equals the number of adjacent equal pairs in the original array.

Algorithms

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

You may delete any number of elements from <code>nums</code>. The remaining elements keep their original order.

The resulting array <code>a</code> is sharp if the bitwise XOR of every pair of adjacent elements is non-zero. That is, <code>a[i] XOR a[i + 1] != 0</code> for every index <code>i</code> such that <code>0 &lt;= i &lt; a.length - 1</code>. An array with at most one element is sharp.

Return the minimum number of deletions needed to make <code>nums</code> sharp.

Bitwise XOR compares the corresponding bits of two integers. A bit in the result is 1 if the corresponding bits differ, and 0 otherwise.

&nbsp;
Example 1:

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

Output: 3

Explanation:

<ul>
	<li>The pairs at indices <code>(0, 1)</code>, <code>(2, 3)</code>, and <code>(3, 4)</code> each have an XOR of 0.</li>
	<li>Deleting one 1 and two 2s leaves <code>[1, 2, 3]</code>, where <code>1 XOR 2 == 3</code> and <code>2 XOR 3 == 1</code> are both non-zero. Therefore, the answer is 3.</li>
</ul>
</div>

Example 2:

<div class="example-block">
Input: nums = [4,4,9,4]

Output: 1

Explanation:

<ul>
	<li>The pair at indices <code>(0, 1)</code> has an XOR of 0.</li>
	<li>Deleting either of these two 4s leaves <code>[4, 9, 4]</code>, where <code>4 XOR 9 == 13</code> and <code>9 XOR 4 == 13</code> are both non-zero.</li>
</ul>
</div>

&nbsp;
Constraints:

<ul>
	<li><code>2 &lt;= nums.length &lt;= 100</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 100</code></li>
</ul>

第 524 场周赛

weekly-contest-524

minDeletions

Minimum Deletions to Make Array Sharp

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

你可以从 <code>nums</code> 中删除任意数量的元素。剩余元素保持原有的相对顺序。

如果结果数组 <code>a</code> 中每一对&nbsp;相邻&nbsp;元素的&nbsp;按位异或&nbsp;结果都&nbsp;不为 0，则称数组 <code>a</code> 是&nbsp;相邻异或非零数组&nbsp;。也就是说，对于每个满足 <code>0 &lt;= i &lt; a.length - 1</code> 的下标 <code>i</code>，都有 <code>a[i] XOR a[i + 1] != 0</code>。长度不超过 1 的数组也被视为相邻异或非零数组。

返回使 <code>nums</code> 变为相邻异或非零数组所需的&nbsp;最少&nbsp;删除次数。

按位异或&nbsp;会逐位比较两个整数对应的二进制位。如果对应位不同，则结果中的该位为 1；否则为 0。

&nbsp;

示例 1：

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

输出： 3

解释：

<ul>
	<li>下标对 <code>(0, 1)</code>、<code>(2, 3)</code> 和 <code>(3, 4)</code> 对应元素的异或结果均为 0。</li>
	<li>删除一个 1 和两个 2 后，得到 <code>[1, 2, 3]</code>，其中 <code>1 XOR 2 == 3</code> 且 <code>2 XOR 3 == 1</code>，两者都不为 0。因此，答案为 3。</li>
</ul>
</div>

示例 2：

<div class="example-block">
输入： nums = [4,4,9,4]

输出： 1

解释：

<ul>
	<li>下标对 <code>(0, 1)</code> 对应元素的异或结果为 0。</li>
	<li>删除这两个 4 中的任意一个后，得到 <code>[4, 9, 4]</code>，其中 <code>4 XOR 9 == 13</code> 且 <code>9 XOR 4 == 13</code>，两者都不为 0。</li>
</ul>
</div>

&nbsp;

提示：

<ul>
	<li><code>2 &lt;= nums.length &lt;= 100</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 100</code></li>
</ul>

使相邻元素按位异或非零的最少删除次数

执行通过

错误解答

超出内存限制

超出输出限制

超出时间限制

执行出错

内部出错

编译出错

超时

Restrictions Failed

给你一个整数数组 nums。

你可以从 nums 中删除任意数量的元素。剩余元素保持原有的相对顺序。

如果结果数组 a 中每一对 相邻 元素的 按位异或 结果都 不为 0，则称数组 a 是 相邻异或非零数组 。也就是说，对于每个满足 0 <= i < a.length - 1 的下标 i，都有 a[i] XOR a[i + 1] != 0。长度不超过 1 的数组也被视为相邻异或非零数组。

返回使 nums 变为相邻异或非零数组所需的 最少 删除次数。

按位异或 会逐位比较两个整数对应的二进制位。如果对应位不同，则结果中的该位为 1；否则为 0。

 

示例 1：

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

输出： 3

解释：

 * 下标对 (0, 1)、(2, 3) 和 (3, 4) 对应元素的异或结果均为 0。
 * 删除一个 1 和两个 2 后，得到 [1, 2, 3]，其中 1 XOR 2 == 3 且 2 XOR 3 == 1，两者都不为 0。因此，答案为 3。

示例 2：

输入： nums = [4,4,9,4]

输出： 1

解释：

 * 下标对 (0, 1) 对应元素的异或结果为 0。
 * 删除这两个 4 中的任意一个后，得到 [4, 9, 4]，其中 4 XOR 9 == 13 且 9 XOR 4 == 13，两者都不为 0。

 

提示：

 * 2 <= nums.length <= 100
 * 1 <= nums[i] <= 100