2025-10-09：执行指令后的得分。用go语言，输入两个长度相同的数组：instructions（每项为 "add" 或 "

福大大架构师每日一题

发布于 2025-12-18 13:59:36

630

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2025-10-09：执行指令后的得分。用go语言，输入两个长度相同的数组：instructions（每项为 "add" 或 "jump"）和 values。

按下面的规则模拟执行并返回结束时的得分：

• 初始位置 i = 0，得分 score = 0。
• 若当前指令为 "add"：把 values[i] 累加到 score，然后将 i 增加 1，执行下一条指令。
• 若当前指令为 "jump"：不改变 score，直接把 i 改为 i + values[i]。（即跳转到该索引处继续执行）
• 当索引越界（i < 0 或 i >= n）或将要执行的指令已经在之前被执行过时，停止模拟（注意：重复访问的指令不再被执行）。

最终返回停止时的 score。

n == instructions.length == values.length。

1 <= n <= 100000。

instructions[i] 只能是 "add" 或 "jump"。

-100000 <= values[i] <= 100000。

输入： 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：已经访问过。过程结束。

题目来自力扣3522。

执行过程详细描述

初始状态：

• 指令数组：["jump", "add", "add", "jump", "add", "jump"]
• 值数组：[2, 1, 3, 1, -2, -3]
• 当前位置：i = 0
• 当前得分：score = 0
• 访问标记：所有指令都未访问过

执行步骤：

第1步：位置0

• 指令："jump"（未访问过）
• 标记位置0为已访问
• 执行跳转：i = 0 + 2 = 2
• 得分保持为0

第2步：位置2

• 指令："add"（未访问过）
• 标记位置2为已访问
• 执行加法：score = 0 + 3 = 3
• 移动到下一条指令：i = 2 + 1 = 3

第3步：位置3

• 指令："jump"（未访问过）
• 标记位置3为已访问
• 执行跳转：i = 3 + 1 = 4
• 得分保持为3

第4步：位置4

• 指令："add"（未访问过）
• 标记位置4为已访问
• 执行加法：score = 3 + (-2) = 1
• 移动到下一条指令：i = 4 + 1 = 5

第5步：位置5

• 指令："jump"（未访问过）
• 标记位置5为已访问
• 执行跳转：i = 5 + (-3) = 2
• 得分保持为1

第6步：位置2

• 发现位置2的指令已经被标记为访问过
• 停止模拟

最终结果：

• 最终得分：1

复杂度分析

时间复杂度：O(n)

• 每个指令最多被执行一次（一旦访问就会被标记）
• 最坏情况下需要遍历所有n个指令
• 每次操作都是常数时间

额外空间复杂度：O(1)

• 算法在原地修改instructions数组来标记访问状态
• 只使用了有限的几个变量（i, ans, n等）
• 没有使用额外的数据结构来存储访问状态

关键点： 通过将已执行的指令设为空字符串来标记访问状态，既避免了重复执行，又不需要额外的空间来记录访问历史，这是该算法设计的巧妙之处。

Go完整代码如下：

package main

import (
    "fmt"
)

func calculateScore(instructions []string, values []int) (ans int64) {
    n := len(instructions)
    i := 0
    for0 <= i && i < n && instructions[i] != "" {
        s := instructions[i]
        instructions[i] = ""
        if s[0] == 'a' {
            ans += int64(values[i])
            i++
        } else {
            i += values[i]
        }
    }
    return
}

func main() {
    instructions := []string{"jump", "add", "add", "jump", "add", "jump"}
    values := []int{2, 1, 3, 1, -2, -3}
    result := calculateScore(instructions, values)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def calculate_score(instructions, values):
    n = len(instructions)
    i = 0
    ans = 0
    
    while 0 <= i < n and instructions[i] != "":
        s = instructions[i]
        instructions[i] = ""  # 标记为已访问
        if s[0] == 'a':  # 如果是 "add" 指令
            ans += values[i]
            i += 1
        else:  # 如果是 "jump" 指令
            i += values[i]
    
    return ans

def main():
    instructions = ["jump", "add", "add", "jump", "add", "jump"]
    values = [2, 1, 3, 1, -2, -3]
    result = calculate_score(instructions, values)
    print(result)

if __name__ == "__main__":
    main()