3522. 执行指令后的得分 

English Version

题目描述

给你两个数组：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}$ 的长度。

Python3

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

Java

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;
    }
}

C++

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;
    }
};

Go

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
}

TypeScript

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;
}