Medium

题目描述

有一个 n x n 的网格，左上角的单元格为 (0, 0)，右下角的单元格为 (n - 1, n - 1)。给你整数 n 和一个整数数组 startPos，其中 startPos = [startrow, startcol] 表示机器人最初位于单元格 (startrow, startcol) 上。

另给你一个长度为 m 的字符串 s，其中 s[i] 是对机器人的第 i 条指令：'L'（向左移动），'R'（向右移动），'U'（向上移动）和 'D'（向下移动）。

机器人可以从 s 中的任一第 i 条指令开始执行。它将会逐条执行指令直到 s 的末尾，但在满足下述条件之一时，机器人将会停止：

  • 下一条指令将会导致机器人移动到网格外。
  • 没有指令可以执行。

返回一个长度为 m 的数组 answer，其中 answer[i] 是机器人从第 i 条指令开始执行可以执行的指令数目。

示例 1：

输入：n = 3, startPos = [0,1], s = "RRDDLU"
输出：[1,5,4,3,1,0]
解释：机器人从 startPos 开始，并从第 i 条指令开始执行：
- 第 0 条："RRDDLU"，只能执行一条指令 "R"，然后它将移动到网格外。
- 第 1 条："RDDLU"，可以执行全部五条指令，机器人仍在网格内，最终到达 (1, 1)。
- 第 2 条："DDLU"，可以执行全部四条指令，机器人仍在网格内，最终到达 (1, 0)。
- 第 3 条："DLU"，可以执行全部三条指令，机器人仍在网格内，最终到达 (0, 0)。
- 第 4 条："LU"，只能执行一条指令 "L"，然后它将移动到网格外。
- 第 5 条："U"，如果向上移动，它将移动到网格外。

示例 2：

输入：n = 2, startPos = [1,1], s = "LURD"
输出：[4,1,0,0]

示例 3：

输入：n = 1, startPos = [0,0], s = "LRUD"
输出：[0,0,0,0]
解释：无论机器人从哪条指令开始执行，都会移动到网格外。

提示：

  • m == s.length
  • 1 <= n, m <= 500
  • startPos.length == 2
  • 0 <= startrow, startcol < n
  • s 由 'L'、'R'、'U' 和 'D' 组成

解题思路

这道题需要模拟机器人从每个位置开始执行指令的过程。

思路分析：

对于每个起始指令位置 i，我们需要模拟机器人从当前位置开始，按顺序执行指令 s[i], s[i+1], ..., s[m-1]，直到遇到以下情况之一：

  1. 下一步会移出网格边界
  2. 所有指令都执行完毕

具体步骤：

  1. 遍历每个可能的起始指令位置 i（从 0 到 m-1）
  2. 对于每个起始位置，重置机器人位置为 startPos
  3. 从位置 i 开始逐个执行指令：
    • 根据指令字符计算下一个位置
    • 检查新位置是否在网格内
    • 如果在网格内，更新位置并继续；否则停止执行
  4. 记录成功执行的指令数量

方向映射：

  • ‘L’: 列坐标减1
  • ‘R’: 列坐标加1
  • ‘U’: 行坐标减1
  • ‘D’: 行坐标加1

时间复杂度为 O(m²)，其中 m 是指令字符串长度。虽然看起来不是最优，但考虑到约束条件（m ≤ 500），这种暴力模拟方法完全可行且易于理解。

代码实现

class Solution {
public:
    vector<int> executeInstructions(int n, vector<int>& startPos, string s) {
        int m = s.length();
        vector<int> result(m);
        
        for (int i = 0; i < m; i++) {
            int row = startPos[0];
            int col = startPos[1];
            int count = 0;
            
            for (int j = i; j < m; j++) {
                // 根据指令计算新位置
                int newRow = row, newCol = col;
                if (s[j] == 'L') newCol--;
                else if (s[j] == 'R') newCol++;
                else if (s[j] == 'U') newRow--;
                else if (s[j] == 'D') newRow++;
                
                // 检查新位置是否在网格内
                if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n) {
                    row = newRow;
                    col = newCol;
                    count++;
                } else {
                    break;
                }
            }
            
            result[i] = count;
        }
        
        return result;
    }
};

class Solution:
    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:
        m = len(s)
        result = []
        
        for i in range(m):
            row, col = startPos[0], startPos[1]
            count = 0
            
            for j in range(i, m):
                # 根据指令计算新位置
                if s[j] == 'L':
                    new_col = col - 1
                    new_row = row
                elif s[j] == 'R':
                    new_col = col + 1
                    new_row = row
                elif s[j] == 'U':
                    new_row = row - 1
                    new_col = col
                else:  # s[j] == 'D'
                    new_row = row + 1
                    new_col = col
                
                # 检查新位置是否在网格内
                if 0 <= new_row < n and 0 <= new_col < n:
                    row, col = new_row, new_col
                    count += 1
                else:
                    break
            
            result.append(count)
        
        return result

public class Solution {
    public int[] ExecuteInstructions(int n, int[] startPos, string s) {
        int m = s.Length;
        int[] result = new int[m];
        
        for (int i = 0; i < m; i++) {
            int row = startPos[0];
            int col = startPos[1];
            int count = 0;
            
            for (int j = i; j < m; j++) {
                // 根据指令计算新位置
                int newRow = row, newCol = col;
                switch (s[j]) {
                    case 'L': newCol--; break;
                    case 'R': newCol++; break;
                    case 'U': newRow--; break;
                    case 'D': newRow++; break;
                }
                
                // 检查新位置是否在网格内
                if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n) {
                    row = newRow;
                    col = newCol;
                    count++;
                } else {
                    break;
                }
            }
            
            result[i] = count;
        }
        
        return result;
    }
}

/**
 * @param {number} n
 * @param {number[]} startPos
 * @param {string} s
 * @return {number[]}
 */
var executeInstructions = function(n, startPos, s) {
    const result = [];
    
    for (let i = 0; i < s.length; i++) {
        let row = startPos[0];
        let col = startPos[1];
        let count = 0;
        
        for (let j = i; j < s.length; j++) {
            const instruction = s[j];
            
            if (instruction === 'L') {
                col--;
            } else if (instruction === 'R') {
                col++;
            } else if (instruction === 'U') {
                row--;
            } else if (instruction === 'D') {
                row++;
            }
            
            if (row < 0 || row >= n || col < 0 || col >= n) {
                break;
            }
            
            count++;
        }
        
        result.push(count);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m²)外层循环遍历m个起始位置，内层循环最多执行m条指令
空间复杂度O(1)除了结果数组外，只使用常数级额外空间

相关题目