【2022-09-24每日一题】1652. 拆炸弹[Easy]
2022-09-24
3分钟阅读时长
2022-09-24每日一题：1652. 拆炸弹
难度：Easy
标签：数组
你有一个炸弹需要拆除，时间紧迫！你的情报员会给你一个长度为 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 是负数，那么和为 之前 的数字。
提示：
n == code.length1 <= n <= 1001 <= code[i] <= 100-(n - 1) <= k <= n - 1
方法一：直接暴力模拟
// 写法一
func decrypt(code []int, k int) []int {
n := len(code)
ans := make([]int, n)
if k == 0 {
return ans
}
for i := 0; i < n; i++ {
sum := 0
if k > 0 {
for j := 1; j <= k; j++ {
sum += code[(i+j)%n]
}
} else {
for j := 1; j <= -k; j++ {
sum += code[(i-j+n)%n]
}
}
ans[i] = sum
}
return ans
}
// 写法二
func decrypt(code []int, k int) []int {
n := len(code)
ans := make([]int, n)
if k == 0 {
return ans
}
for i := 0; i < n; i++ {
if k > 0 {
for j := i + 1; j < i+k+1; j++ {
ans[i] += code[j%n]
}
} else {
for j := i + k; j < i; j++ {
ans[i] += code[(j+n)%n]
}
}
}
return ans
}
复杂度分析
- 时间复杂度O(n×∣k∣)。
- 忽略答案的空间消耗，空间复杂度 O(1)。
方法二：
详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读
func decrypt(code []int, k int) []int {
n := len(code)
ans := make([]int, n)
if k == 0 {
return ans
}
code = append(code, code...)
// 定位0号编码，左右开始位置
l, r := 1, k
if k < 0 {
l, r = n+k, n-1
}
sum := 0
for _, v := range code[l:r+1] {
sum += v
}
for i := range ans {
ans[i] = sum
// 计算下一个数字
sum -= code[l]
sum += code[r+1]
l, r = l+1, r+1
}
return ans
}
复杂度分析
- 时间复杂度：O(n)，其中 n 为数组 code 的长度。
- 空间复杂度：O(n)，其中 n 为数组 code 的长度，主要为数组拼接后的空间开销，也可以通过取模映射操作来将空间复杂度降到 O(1)。
方法三：前缀和优化
若 k 为正数，ans[i]=s[i+k+1]−s[i+1]。
若 k 为负数，ans[i]=s[i+n]−s[i+k+n]。
func decrypt(code []int, k int) []int {
n := len(code)
ans := make([]int, n)
if k == 0 {
return ans
}
sum := make([]int, n<<1|1)
for i := 0; i < n<<1; i++ {
sum[i+1] = sum[i] + code[i%n]
}
for i := range code {
if k > 0 {
ans[i] = sum[i+k+1] - sum[i+1]
} else {
ans[i] = sum[i+n] - sum[i+k+n]
}
}
return ans
}
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(n)