LeetCode 1652: 拆炸弹 (Defuse the Bomb)
题目描述
你有一个炸弹需要拆除，时间紧迫！你的情报员会给你一个长度为 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 < 0，那么和为 之前的数字。
提示
n == code.length1 <= n <= 1001 <= code[i] <= 100-(n - 1) <= k <= n - 1
题解
解题思路
使用滑动窗口可以高效解决该问题。在滑动窗口中：
- 初始化第一个窗口的和
s。 - 随着窗口向右滑动，利用增量更新代替重新计算窗口和，减少计算量。
滑动窗口初始位置
- 如果
k > 0：窗口的下标范围是[1, k+1)。 - 如果
k < 0：窗口的下标范围是[n-|k|, n)。
无论 k 是正是负，窗口的大小始终是 |k|。
滑动更新逻辑
- 每次右移窗口：
- 移入窗口的元素下标为
r % n。 - 移出窗口的元素下标为
(r - |k|) % n。
- 移入窗口的元素下标为
- 用
s += 移入元素 - 移出元素更新窗口和。
为什么可以省略 k = 0 的特判？
当 k = 0 时：
- 窗口大小为
|k| = 0，初始和为sum(code[r-k:r]) = sum([]) = 0。 - 滑动窗口更新时，
code[r % n]和code[(r - k) % n]是同一个元素，s的增量总为 0。 - 因此，结果始终是
[0] * n，无需显式处理。
代码实现
from typing import Listclass Solution:def decrypt(self, code: List[int], k: int) -> List[int]:n = len(code)r = k + 1 if k > 0 else n # 初始窗口右边界ans = [0] * nk = abs(k) # 窗口大小s = sum(code[r - k:r]) # 第一个窗口的和for i in range(n):ans[i] = s # 当前窗口的和# 更新窗口和：加上新元素，减去旧元素s += code[r % n] - code[(r - k) % n]r += 1 # 窗口右边界右移return ans
复杂度分析
-
时间复杂度：
- 窗口初始化和为
O(k)。 - 滑动窗口更新和为
O(n)。
总复杂度为O(n + k)。
- 窗口初始化和为
-
空间复杂度：
仅使用了常数额外空间，空间复杂度为O(1)。
示例运行
示例 1
code = [5, 7, 1, 4]
k = 3
solution = Solution()
print(solution.decrypt(code, k)) # 输出：[12, 10, 16, 13]
示例 2
code = [1, 2, 3, 4]
k = 0
print(solution.decrypt(code, k)) # 输出：[0, 0, 0, 0]
示例 3
code = [2, 4, 9, 3]
k = -2
print(solution.decrypt(code, k)) # 输出：[12, 5, 6, 13]
总结
本题利用滑动窗口减少计算量，结合循环数组的特性，完成了高效的解密逻辑。通过将 k > 0 和 k < 0 的情况统一到一个逻辑中，代码实现更为简洁，并成功省略了 k = 0 的特判。
