LeetCode - 1652 拆炸弹

目录

题目详情

输入输出

题目解析

算法源码

题目来源

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]开始的

算法源码

var decrypt = function(code, k) {
	let newArr = code.slice().fill(0)
	let K = Math.abs(k)
	let sum = code.reduce((pre, cur)=>{return pre+cur}, 0)
	
	let base = 0
	if(K > code.length) {
		base = Math.floor(K / code.length) * sum
	}
	
	let x = k > 0 ? 1 : -1;
	for(let i=0; i<code.length; i++) {
		for(let j=1; j<=K % code.length; j++) {
			newArr[i] += getK(code, i+x*j)
		}
		newArr[i] += base
	}
	
	return newArr
}

function getK(code, k){
	if(k >= 0 && k < code.length) {
		return code[k]
	} else if (k >= code.length) {
		return code[k % code.length]
	} else {
		return code[k % code.length + code.length]
	}
}

//console.log(decrypt([5,7,1,4],3))
//console.log(decrypt([1,2,3,4],0))
//console.log(decrypt([2,4,9,3],-10))