简单枚举 - 1652. 拆炸弹

Problem: 1652. 拆炸弹

思路

分k > 0、k < 0和k == 0三种方法进行讨论

解题过程

把code复制一遍，然后拼接在code自己上

k > 0

1. for i, 0 -> n - 1一遍，枚举前面每个元素（后面会越界）

2. 创建一个整数sum，表示接下来k个数字之和

3. for j, 1 -> k一遍，将code[i + j]累计在sum上

4. 将sum添加到ans里

k < 0

1. for i, n -> n * 2一遍，枚举后面每个元素（前面会越界）

2. 创建一个整数sum，表示之前k个数字之和

3. for j, k -> 0一遍，将code[i + j]累计在sum上

4. 将sum添加到ans里

k == 0

1. for i, 0 -> n - 1一遍，枚举每个元素（for i, n -> n * 2也行）

2. 将0添加到ans里

复杂度

• 时间复杂度: $O(NK)$$O(NK)$，其中$N$$N$是code的长度 因为在for i, 0 -> n - 1里嵌套了一层for j, 1 -> k或在for i, n, n + 1里嵌套了一层for j, k -> 0

• 空间复杂度: $O(N)$$O(N)$，其中$N$$N$是code的长度 因为整个ans用了$N$$N$的空间

Code

C++

xxxxxxxxxx
class Solution {
public:
    vector<int> decrypt(vector<int>& code, int k) {
        int n = code.size();
        code.insert(code.end(), code.begin(), code.end());
        vector<int> ans;
        if (k > 0) {
            for (int i = 0; i < n; i++) {
                int sum = 0;
                for (int j = 1; j <= k; j++) {
                    sum += code[i + j];
                }
                ans.push_back(sum);
            }
        } else if (k < 0) {
            for (int i = n; i < 2 * n; i++) {
                int sum = 0;
                for (int j = k; j < 0; j++) {
                    sum += code[i + j];
                }
                ans.push_back(sum);
            }
        } else {
            for (int i = 0; i < n; i++) {
                ans.push_back(0);
            }
        }
        return ans;
    }
};

Python

xxxxxxxxxx
class Solution:
    def decrypt(self, code: List[int], k: int) -> List[int]:
        n = len(code)
        code.extend(code)
        ans = []
        if k > 0:
            for i in range(n):
                _sum = 0
                for j in range(1, k + 1):
                    _sum += code[i + j]
                ans.append(_sum)
        elif k < 0:
            for i in range(n, 2 * n):
                _sum = 0
                for j in range(k, 0):
                    _sum += code[i + j]
                ans.append(_sum)
        else:
            for i in range(n):
                ans.append(0)
        return ans

C#

xxxxxxxxxx
public class Solution {
    public int[] Decrypt(int[] code, int k) {
        int n = code.GetLength(0);
        int[] Code = new int[n * 2];
        for (int i = 0; i < n; i++) {
            Code[i] = code[i];
        }
        for (int i = n; i < 2 * n; i++) {
            Code[i] = code[i - n];
        }
        List<int> ans = new List<int>();
        if (k > 0) {
            for (int i = 0; i < n; i++) {
                int sum = 0;
                for (int j = 1; j <= k; j++) {
                    sum += Code[i + j];
                }
                ans.Add(sum);
            }
        } else if (k < 0) {
            for (int i = n; i < 2 * n; i++) {
                int sum = 0;
                for (int j = k; j < 0; j++) {
                    sum += Code[i + j];
                }
                ans.Add(sum);
            }
        } else {
            for (int i = 0; i < n; i++) {
                ans.Add(0);
            }
        }
        return ans.ToArray();
    }
}