Easy

题目描述

你有一个炸弹需要拆除，时间不多了！你的线人会提供一个长度为 n 的环形数组 code 和一个密钥 k。

要破译密码，你必须替换每个数字。所有数字都是同时替换的。

  • 如果 k > 0，将第 i 个数字替换为接下来 k 个数字的和。
  • 如果 k < 0，将第 i 个数字替换为前面 -k 个数字的和。
  • 如果 k == 0，将第 i 个数字替换为 0。

由于 code 是环形的，code[n-1] 的下一个元素是 code[0]，code[0] 的前一个元素是 code[n-1]。

给定环形数组 code 和整数密钥 k，返回解密后的代码来拆除炸弹！

示例 1：

输入：code = [5,7,1,4], k = 3
输出：[12,10,16,13]
解释：每个数字都被接下来 3 个数字的和替换。解密后的代码是 [7+1+4, 1+4+5, 4+5+7, 5+7+1]。注意数字是环形的。

示例 2：

输入：code = [1,2,3,4], k = 0
输出：[0,0,0,0]
解释：当 k 为零时，数字被替换为 0。

示例 3：

输入：code = [2,4,9,3], k = -2
输出：[12,5,6,13]
解释：解密后的代码是 [3+9, 2+3, 4+2, 9+4]。注意数字再次环形。如果 k 是负数，则是前面数字的和。

提示：

  • n == code.length
  • 1 <= n <= 100
  • 1 <= code[i] <= 100
  • -(n - 1) <= k <= n - 1

解题思路

这道题要求我们对环形数组进行特殊的求和操作。核心在于处理环形数组的索引计算和三种不同的情况。

思路分析：

  1. k = 0 的情况：最简单，所有位置都填 0。

  2. k > 0 的情况：对于每个位置 i，需要计算后面 k 个数字的和。由于是环形数组，需要使用模运算处理索引越界。

  3. k < 0 的情况：对于每个位置 i，需要计算前面 |k| 个数字的和。同样需要处理环形索引。

优化方案：

  • 方法一：暴力解法，对每个位置直接计算所需的和，时间复杂度 O(n×|k|)
  • 方法二：滑动窗口优化，先计算第一个窗口的和，然后滑动窗口更新，时间复杂度 O(n)

由于题目约束较小(n ≤ 100)，两种方法都可行，但滑动窗口更优雅。这里给出滑动窗口的解法。

实现要点：

  • 使用模运算 (i + n) % n 处理负索引
  • 预先计算窗口和，然后滑动更新
  • 分别处理 k > 0 和 k < 0 的情况

代码实现

class Solution {
public:
    vector<int> decrypt(vector<int>& code, int k) {
        int n = code.size();
        vector<int> result(n, 0);
        
        if (k == 0) return result;
        
        // 计算初始窗口和
        int windowSum = 0;
        int start, end;
        
        if (k > 0) {
            // k > 0: 计算后面k个数字的和
            start = 1;
            end = k;
        } else {
            // k < 0: 计算前面|k|个数字的和
            start = n + k;
            end = n - 1;
        }
        
        // 计算初始窗口和
        for (int i = start; i <= end; i++) {
            windowSum += code[i % n];
        }
        
        // 滑动窗口
        for (int i = 0; i < n; i++) {
            result[i] = windowSum;
            // 移除窗口最左边的元素，添加下一个元素
            windowSum -= code[start % n];
            start++;
            end++;
            windowSum += code[end % n];
        }
        
        return result;
    }
};

class Solution:
    def decrypt(self, code: List[int], k: int) -> List[int]:
        n = len(code)
        result = [0] * n
        
        if k == 0:
            return result
        
        # 计算初始窗口和
        window_sum = 0
        if k > 0:
            # k > 0: 计算后面k个数字的和
            start, end = 1, k
        else:
            # k < 0: 计算前面|k|个数字的和
            start, end = n + k, n - 1
        
        # 计算初始窗口和
        for i in range(start, end + 1):
            window_sum += code[i % n]
        
        # 滑动窗口
        for i in range(n):
            result[i] = window_sum
            # 移除窗口最左边的元素，添加下一个元素
            window_sum -= code[start % n]
            start += 1
            end += 1
            window_sum += code[end % n]
        
        return result

public class Solution {
    public int[] Decrypt(int[] code, int k) {
        int n = code.Length;
        int[] result = new int[n];
        
        if (k == 0) return result;
        
        // 计算初始窗口和
        int windowSum = 0;
        int start, end;
        
        if (k > 0) {
            // k > 0: 计算后面k个数字的和
            start = 1;
            end = k;
        } else {
            // k < 0: 计算前面|k|个数字的和
            start = n + k;
            end = n - 1;
        }
        
        // 计算初始窗口和
        for (int i = start; i <= end; i++) {
            windowSum += code[i % n];
        }
        
        // 滑动窗口
        for (int i = 0; i < n; i++) {
            result[i] = windowSum;
            // 移除窗口最左边的元素，添加下一个元素
            windowSum -= code[start % n];
            start++;
            end++;
            windowSum += code[end % n];
        }
        
        return result;
    }
}

var decrypt = function(code, k) {
    const n = code.length;
    const result = new Array(n);
    
    if (k === 0) {
        return new Array(n).fill(0);
    }
    
    for (let i = 0; i < n; i++) {
        let sum = 0;
        if (k > 0) {
            for (let j = 1; j <= k; j++) {
                sum += code[(i + j) % n];
            }
        } else {
            for (let j = 1; j <= Math.abs(k); j++) {
                sum += code[(i - j + n) % n];
            }
        }
        result[i] = sum;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n)
空间复杂度O(1)

说明：

  • 时间复杂度：O(n)，只需要遍历一次数组，每次窗口滑动都是 O(1) 操作
  • 空间复杂度：O(1)，除了结果数组外，只使用了常数级别的额外空间

相关题目