3522. 执行指令后的得分

题目描述

给你两个数组：instructions 和 values，数组的长度均为 n。

你需要根据以下规则模拟一个过程：

从下标 i = 0 的第一个指令开始，初始得分为 0。
如果 instructions[i] 是 "add"：
- 将 values[i] 加到你的得分中。
- 移动到下一个指令 (i + 1)。
如果 instructions[i] 是 "jump"：
- 移动到下标为 (i + values[i]) 的指令，但不修改你的得分。

当以下任一情况发生时，过程会终止：

越界（即 i < 0 或 i >= n），或
尝试再次执行已经执行过的指令。被重复访问的指令不会再次执行。

返回过程结束时的得分。

示例 1：

输入： instructions = ["jump","add","add","jump","add","jump"], values = [2,1,3,1,-2,-3]

输出： 1

解释：

从下标 0 开始模拟过程：

下标 0：指令是 "jump"，移动到下标 0 + 2 = 2。
下标 2：指令是 "add"，将 values[2] = 3 加到得分中，移动到下标 3。得分变为 3。
下标 3：指令是 "jump"，移动到下标 3 + 1 = 4。
下标 4：指令是 "add"，将 values[4] = -2 加到得分中，移动到下标 5。得分变为 1。
下标 5：指令是 "jump"，移动到下标 5 + (-3) = 2。
下标 2：已经访问过。过程结束。

示例 2：

输入： instructions = ["jump","add","add"], values = [3,1,1]

输出： 0

解释：

从下标 0 开始模拟过程：

下标 0：指令是 "jump"，移动到下标 0 + 3 = 3。
下标 3：越界。过程结束。

示例 3：

输入： instructions = ["jump"], values = [0]

输出： 0

解释：

从下标 0 开始模拟过程：

下标 0：指令是 "jump"，移动到下标 0 + 0 = 0。
下标 0：已经访问过。过程结束。

提示：

n == instructions.length == values.length
1 <= n <= 10⁵
instructions[i] 只能是 "add" 或 "jump"。
-10⁵ <= values[i] <= 10⁵

解法

方法一：模拟

我们根据题意模拟即可。

我们定义一个长度为 \(n\) 的布尔数组 \(\textit{vis}\)，用于记录每一条指令是否被执行过，初始时均为 \(\text{false}\)。

然后我们从下标 \(i = 0\) 开始，循环执行以下操作：

将 \(\textit{vis}[i]\) 置为 \(\text{true}\)；
如果 \(\textit{instructions}[i]\) 的第一个字符为 'a'，那么我们将答案增加 \(\textit{value}[i]\)，然后 \(i\) 加 \(1\)；否则，我们将 \(i\) 增加 \(\textit{value}[i]\)。

循环，直至 \(i \lt 0\) 或者 \(i \ge n\)，或者 \(\textit{vis}[i]\) 为 \(\text{true}\)。

最后返回答案即可。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是数组 \(\textit{value}\) 的长度。

Python3JavaC++GoTypeScript

class Solution:
    def calculateScore(self, instructions: List[str], values: List[int]) -> int:
        n = len(values)
        vis = [False] * n
        ans = i = 0
        while 0 <= i < n and not vis[i]:
            vis[i] = True
            if instructions[i][0] == "a":
                ans += values[i]
                i += 1
            else:
                i = i + values[i]
        return ans

class Solution {
    public long calculateScore(String[] instructions, int[] values) {
        int n = values.length;
        boolean[] vis = new boolean[n];
        long ans = 0;
        int i = 0;

        while (i >= 0 && i < n && !vis[i]) {
            vis[i] = true;
            if (instructions[i].charAt(0) == 'a') {
                ans += values[i];
                i += 1;
            } else {
                i = i + values[i];
            }
        }

        return ans;
    }
}

class Solution {
public:
    long long calculateScore(vector<string>& instructions, vector<int>& values) {
        int n = values.size();
        vector<bool> vis(n, false);
        long long ans = 0;
        int i = 0;

        while (i >= 0 && i < n && !vis[i]) {
            vis[i] = true;
            if (instructions[i][0] == 'a') {
                ans += values[i];
                i += 1;
            } else {
                i += values[i];
            }
        }

        return ans;
    }
};

func calculateScore(instructions []string, values []int) (ans int64) {
    n := len(values)
    vis := make([]bool, n)
    i := 0
    for i >= 0 && i < n && !vis[i] {
        vis[i] = true
        if instructions[i][0] == 'a' {
            ans += int64(values[i])
            i += 1
        } else {
            i += values[i]
        }
    }
    return
}

function calculateScore(instructions: string[], values: number[]): number {
    const n = values.length;
    const vis: boolean[] = Array(n).fill(false);
    let ans = 0;
    let i = 0;

    while (i >= 0 && i < n && !vis[i]) {
        vis[i] = true;
        if (instructions[i][0] === 'a') {
            ans += values[i];
            i += 1;
        } else {
            i += values[i];
        }
    }

    return ans;
}

3522. 执行指令后的得分

题目描述

解法

方法一：模拟

评论