What is the key approach to solving Snake in Matrix?

The key approach is to simulate the snake's movement by updating the row and column position based on each command and then calculating the final position in the grid.

How do I handle boundary movements in the Snake in Matrix problem?

The problem guarantees that the snake will stay within the grid boundaries, so the focus should be on correctly updating the row and column for each command.

How does GhostInterview help with solving Snake in Matrix?

GhostInterview guides you in simulating the snake's movement efficiently, ensuring each command is processed correctly and edge cases are handled.

What is the time complexity of the Snake in Matrix problem?

The time complexity is O(m), where m is the number of commands, since each command requires constant time to process.

What should I focus on when solving Snake in Matrix?

Focus on simulating the movement of the snake and correctly updating its position based on the commands, ensuring the final position is accurately calculated.

#3248

Easy

auto_awesome数组·string

LeetCode 题解工作台

矩阵中的蛇

大小为 n x n 的矩阵 grid 中有一条蛇。蛇可以朝四个可能的方向移动。矩阵中的每个单元格都使用位置进行标识： grid[i][j] = (i * n) + j 。蛇从单元格 0 开始，并遵循一系列命令移动。给你一个整数 n 表示 grid 的大小，另给你一个字符串数组 command…

数组字符串模拟

题目描述

大小为 n x n 的矩阵 grid 中有一条蛇。蛇可以朝 四个可能的方向 移动。矩阵中的每个单元格都使用位置进行标识： grid[i][j] = (i * n) + j。

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

给你一个整数 n 表示 grid 的大小，另给你一个字符串数组 commands，其中包括 "UP"、"RIGHT"、"DOWN" 和 "LEFT"。题目测评数据保证蛇在整个移动过程中将始终位于 grid 边界内。

返回执行 commands 后蛇所停留的最终单元格的位置。

示例 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" 组成。
生成的测评数据确保蛇不会移动到矩阵的边界外。

lightbulb

解题思路

方法一：模拟

我们可以用两个变量 $x$ 和 $y$ 来表示蛇的位置，初始时 $x = y = 0$ ，然后遍历 $\textit{commands}$ ，根据当前的命令更新 $x$ 和 $y$ 的值，最后返回 $x \times n + y$ 即可。

时间复杂度 $O(n)$ ，其中 $n$ 是数组 $\textit{commands}$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def finalPositionOfSnake(self, n: int, commands: List[str]) -> int:
        x = y = 0
        for c in commands:
            match c[0]:
                case "U":
                    x -= 1
                case "D":
                    x += 1
                case "L":
                    y -= 1
                case "R":
                    y += 1
        return x * n + y

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate can efficiently simulate the movement of the snake using simple row and column updates.
question_mark
The candidate understands the need to update indices based on the given commands and matrix dimensions.
question_mark
The candidate handles edge cases, such as boundary movements and command sequences, effectively.

warning

常见陷阱

外企场景

error
Failing to correctly simulate the movement based on the command sequence, especially when alternating between opposite directions.
error
Not updating the snake's position correctly after each command, leading to an incorrect final position.
error
Misunderstanding the matrix indexing formula and incorrectly calculating the final position in the grid.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Changing the grid size n to be larger, which may involve handling a more extensive range of commands.
arrow_right_alt
Implementing the problem with additional constraints, such as limiting the number of directions or varying grid sizes dynamically.
arrow_right_alt
Simulating the movement in a larger matrix with more complex or dynamic command inputs, testing the solution's robustness.

help

常见问题

外企场景

继续练习

#3522 执行指令后的得分 #2744 最大字符串配对数目 #3242 设计相邻元素求和服务