数字游戏
难度:
标签:
题目描述
English description is not available for the problem. Please switch to Chinese.
代码结果
运行时间: 130 ms, 内存: 35.3 MB
/*
* 思路:
* 使用 Java Stream API 进行处理。
* 对于每个计数器编号 i,从 0 到 i 的序列需要满足 nums[a] + 1 == nums[a + 1]。
* 从前往后遍历,每次计算需要的最小操作数,并更新数组。
* 由于答案可能很大,需要对 1,000,000,007 取余。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public int[] minOperations(int[] nums) {
int MOD = 1_000_000_007;
return IntStream.range(0, nums.length)
.map(i -> {
if (i == 0) return 0;
if (nums[i] != nums[i - 1] + 1) {
nums[i] = nums[i - 1] + 1;
return Math.abs(nums[i] - nums[i - 1]) % MOD;
}
return 0;
})
.toArray();
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {3, 4, 5, 1, 6, 7};
System.out.println(Arrays.toString(sol.minOperations(nums))); // 输出: [0, 0, 0, 5, 6, 7]
}
}
解释
方法:
本题目的是通过最少的操作次数,使得数组nums的前i个元素满足nums[a]+1 == nums[a+1]的条件。为了方便处理,我们首先将数组nums中的每个元素减去其索引,得到一个新的数组。接着,我们从左到右遍历这个新数组,并维护一个当前的标准值cur,以及左右两边的元素数量差值totalDiff。每次遍历到一个新元素时,我们更新左右两边的元素数量,并根据这个数量差值来调整标准值cur,以及计算出当前的最少操作次数res,并将其加入到答案数组ans中。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在处理数组时首先要对每个元素执行减去其索引的操作?这样做的目的和好处是什么?
▷🦆
题解中提到维护一个当前的标准值`cur`以及左右两边的元素数量差值`totalDiff`,请问这两个变量具体是如何影响操作次数计算的?
▷🦆
在调整标准值`cur`时,如果新的目标`target`需要跳过一些没有元素的位置,这种跳过操作在算法中是如何实现的?
▷