LeetCode 353. 贪吃蛇

2023-02-22 HGNULB 约 13 分钟

文章信息 7 个分类 5 个标签

分类

题目描述

✅ 353. 贪吃蛇

题意分析

设计一个贪吃蛇游戏：蛇初始长度为 1，位于左上角 (0, 0)。每次调用 move 传入 U/D/L/R 之一，蛇头朝该方向走一格。若走到食物上，蛇长度加一、分数加一；否则蛇整体前移（头进尾出，长度不变）。撞墙或撞到自己的身体则返回 -1，否则返回当前分数。

食物按 food 数组给定的顺序依次出现，只有吃掉第 k 个才会出现第 k+1 个。这意味着任何时刻场上只有一个食物，位置就是 food[foodIndex]，判断「是否吃到」只需与这一项比较，不需要维护食物集合。

需要 $O(1)$ 判断的两件事是「新位置是否出界」和「新位置是否撞到自己」。前者用坐标范围判断即可，后者若遍历蛇身则是 $O(L)$，在调用次数多、蛇很长时会退化，所以要额外维护一个占用集合。

最微妙的规则是尾巴：当蛇没吃到食物时，尾巴那一格在这一步会腾出来，所以蛇头是可以移动到原尾巴位置的。这条规则决定了「移尾」和「判撞」这两个操作的先后顺序，是本题最主要的考点。

边界包括：网格只有一行或一列时，某些方向必然撞墙；蛇长度为 1 时头尾是同一格；食物恰好出现在蛇身上的情况题目已排除；以及食物全部吃完后 foodIndex 越界的保护。

解法：队列 + 哈希集合模拟

核心思路

朴素做法是用一个列表按顺序存蛇身格子，每次移动时在列表里线性查找新位置是否已被占用。逻辑对，但单次移动是 $O(L)$，蛇最长可达网格面积，调用次数又很多，整体退化成平方级。瓶颈在于「判断某格是否属于蛇身」这个查询被用线性扫描解决了。

观察点是：蛇身在结构上是一条先进先出的序列——新格子总是从头部加入，旧格子总是从尾部离开，这正是队列的语义；而「某格是否被占用」是一个纯粹的成员查询，正是哈希集合的语义。两者维护同一份内容、各自回答不同的问题，就能把每次移动压到常数时间。

于是数据结构定为一个双端队列 body（队首是尾巴、队尾是蛇头）加一个哈希集合 occupied。为了让格子能直接进集合，把二维坐标编码成一维整数 r * width + c，这是一一映射，解码用整除和取余即可。

不变量是：任意 move 调用返回后，body 中的元素从队首到队尾恰好是蛇从尾到头的每一节，且 occupied 的内容与 body 完全一致。两个结构必须在同一处代码里同增同减，任何一处只改其中之一都会让不变量破裂。

核心的顺序决策来自尾巴规则。设新位置为 next：如果这一步没吃到食物，尾巴会离开，此时它腾出的格子对 next 而言是可用的。所以正确的执行顺序是——先把尾巴从两个结构里移除，再检查 next 是否与剩余蛇身冲突。如果反过来先判撞，就会把「头移动到原尾巴位置」这种完全合法的操作误判成自撞，最典型的场景是蛇绕成一圈后头咬着自己尾巴走。

反之，如果这一步吃到了食物，尾巴不动、蛇变长，此时不能移除尾巴，判撞时也必须把尾巴算在内。

还有一个容易被忽略的顺序：越界检查要放在最前面，因为一旦越界就直接返回 -1，不应该对任何结构产生副作用。

解题步骤

构造函数里初始化宽高、食物数组、食物下标、分数，并把编号 0（即左上角）同时放入 body 和 occupied。之所以两处都要放，是不变量的起点要求；只放一处会让第一步移动的判撞或移尾出错。

move 开头取队尾作为当前蛇头，并解码成行列 r = head / width、c = head % width。之所以能这样解码，是因为编码 r * width + c 中 c 严格小于 width，除法和取余是这个编码的精确逆运算。

按方向调整 r 或 c。之所以用 switch 而不是方向数组，是因为输入是字符串常量，直接分支比建映射表更直白；default 分支承担 R，因为四个方向已被穷尽。

立刻检查 r、c 是否越界，越界直接返回 -1。之所以必须最先检查，是因为越界坐标编码出的整数可能与某个合法格子的编号重合（例如 c = -1 时 r * width - 1 恰好是上一行的末尾），先编码再判断会得到错误结论；同时提前返回也保证了游戏结束时不留下半更新的状态。

计算 next = r * width + c，并判断是否吃到食物：要求 foodIndex 未越界且 food[foodIndex] 的行列与新位置相同。之所以要先判 foodIndex < food.length，是因为食物吃完后数组已无更多项，不判会直接抛越界异常。

若没吃到食物，从 body 队首弹出尾巴，并从 occupied 中删除它。之所以放在判撞之前，是因为尾巴在这一步确实离开了它的格子，蛇头有权占据它。

