LeetCode 1652: 拆炸弹 (Defuse the Bomb)超详细解释

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.length
• 1 <= n <= 100
• 1 <= 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 List

class Solution:
    def decrypt(self, code: List[int], k: int) -> List[int]:
        n = len(code)
        r = k + 1 if k > 0 else n  # 初始窗口右边界
        ans = [0] * n
        k = 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 的特判。

原文地址：https://blog.csdn.net/qq_17405059/article/details/143887777

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！