题目地址:https://leetcode-cn.com/problems/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,请你返回解密后的结果来拆除炸弹! https://leetcode-cn.com/problems/defuse-the-bomb/
示例 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 是负数,那么和为 之前 的数字。 https://leetcode-cn.com/problems/defuse-the-bomb/
提示:
n == code.length
1 <= n<= 100
1 <= code[i] <= 100
-(n - 1) <= k <= n - 1
理解:
k如果是正数就返回接下来n个数的和,如果是负数就返回之前n个数的和,如果是0,则返回0;
其实这道题是把数组当成一个循环队列来看的。
我们的思维是,需要把和k和当前下标做运算的结果模一个数组length以达到循环队列的效果。
一、爆破法
爆破法的思路很简单,我们新建一个数组,用来存储计算和返回结果。
然后计算之前对k进行分类(这里想到其实可以做一个正负数复用的代码段,但是数学功底一般没法总结出这么一个公式)
k是0则直接返回0,k是正数则从当前坐标+1 一直到当前坐标+k,当然为了用成循环队列,所以我们会%length
相反如果k是负数,那么就是从当前坐标+k 一直到当前目标+(-1)。
执行结果如下:
74 / 74 个通过测试用例
状态:通过
执行用时: 2 ms
内存消耗: 38.6 MB
public static int[] decryptMe(int[] code, int k) {
int[] ans = new int[code.length];
if (k > 0) {
for (int i = 0; i < code.length; i++) {
for (int j = 1; j <= k; j++) {
ans[i] += code[(i + j) % code.length];
}
}
} else {
for (int i = 0; i < code.length; i++) {
for (int j = k; j < 0; j++) {
ans[i] += code[(i + j + code.length) % code.length];
}
}
}
return ans;
}
二、评论区大佬法
评论区大佬用的方法是0ms,我们来看看他是怎么做的。(内存考前的答案的貌似没多少)
上来也是创建一个返回数组如果k=0直接返回
先做了个数据处理
k>0时1~length-1的元素都要加上他自己前一个元素的值
k<0时0~length-2的元素都要加上他后一个元素的值
然后根据k的正负值取不同的结果
执行结果如下:
74 / 74 个通过测试用例
状态:通过
执行用时: 0 ms
内存消耗: 38.6 MB
public int[] decrypt0ms(int[] a, int k) {
int[] ans=new int[a.length];
if(k==0)return ans;
if(k>0)for(int i=1;i<a.length;i++)a[i]+=a[i-1];
else for(int i=a.length-2;i>=0;i--)a[i]+=a[i+1];
if(k>0){
for(int i=0;i<a.length;i++){
ans[i]=(i+k<a.length?a[i+k]:a[a.length-1]+a[i+k-a.length])-a[i];
}
}else{
for(int i=0;i<a.length;i++){
ans[i]=(i+k<0?a[0]+a[i+k+a.length]:a[i+k])-a[i];
}
}
return ans;
}
说实话大佬的做法我还是没有想明白,可能是因为数学太差了。留给后面的自己吧哈哈哈哈,毕竟这只是一道easy,结果差不太多的情况下不需要太过深究。