Medium

题目描述

给你两个大小为 n 的数组，instructions 和 values。

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

  • 从索引 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^5
  • instructions[i] 是 "add" 或 "jump"
  • -10^5 <= values[i] <= 10^5

解题思路

这是一道典型的指令模拟题，需要按照给定规则逐步执行指令。

核心思路：

  1. 使用一个集合（或布尔数组）记录已访问过的指令索引，避免重复执行
  2. 从索引 0 开始，根据指令类型执行相应操作：
    • "add" 指令：将对应值加到分数上，索引递增1
    • "jump" 指令：将索引跳转到 i + values[i]，分数不变
  3. 继续执行直到满足终止条件：索引越界或访问已执行过的指令

算法步骤：

  1. 初始化分数为 0，当前索引为 0
  2. 创建访问记录集合
  3. 在循环中：
    • 检查当前索引是否越界或已访问过，如果是则退出
    • 将当前索引标记为已访问
    • 根据指令类型执行对应操作
    • 更新索引位置
  4. 返回最终分数

时间复杂度优化： 由于每个指令最多被访问一次，所以时间复杂度是 O(n)。使用哈希集合或布尔数组都可以实现 O(1) 的查找和插入操作。

这种模拟方法直观且高效，适合处理此类指令执行问题。

代码实现

class Solution {
public:
    long long calculateScore(vector<string>& instructions, vector<int>& values) {
        int n = instructions.size();
        long long score = 0;
        int i = 0;
        unordered_set<int> visited;
        
        while (i >= 0 && i < n && visited.find(i) == visited.end()) {
            visited.insert(i);
            
            if (instructions[i] == "add") {
                score += values[i];
                i++;
            } else { // "jump"
                i += values[i];
            }
        }
        
        return score;
    }
};

class Solution:
    def calculateScore(self, instructions: List[str], values: List[int]) -> int:
        n = len(instructions)
        score = 0
        i = 0
        visited = set()
        
        while 0 <= i < n and i not in visited:
            visited.add(i)
            
            if instructions[i] == "add":
                score += values[i]
                i += 1
            else:  # "jump"
                i += values[i]
        
        return score

public class Solution {
    public long CalculateScore(string[] instructions, int[] values) {
        int n = instructions.Length;
        long score = 0;
        int i = 0;
        HashSet<int> visited = new HashSet<int>();
        
        while (i >= 0 && i < n && !visited.Contains(i)) {
            visited.Add(i);
            
            if (instructions[i] == "add") {
                score += values[i];
                i++;
            } else { // "jump"
                i += values[i];
            }
        }
        
        return score;
    }
}

var calculateScore = function(instructions, values) {
    const n = instructions.length;
    let score = 0;
    let i = 0;
    const visited = new Set();
    
    while (i >= 0 && i < n && !visited.has(i)) {
        visited.add(i);
        
        if (instructions[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n) - 每个指令最多被访问一次
空间复杂度O(n) - 哈希集合最多存储 n 个索引