检查 occupied 是否包含 next，包含则返回 -1。之所以此时的集合状态是准确的：没吃食物时尾巴已被移除，吃了食物时尾巴仍在，两种情形下集合都恰好等于「移动后蛇头之外的身体」。

把 next 加入 body 队尾和 occupied。之所以两处同时加，仍是维持不变量。

若吃到食物，分数加一、食物下标加一。之所以推进下标，是因为食物按序出现，下一个待吃的自然是后一项。

返回当前分数。

以 width = 3, height = 2, food = [[1, 2], [0, 1]] 走一遍，网格编号为第一行 0、1、2，第二行 3、4、5。

初始：body = [0]，occupied = {0}，score = 0，foodIndex = 0。

move("R")：头是 0，r = 0、c = 0，右移得 c = 1，不越界，next = 1。食物是 (1, 2)，与 (0, 1) 不符，未吃到。移尾：弹出 0，occupied = {}。判撞：occupied 不含 1，通过。加入：body = [1]，occupied = {1}。返回 0。

move("D")：头是 1，r = 0、c = 1，下移得 r = 1，不越界，next = 1 * 3 + 1 = 4。食物 (1, 2) 不符。移尾：弹出 1。判撞通过。body = [4]，occupied = {4}。返回 0。

move("R")：头是 4，r = 1、c = 1，右移得 c = 2，不越界，next = 5。食物 (1, 2) 与 (1, 2) 相符，吃到了。不移尾。判撞：occupied = {4} 不含 5，通过。加入：body = [4, 5]，occupied = {4, 5}，蛇长变成 2。分数加一得 1，foodIndex 变 1。返回 1。

move("U")：头是 5，r = 1、c = 2，上移得 r = 0，不越界，next = 2。新食物是 (0, 1)，与 (0, 2) 不符。移尾：弹出 4，occupied = {5}。判撞：不含 2，通过。body = [5, 2]，occupied = {5, 2}。返回 1。

move("L")：头是 2，左移得 c = 1，next = 1。食物 (0, 1) 相符，吃到。不移尾。判撞：occupied = {5, 2} 不含 1，通过。body = [5, 2, 1]，分数变 2，foodIndex 变 2。返回 2。

move("U")：头是 1，r = 0，上移得 r = -1，越界，返回 -1。游戏结束。

整个过程验证了「未吃食物时先移尾」的必要性：若在第四步先判撞再移尾，虽未出错，但只要构造一条首尾相接的路径（比如 2×2 网格中蛇长为 2 绕圈），先判撞就会把合法移动误判为死亡。

代码实现

class SnakeGame {
    private final int width;
    private final int height;
    private final int[][] food;
    private int foodIndex;
    private int score;
    private final Deque<Integer> body;
    private final Set<Integer> occupied;

    public SnakeGame(int width, int height, int[][] food) {
        this.width = width;
        this.height = height;
        this.food = food;
        this.foodIndex = 0;
        this.score = 0;
        this.body = new ArrayDeque<>();
        this.occupied = new HashSet<>();

        body.addLast(0);
        occupied.add(0);
    }

    public int move(String direction) {
        int head = body.peekLast();
        int r = head / width;
        int c = head % width;

        switch (direction) {
            case "U":
                r--;
                break;
            case "D":
                r++;
                break;
            case "L":
                c--;
                break;
            default:
                c++;
                break;
        }

        if (r < 0 || r >= height || c < 0 || c >= width) {
            return -1;
        }

        int next = r * width + c;
        boolean eating = foodIndex < food.length
                && food[foodIndex][0] == r
                && food[foodIndex][1] == c;

        if (!eating) {
            int tail = body.pollFirst();
            occupied.remove(tail);
        }

        if (occupied.contains(next)) {
            return -1;
        }

        body.addLast(next);
        occupied.add(next);

        if (eating) {
            score++;
            foodIndex++;
        }

        return score;
    }
}

type SnakeGame struct {
    width     int
    height    int
    food      [][]int
    foodIndex int
    score     int
    body      *list.List
    occupied  map[int]bool
}

func Constructor(width int, height int, food [][]int) SnakeGame {
    body := list.New()
    body.PushBack(0)

    return SnakeGame{
        width:     width,
        height:    height,
        food:      food,
        foodIndex: 0,
        score:     0,
        body:      body,
        occupied:  map[int]bool{0: true},
    }
}

func (g *SnakeGame) Move(direction string) int {
    head := g.body.Back().Value.(int)
    r := head / g.width
    c := head % g.width

    switch direction {
    case "U":
        r--
    case "D":
        r++
    case "L":
        c--
    default:
        c++
    }

    if r < 0 || r >= g.height || c < 0 || c >= g.width {
        return -1
    }

    next := r*g.width + c
    eating := g.foodIndex < len(g.food) && g.food[g.foodIndex][0] == r && g.food[g.foodIndex][1] == c

    if !eating {
        tail := g.body.Front()
        g.body.Remove(tail)
        delete(g.occupied, tail.Value.(int))
    }

    if g.occupied[next] {
        return -1
    }

    g.body.PushBack(next)
    g.occupied[next] = true

    if eating {
        g.score++
        g.foodIndex++
    }

    return g.score
}

