LeetCode - 1652 拆炸弹

客官°小女子只卖身不卖艺 2023-09-26 09:12 97阅读 0赞

**目录**

题目详情

输入输出

题目解析

算法源码

--------------------

### 题目来源 ###

[1652. 拆炸弹 - 力扣（LeetCode）][1652. _ - _LeetCode]

### 题目详情 ###

你有一个炸弹需要拆除，时间紧迫！你的情报员会给你一个长度为 `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 ，请你返回解密后的结果来拆除炸弹！

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

### 输入输出 ###

示例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 是负数，那么和为 之前 的数字。

### 题目解析 ###

这道题来源于leetcode，因此算法不需要考虑输入输出的逻辑，比牛客方便一点，只要直接使用固定名称的函数即可。

然后就是算法思考，我觉得有两个难点：

1、数组是有越界限制的，而循环数组没有越界限制，因此循环数组取索引小于0和大于arr.length-1的元素是OK的，因此我们需要考虑如何获取循环数组的“越界”元素值，我这边定义了一个getK方法来获取循环数组的值。

2、“循环遍历出数组的每一个元素，比如遍历出第i个元素，则第i个元素的值需要被替换为该元素后面的k个元素的和”。-----这个逻辑其实还算比较简单，硬算也不是不可以，并且leetcode原题目中限定了k的范围在0到99之间，因此硬算也不会引起太大的性能问题。可能这就是这题被划为简单题的原因吧。

我这里的算法设计还是考虑进了k值较大的情况，

比如code=\[1,2,3,4\]，k=1000，此时

code\[0\]将会被替换为：2 + 3 + 4+（1+2+3+4）\* 249 \+ 1 = **（1+2+3+4）\*250**，

code\[1\]将会被替换为：3 + 4 +（1+2+3+4）\* 249 \+ 1 + 2 = **（1+2+3+4）\*250**，

code\[2\]将会被替换为：4 +（1+2+3+4）\* 249 \+ 1 + 2 + 3 = **（1+2+3+4）\*250**，

code\[3\]将会被替换为：（1+2+3+4）\* 249 \+ 1 + 2 + 3 + 4 = **（1+2+3+4）\*250**，

也就是说，如果k是code.length的整数倍，则code数组每一个元素都会被替换为相同值，即sum(code) \* (k/code.length)

如果k=1001，则

code\[0\]会被替换为2+3+4+（1+2+3+4）\* 249 \+ 1+2 = （**1+2+3+4）\* 250 + 2**

如果k=1002，则

code\[0\]会被替换为2+3+4+（1+2+3+4）\* 249 \+ 1+2+3 = （**1+2+3+4）\* 250 + 2 + 3**

如果k=1003，则

code\[0\]会被替换为2+3+4+（1+2+3+4）\* 249 \+ 1+2+3 + 4 = （**1+2+3+4）\* 250 + 2 + 3 + 4**

也就是说，如果 k 不是code.length的整数倍，则多出来的k%code.length个数，就是从code\[i+1\]开始的

### 算法源码 ###

[1652. _ - _LeetCode]: https://leetcode.cn/problems/defuse-the-bomb/

LeetCode - 1652 拆炸弹

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 LeetCode-343. 整数拆分

相关 leetcode 139. 单词拆分

相关洛谷——P1652 圆

相关 LeetCode - 1652 拆炸弹

相关数字炸弹游戏

相关 leetcode 343 整数拆分

相关 leetcode 139 单词拆分

相关二进制炸弹实验binarybomb 拆弹

相关【LeetCode】- 139 - 单词拆分

相关 linux fork炸弹