前言
速通三道题，第四题题意看了半天，读懂了但是不会做😅
简单记录一下解题过程：
1. 100345. 使所有元素都可以被 3 整除的最少操作数
给你一个整数数组 nums 。一次操作中，你可以将 nums 中的 任意 一个元素增加或者减少 1 。
请你返回将 nums 中所有元素都可以被 3 整除的 最少 操作次数。
输入：nums = [1,2,3,4]
输出：3
解释： 通过以下 3 个操作，数组中的所有元素都可以被 3 整除：
将 1 减少 1 。
将 2 增加 1 。
将 4 减少 1 。
思路
可以任意加1或者减1，那么任何数都可以经过最多依次操作来保证其被3整除。 除了本身可以被3整除的数为 %3 === 1%3 === 2
function minimumOperations(nums: number[]): number {
let res = 0
nums.forEach((item) => {
if (item % 3 === 1 || item % 3 === 2)
res += 1
})
return res
}
function minimumOperations(nums: number[]): number {
let res = 0
nums.forEach((item) => {
if (item % 3 === 1 || item % 3 === 2)
res += 1
})
return res
}
2. 100344. 使二进制数组全部等于 1 的最少操作次数 I
给你一个二进制数组 nums 。
你可以对数组执行以下操作 任意 次（也可以 0 次）：
选择数组中 任意连续 3 个元素，并将它们 全部反转 。 反转 一个元素指的是将它的值从 0 变 1 ，或者从 1 变 0 。
请你返回将 nums 中所有元素变为 1 的 最少 操作次数。如果无法全部变成 1 ，返回 -1 。
输入：nums = [0,1,1,1,0,0]
输出：3
解释： 我们可以执行以下操作：
选择下标为 0 ，1 和 2 的元素并反转，得到 nums = [1,0,0,1,0,0] 。
选择下标为 1 ，2 和 3 的元素并反转，得到 nums = [1,1,1,0,0,0] 。
选择下标为 3 ，4 和 5 的元素并反转，得到 nums = [1,1,1,1,1,1] 。
思路
暴力模拟：通过题意可以发现，从左依次遍历只要遇到0就将其后两个数，包括自身一共三个数反转，直到nums[length-2]
function minOperations(nums: number[]): number {
const arr = nums.slice()
let res = 0
const len = nums.length
for (let i = 0; i < len - 2; i++) {
if (arr[i] === 0) {
arr[i] = 1
arr[i + 1] = arr[i + 1] === 1 ? 0 : 1
arr[i + 2] = arr[i + 2] === 1 ? 0 : 1
res++
}
}
if (!arr[len - 1] || !arr[len - 2])
return -1
return res
}
function minOperations(nums: number[]): number {
const arr = nums.slice()
let res = 0
const len = nums.length
for (let i = 0; i < len - 2; i++) {
if (arr[i] === 0) {
arr[i] = 1
arr[i + 1] = arr[i + 1] === 1 ? 0 : 1
arr[i + 2] = arr[i + 2] === 1 ? 0 : 1
res++
}
}
if (!arr[len - 1] || !arr[len - 2])
return -1
return res
}
3. 100346. 使二进制数组全部等于 1 的最少操作次数 II
给你一个二进制数组 nums 。
你可以对数组执行以下操作 任意 次（也可以 0 次）：
选择数组中 任意 一个下标 i ，并将从下标 i 开始一直到数组末尾 所有 元素 反转 。 反转 一个元素指的是将它的值从 0 变 1 ，或者从 1 变 0 。
请你返回将 nums 中所有元素变为 1 的 最少 操作次数。
输入：nums = [0,1,1,0,1]
输出：4
解释： 我们可以执行以下操作：
选择下标 i = 1 执行操作，得到 nums = [0,0,0,1,0] 。
选择下标 i = 0 执行操作，得到 nums = [1,1,1,0,1] 。
选择下标 i = 4 执行操作，得到 nums = [1,1,1,0,0] 。
选择下标 i = 3 执行操作，得到 nums = [1,1,1,1,1] 。
tip:
1 <= nums.length <= 10^5
0 <= nums[i] <= 1
思路
首先简单想到的同样是暴力模拟：从左到右遍历，遇到0就将其后的所有数反转，直到最后一个数为1
function minOperations(nums: number[]): number {
let res = 0
for (let i = 0; i < nums.length; i++) {
if (nums[i] === 0) {
for (let j = i; j < nums.length; j++)
nums[j] = nums[j] === 0 ? 1 : 0
res++
}
}
return res
}
function minOperations(nums: number[]): number {
let res = 0
for (let i = 0; i < nums.length; i++) {
if (nums[i] === 0) {
for (let j = i; j < nums.length; j++)
nums[j] = nums[j] === 0 ? 1 : 0
res++
}
}
return res
}
显然，从题目的提示可以看到1 <= nums.length <= 10^5，那么 O(n^2) 的时间复杂度显然不可取，所以考虑优化一下。
首先想到的是值是特殊的值，考虑采取亦或来提高运算的效率：nums[j] = nums[j] === 0 ? 1 : 0nums[j] ^= 1
不过从这样简单的计算量的优化始终拜托不了还是 O(n^2) 的时间复杂度的限制，依然超时；
这时候就考虑换一个思路，去读了一遍题目给的示例过程没感觉到什么特殊的处理过程，不过想要降低到 O(n) 的时间复杂度，首先想到的肯定不能去模拟一遍赋值的流程，也许可以直接根据翻转的次数来计算； 这是因为 0 -> 1 -> 0 -> 1 … 这样的反转过程存在奇数偶数次的规律，翻转奇数次得到的是相反的数，翻转偶数次得到的是自身。那么就可以考虑不同的值不同处理： 记翻转次数为res
对于0
当
时，显然我们需要再翻转一次，保证为1 即res%2===0res++当
时，此时正好翻转为1，不做其他处理res%2===1
对于1
当
时，此时正好翻转为1，不做其他处理res%2===0当
时，显然我们需要再翻转一次，保证为1 即res%2===1res++
function minOperations(nums: number[]): number {
let res = 0
for (let i = 0; i < nums.length; i++) {
const item = nums[i]
if (item === 1) {
if (res % 2 === 0)
continue
else
res++
}
else {
if (res % 2 === 1)
continue
else
res++
}
}
return res
}
function minOperations(nums: number[]): number {
let res = 0
for (let i = 0; i < nums.length; i++) {
const item = nums[i]
if (item === 1) {
if (res % 2 === 0)
continue
else
res++
}
else {
if (res % 2 === 1)
continue
else
res++
}
}
return res
}
当然上述代码只是对思路的一个直接描述，还可以有很多工程上的优化；不过对于算法的直接复杂度而言优化不大，这里暂时省略。
第四题 略
总结
常规c3道题，前三道题都比较简单。