leetcode
leetcode 2851 ~ 2900
数字游戏

数字游戏

难度:

标签:

题目描述

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)

代码细节讲解

🦆
为什么在处理数组时首先要对每个元素执行减去其索引的操作?这样做的目的和好处是什么?
在处理数组时,对每个元素减去其索引的操作是为了将问题转化为寻找一个连续的、以0开始递增的数列。原问题要求nums[a]+1 == nums[a+1],减去索引后,这个条件变为新数组中的相邻元素应该相等。这种转换简化了问题,使得我们可以通过维护一个当前的标准值和左右两边的元素数量差值来优化操作,从而更有效地达到目标条件。
🦆
题解中提到维护一个当前的标准值`cur`以及左右两边的元素数量差值`totalDiff`,请问这两个变量具体是如何影响操作次数计算的?
在算法中,`cur`表示当前的最优或标准值,即使得操作次数最小的目标数值。`totalDiff`是左右两边相对于`cur`的元素数量差值,用于判断是否需要调整`cur`以达到更优的操作次数。当新的元素数值与`cur`不一致时,根据它们的差值和`totalDiff`的正负,我们可以确定是增加还是减少`cur`,并计算因此产生的操作次数。调整`cur`时,我们还需要考虑跳过那些计数为0的值,以确保`cur`总是指向存在的元素,从而最小化操作次数。
🦆
在调整标准值`cur`时,如果新的目标`target`需要跳过一些没有元素的位置,这种跳过操作在算法中是如何实现的?
当需要调整标准值`cur`到新的目标`target`,且`target`处的元素计数为0时,算法通过循环遍历`cnt`数组来寻找下一个非零计数的位置。这个遍历过程涉及向左或向右检查直到找到有元素的位置。通过这种方式,我们确保了`cur`总是更新到有效的、有实际元素存在的位置,即使需要跳过一些计数为0的间隔。这个过程是通过简单的循环实现的,保证了在调整`cur`时总能找到最近的有效目标值。

相关问题