1652. 拆炸弹

🟢   🔖  数组 滑动窗口  🔗 力扣 LeetCode

题目

You have a bomb to defuse, and your time is running out! Your informer will provide you with a circular array code of length of n and a key k.

To decrypt the code, you must replace every number. All the numbers are replaced simultaneously.

• If k > 0, replace the ith number with the sum of the next k numbers.
• If k < 0, replace the ith number with the sum of the previous k numbers.
• If k == 0, replace the ith number with 0.

As code is circular, the next element of code[n-1] is code[0], and the previous element of code[0] is code[n-1].

Given the circular array code and an integer key k, return the decrypted code to defuse the bomb!

Example 1:

Input: code = [5,7,1,4], k = 3

Output: [12,10,16,13]

Explanation: Each number is replaced by the sum of the next 3 numbers. The decrypted code is [7+1+4, 1+4+5, 4+5+7, 5+7+1]. Notice that the numbers wrap around.

Example 2:

Input: code = [1,2,3,4], k = 0

Output: [0,0,0,0]

Explanation: When k is zero, the numbers are replaced by 0.

Example 3:

Input: code = [2,4,9,3], k = -2

Output: [12,5,6,13]

Explanation: The decrypted code is [3+9, 2+3, 4+2, 9+4]. Notice that the numbers wrap around again. If k is negative, the sum is of the previous numbers.

Constraints:

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

题目大意

你有一个炸弹需要拆除，时间紧迫！你的情报员会给你一个长度为 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 时，所有数字都被 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. 初始滑动窗口

• 使用变量 sum 来记录第一个窗口的和。
• 对于 k > 0，初始窗口范围是数组第 1 到第 k 个元素。
• 对于 k < 0，初始窗口范围是数组倒数第 1 到倒数第 |k| 个元素。
• 通过循环计算初始窗口的和 sum。

2. 滑动窗口遍历数组

• 从索引 i = 1 开始，逐步更新 sum 和结果数组 res：
  • 当 k > 0 时：
    • 将窗口的右端扩展到 (i + k) % n。
    • 从窗口中移除的元素是当前索引 i 的元素。
  • 当 k < 0 时：
    • 从窗口中移除的元素是窗口左端 (i + k - 1 + n) % n。
    • 将窗口的左端扩展到 (i - 1 + n) % n。
• 将更新后的 sum 追加到结果数组 res。

3. 最终返回结果数组 res。

复杂度分析

• 时间复杂度：O(n + |k|)，初始窗口和计算需要 O(|k|)，数组遍历和滑动窗口更新需要 O(n)。
• 空间复杂度：O(n)，结果数组 res 占用 O(n) 空间，其余变量为常数级空间。

代码

/**
 * @param {number[]} code
 * @param {number} k
 * @return {number[]}
 */
var decrypt = function (code, k) {
	const n = code.length;

	// 如果 k == 0，返回一个全为 0 的数组
	if (k == 0) return new Array(n).fill(0);

	const direction = k > 0 ? 1 : -1; // 确定方向
	let sum = 0;
	for (let i = 1; i <= Math.abs(k); i++) {
		const idx = (0 + i * direction + n) % n;
		sum += code[idx];
	}

	// 初始化结果数组并加入第一个窗口的和
	let res = [sum];

	// 遍历数组更新窗口和结果
	for (let i = 1; i < n; i++) {
		if (k > 0) {
			// k > 0 时，扩展窗口右端 (i + k) % n，移除窗口左端 i
			sum = sum + code[(i + k) % n] - code[i];
		} else {
			// k < 0 时，移除窗口左端 (i + k - 1 + n) % n，扩展窗口左端 (i - 1 + n) % n
			sum = sum - code[(i + k - 1 + n) % n] + code[(i - 1 + n) % n];
		}
		res.push(sum);
	}

	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
2490	回环句	[✓]	字符串	🟢	🀄️ 🔗
2515	到目标字符串的最短距离		数组 字符串	🟢	🀄️ 🔗
2516	每种字符至少取 K 个	[✓]	哈希表 字符串 滑动窗口	🟠	🀄️ 🔗