What is the main strategy for Calculate Score After Performing Instructions?

Simulate instructions sequentially while tracking values with a hash table to efficiently compute the final score.

Can jumps move the pointer outside the array?

Yes, the process ends immediately if a jump causes the pointer to go out of bounds.

How do I handle repeated instruction sequences?

Use a hash table to store previously computed results for identical sequences to avoid recalculation.

Are negative values allowed in the instructions array?

Yes, negative values can occur and must be handled correctly for both add and jump operations.

Why is array scanning plus hash lookup crucial here?

Because it allows fast traversal of instructions while quickly accessing prior results to maintain efficiency on large inputs.

#3522

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

执行指令后的得分

给你两个数组： instructions 和 values ，数组的长度均为 n 。你需要根据以下规则模拟一个过程：从下标 i = 0 的第一个指令开始，初始得分为 0。如果 instructions[i] 是 "add" ：将 values[i] 加到你的得分中。移动到下一个指令 (i …

数组哈希表字符串模拟

题目描述

给你两个数组：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⁵

lightbulb

解题思路

方法一：模拟

我们根据题意模拟即可。

我们定义一个长度为 $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}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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

speed

复杂度分析

指标	值
时间	complexity is O(n) for scanning all instructions with O(1) hash lookups per operation. Space complexity is O(n) due to storing positions or values in the hash table for fast access.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Focus on array scanning combined with hash table lookups.
question_mark
Check edge conditions for jumps going out of array bounds.
question_mark
Look for opportunities to reuse computed values for repeated sequences.

warning

常见陷阱

外企场景

error
Failing to check array bounds after a jump, leading to runtime errors.
error
Overwriting or ignoring previous hash entries, causing incorrect scores.
error
Confusing the order of add and jump operations when updating score.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Instructions could include multiply operations requiring dynamic score adjustments.
arrow_right_alt
Allow variable-length jumps based on previous scores, increasing simulation complexity.
arrow_right_alt
Use nested instruction sequences, requiring multi-level hash tracking for correctness.

help

常见问题

外企场景

继续练习

#2744 最大字符串配对数目 #3527 找到最常见的回答 #3510 移除最小数对使数组有序 II