Easy

题目描述

在一个 n × n 的矩阵网格中有一条蛇，可以向四个方向移动。网格中的每个单元格都由位置标识：grid[i][j] = (i * n) + j。

蛇从单元格 0 开始，并按照一系列命令移动。

给定一个整数 n 表示网格的大小，以及一个字符串数组 commands，其中每个 command[i] 都是 “UP”、“RIGHT”、“DOWN” 或 “LEFT” 之一。保证蛇在移动过程中始终保持在网格边界内。

返回蛇在执行完所有命令后最终停留的单元格位置。

示例 1：

输入：n = 2, commands = ["RIGHT","DOWN"]
输出：3
解释：
0 1
2 3

0 1
2 3

0 1
2 3

示例 2：

输入：n = 3, commands = ["DOWN","RIGHT","UP"]
输出：1
解释：
0 1 2
3 4 5
6 7 8

0 1 2
3 4 5
6 7 8

0 1 2
3 4 5
6 7 8

0 1 2
3 4 5
6 7 8

约束条件：

  • 2 <= n <= 10
  • 1 <= commands.length <= 100
  • commands 仅包含 “UP”、“RIGHT”、“DOWN” 和 “LEFT”
  • 输入保证蛇不会移动到边界外

提示：

  • 尝试在每次命令后更新蛇的行和列位置。

解题思路

这是一道经典的模拟题，需要我们追踪蛇在矩阵中的移动路径。

核心思路：

由于矩阵中每个位置的编号规律是 position = row × n + col，我们可以用两种方法来解决：

方法一：坐标模拟

  • 维护蛇的当前坐标 (row, col)
  • 根据命令更新坐标：UP减少行，DOWN增加行，LEFT减少列，RIGHT增加列
  • 最后根据公式计算最终位置编号

方法二：直接位置计算

  • 直接对位置编号进行操作
  • UP: position -= n, DOWN: position += n, LEFT: position -= 1, RIGHT: position += 1

两种方法时间复杂度相同，但方法一更直观易懂，方法二更简洁。这里我们采用方法一作为主要解法，因为它更符合题目提示的思路，同时代码可读性更好。

由于题目保证蛇不会越界，我们无需进行边界检查，只需按命令移动即可。

代码实现

class Solution {
public:
    int finalPositionOfSnake(int n, vector<string>& commands) {
        int row = 0, col = 0;
        
        for (const string& command : commands) {
            if (command == "UP") {
                row--;
            } else if (command == "DOWN") {
                row++;
            } else if (command == "LEFT") {
                col--;
            } else if (command == "RIGHT") {
                col++;
            }
        }
        
        return row * n + col;
    }
};

class Solution:
    def finalPositionOfSnake(self, n: int, commands: List[str]) -> int:
        row, col = 0, 0
        
        for command in commands:
            if command == "UP":
                row -= 1
            elif command == "DOWN":
                row += 1
            elif command == "LEFT":
                col -= 1
            elif command == "RIGHT":
                col += 1
        
        return row * n + col

public class Solution {
    public int FinalPositionOfSnake(int n, IList<string> commands) {
        int row = 0, col = 0;
        
        foreach (string command in commands) {
            if (command == "UP") {
                row--;
            } else if (command == "DOWN") {
                row++;
            } else if (command == "LEFT") {
                col--;
            } else if (command == "RIGHT") {
                col++;
            }
        }
        
        return row * n + col;
    }
}

/**
 * @param {number} n
 * @param {string[]} commands
 * @return {number}
 */
var finalPositionOfSnake = function(n, commands) {
    let row = 0, col = 0;
    
    for (let command of commands) {
        if (command === "UP") row--;
        else if (command === "DOWN") row++;
        else if (command === "LEFT") col--;
        else if (command === "RIGHT") col++;
    }
    
    return row * n + col;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(m)，其中 m 是命令数组的长度，需要遍历所有命令
空间复杂度O(1)，只使用常数额外空间存储坐标变量