4083. 使相邻元素按位异或非零的最少删除次数
难度简单
题目描述
给你一个整数数组 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 <= 1001 <= nums[i] <= 100
解法
方法一
1 | |
1 | |
1 | |
1 | |