Topic description

This is on LeetCode 1652. Defuse the Bomb , the difficulty is easy.

Tag : "simulation", "prefix sum"

You have a bomb to defuse and time is running out! Your agent will give you a circular array code of length n and a key k.

To get the correct password, you need to replace every number. All numbers will be replaced at the same time.

• If $k > 0$, replace the ith number with the sum of the next k numbers.
• If $k < 0$, replace the ith digit with the sum of the previous k digits.
• If $k = 0$, replace the i-th digit with 0.

Since code is cyclic, the next element of code[n-1] is code[0] and the previous element of code[0] is code[n-1] .

Given the loop array code and integer key k, please return the decrypted result to defuse the bomb!

Example 1:

enter: code = [5,7,1,4], k = 3

output:[12,10,16,13]

Explanation: Each number is replaced by the sum of the next 3 numbers. The decrypted password is [7+1+4, 1+4+5, 4+5+7, 5+7+1]. Notice that the arrays are concatenated circularly.

Example 2:

enter: code = [1,2,3,4], k = 0

output:[0,0,0,0]

Explanation: when k When 0, all numbers are replaced by 0.

Example 3:

enter: code = [2,4,9,3], k = -2

output:[12,5,6,13]

Explanation: The decrypted password is [3+9, 2+3, 4+2, 9+4] . Notice that the arrays are concatenated circularly. if k is negative, then the sum is the number before .

hint:

• $n = code.length$
• $1 <= n <= 100$
• $1 <= code[i] <= 100$
• $-(n - 1) <= k <= n - 1$

prefix sum

According to the meaning of the question code is a circular array, we can build a prefix sum array of length $2 \times n$ (for convenience, we make the prefix and array subscripts start from $1$), and use the prefix sum array to construct the answer.

For each $ans[i - 1]$where $i$ranges from $[1, n]$, we determine Which paragraph is taken from the prefix and array based on the positive and negative k values:

• If there is $k < 0$: you need to take the number of $-k$before the position $i$to prevent the lower crossing mark, first move the position $i$backwards by $n$offsets (i.e., position $i + n$), then you know the corresponding interval $[i + n + k, i + n - 1]$, corresponding interval and $sum[i + n - 1] - sum[i + n + k - 1]$
• If there is $k > 0$: the number of $k$after the position $i$is required, corresponding to the prefix and array subscript $[i + 1, i + k]$, corresponding to the interval sum of $sum[i + k] - sum[i]$

Java code:

class Solution {
    public int[] decrypt(int[] code, int k) {
        int n = code.length;
        int[] ans = new int[n];
        if (k == 0) return ans;
        int[] sum = new int[n * 2 + 10];
        for (int i = 1; i <= 2 * n; i++) sum[i] += sum[i - 1] + code[(i - 1) % n];
        for (int i = 1; i <= n; i++) {
            if (k < 0) ans[i - 1] = sum[i + n - 1] - sum[i + n + k - 1];
            else ans[i - 1] = sum[i + k] - sum[i];
        }
        return ans;
    }
}

TypeScript code:

function decrypt(code: number[], k: number): number[] {
    const n = code.length
    const ans = new Array<number>(n).fill(0)
    if (k == 0) return ans
    const sum = new Array<number>(2 * n + 10).fill(0)
    for (let i = 1; i <= 2 * n; i++) sum[i] = sum[i - 1] + code[(i - 1) % n]
    for (let i = 1; i <= n; i++) {
        if (k < 0) ans[i - 1] = sum[i + n - 1] - sum[i + n + k - 1]
        else ans[i - 1] = sum[i + k] - sum[i]
    }
    return ans
};

Python code:

class Solution:
    def decrypt(self, code: List[int], k: int) -> List[int]:
        n = len(code)
        ans = [0] * n
        if k == 0:
            return ans
        sum = [0] * (2 * n + 10)
        for i in range(1, 2 * n + 1):
            sum[i] = sum[i - 1] + code[(i - 1) % n]
        for i in range(1, n + 1):
            if k < 0:
                ans[i - 1] = sum[i + n - 1] - sum[i + n + k - 1]
            else:
                ans[i - 1] = sum[i + k] - sum[i]
        return ans

• Time complexity: $O(n)$
• Space complexity: $O(n)$

at last

This is No.1652 of our "Brush through LeetCode" series, starting in 2021/01/01. There are 1916 titles on LeetCode as of the start date, some of which are all lock titles. We will start with all Finished the topics with the lock.

In this series of articles, in addition to explaining the problem-solving ideas, the most concise code will be given as much as possible. If general solutions are involved, corresponding code templates will also be provided.

In order to facilitate students to debug and submit code on the computer, I have established relevant warehouses: https://github.com/SharingSou... .

In the warehouse address, you can see the link to the solution of the series of articles, the corresponding code of the series of articles, the link to the original question of LeetCode and other preferred solutions.

For more, more comprehensive and more popular "Written Test/Interview" related information, please visit the beautifully typed Collection new base 🎉🎉

This article is by mdnice Multi-platform release