复杂度分析

时间复杂度：单次 move 为 $O(1)$，凭据是整个流程只有常数次算术、一次队首弹出、一次队尾插入、一次集合查询和至多两次集合增删，全部是常数或均摊常数操作，与蛇的长度无关。

空间复杂度：$O(\min(width \times height, F))$，其中 $F$ 是食物总数，凭据是蛇身长度等于初始长度加已吃食物数、且不可能超过网格格子总数，body 与 occupied 保存的是同一批格子，食物数组本身由调用方持有不额外计入。

关键点总结

一份数据要同时回答「顺序问题」和「成员问题」时，就用两个结构并行维护：队列负责先进先出的顺序语义，哈希集合负责 $O(1)$ 的存在性查询。代价是必须保证两者始终同增同减。

二维坐标编码成 r * width + c 是网格题的通用手法，它让格子可以直接作为哈希键或数组下标；使用时务必确认 c 严格小于 width，否则映射不再是单射。

越界检查要在编码之前完成。负的列坐标编码后可能与合法格子撞号，先编码再判断会得到看似合理却完全错误的结论。

「尾巴在本步腾出的格子对蛇头可用」这条规则决定了「先移尾、后判撞」的顺序，这是本题唯一真正的算法陷阱，也是面试官最常验证的点。

顺序出现的资源（本题的食物）只需一个下标指针，不需要集合或队列；判断命中时永远只和当前指针指向的那一项比较，并在推进前检查越界。

面试视角：面试官会先让你说清数据结构选型及理由，然后专门构造「蛇头追上自己尾巴」的用例来检验顺序问题。主动说出这个用例并解释为什么要先移尾，基本就拿到了这题的核心分。常见追问是「如果要支持撤销上一步移动怎么办」，答案是额外记录被弹出的尾巴值和当时的分数、食物下标，做一次逆操作。

易错点总结

先判撞再移尾：用例 width = 2, height = 2，蛇长 2 时执行绕圈移动，蛇头走向原尾巴格会被误判为自撞返回 -1，而这是合法移动。

吃到食物时也移除尾巴：用例 width = 3, height = 2, food = [[1, 2]]，第三步吃到食物后蛇长应为 2，但尾巴被弹出导致长度仍为 1，后续所有自撞判断都偏松。

越界检查放在编码之后，用 next < 0 || next >= width * height 判断：用例 width = 3, height = 2，蛇头在 (1, 0) 即编号 3 时向左移动，c = -1 编码得 1 * 3 - 1 = 2，落在合法范围内，会被当成移动到 (0, 2)，蛇直接穿墙。

只维护队列不维护集合，判撞时遍历队列：用例网格 100×100、调用上万次且蛇很长，单次移动退化成 $O(L)$，总体超时。

只维护集合不维护队列：用例任意需要移尾的移动，集合无序，取不出「最早进入的那个格子」，尾巴无从删除。

移尾时只从队列弹出而忘记从集合删除：用例 width = 3, height = 1，蛇在一行内左右往返，集合里残留已离开的格子，第二次经过时被误判为自撞。

判断吃食物时不检查 foodIndex < food.length：用例食物全部吃完后继续调用 move，food[foodIndex] 直接抛数组越界异常。

吃到食物后忘记推进 foodIndex：用例 food = [[0, 1], [0, 2]]，蛇会在同一格上反复得分，分数无限增长，且第二个食物永远不出现。

用 body.peekFirst() 取蛇头：用例任意长度大于 1 的蛇，取到的是尾巴，移动方向计算完全错位，第二步起就返回错误结果。

分数用 body.size() - 1 现算而不单独维护：用例吃到食物但随后撞墙返回 -1 的序列，本身尚可；但若在返回 -1 之前已经修改过 body，长度与真实分数脱节，需要额外回滚，单独维护 score 更稳。

Java 里 occupied.remove(tail) 中 tail 是 int 而集合是 Set<Integer>：装箱后调用的是按对象删除的重载，行为正确；但若集合误写成 Set<Object> 或 List<Integer>，remove(int) 会被解析成按下标删除，删掉错误的元素。

Go 里先 g.body.Remove(tail) 再读 tail.Value 时误以为值已被清空而改用其他变量缓存出错：正确做法是 Remove 后 Value 依然可读，或直接接收 Remove 的返回值。

相似题目

题目	难度	考察点
146. LRU 缓存	中等	同样是哈希表配双向链表，但链表节点需支持任意位置摘除
380. O(1) 时间插入、删除和获取随机元素	中等	哈希表配动态数组，删除时用尾元素填坑以保持 $O(1)$
622. 设计循环队列	中等	用定长数组加双指针模拟队列，考察满与空的区分
933. 最近的请求次数	简单	队列只做按时间过期的出队，不需要成员查询
362. 敲击计数器	中等	同为时间窗口维护，可用队列也可用定长环形桶做常数空间优化