Swift 实战：用链表和哈希表写出高性能的贪吃蛇引擎（LeetCode 353）

摘要

这题的目标是设计一个“贪吃蛇”核心引擎：给定棋盘大小和一串食物位置，支持不断调用 move(direction) 推进游戏，返回当前分数，撞墙或咬到自己就结束（返回 -1）。本文用 Swift 从零实现一个能跑起来的 Demo，包括完整的 SnakeGame 类、关键数据结构设计、边界与碰撞处理、以及几组样例跑数。代码贴近实战，既能交作业，也能当你写小型游戏/面试题的参考模板。

描述

题目要我们实现三个能力：

• SnakeGame(width, height, food): 初始化棋盘和食物队列。

• move(direction: String) -> Int: 让蛇向 U/D/L/R 走一步；

  • 吃到食物：长度 +1，分数 +1。
  • 普通移动：头前进一格，尾巴同时挪走一格。
  • 撞墙/咬到自己：返回 -1（游戏结束）。

• 返回值：当前分数（吃到几次食物）。若结束，始终返回 -1。

要点在于：如何让每次 move 都保持 O(1) 或接近 O(1) 的时间复杂度。

解决方案

高效思路（也是业界常见写法）：

1. 双端结构存蛇身：
   用一个可 O(1) 头插、尾删的结构维护蛇身顺序（头在尾端更直观），我们用一个简易的 双向链表。

2. 快速查重靠哈希集合：
   用 Set 存蛇身占用的格子，一步就能判断“咬到自己”。

3. 一维编码坐标：
   位置 (r, c) 编码为 id = r * width + c。既省内存又快。

4. 先判断是否吃到食物：

   • 吃到：不移除尾巴（蛇变长）。
   • 没吃到：先把尾巴从集合里移除（因为尾巴会移动），再判断新头是否与身体冲突。

5. 边界/自撞检查：

   • 越界直接结束。
   • 自撞：若新头位置已经在集合里（注意“没吃到食物”的情况下我们先拿掉尾巴再查重）。

解析问题与解决方案

下面是完整可运行的 Swift 代码（命令行/Playground 都能跑）。为了 O(1) 头插尾删，我们写了个轻量的双向链表 Deque；蛇身用 Deque<Int> 维护，哈希表记录占用。

import Foundation// 轻量双向链表（Deque）——支持 O(1) 头删尾插等操作
final class Deque<T> {final class Node<T> {var val: Tvar prev: Node<T>?var next: Node<T>?init(_ v: T) { self.val = v }}private var head: Node<T>?private var tail: Node<T>?private(set) var count: Int = 0var isEmpty: Bool { count == 0 }func pushBack(_ v: T) {let node = Node(v)if let t = tail {t.next = nodenode.prev = ttail = node} else {head = nodetail = node}count += 1}func popFront() -> T? {guard let h = head else { return nil }let v = h.vallet nh = h.nextnh?.prev = nilhead = nhif nh == nil { tail = nil }count -= 1return v}func back() -> T? { tail?.val }func front() -> T? { head?.val }
}// 核心：SnakeGame
final class SnakeGame {private let width: Intprivate let height: Intprivate let food: [[Int]]private var foodIndex: Int = 0// 蛇身：尾在 front，头在 backprivate var body = Deque<Int>()// 占用表：快速判断“撞到自己”private var occupied = Set<Int>()private var score = 0// 方向映射private let dirMap: [String: (Int, Int)] = ["U": (-1, 0), "D": (1, 0),"L": (0, -1), "R": (0, 1)]init(_ width: Int, _ height: Int, _ food: [[Int]]) {self.width = widthself.height = heightself.food = food// 初始蛇：长度为 1，在 (0,0)let startId = 0body.pushBack(startId)occupied.insert(startId)score = 0foodIndex = 0}// 坐标与一维 id 的互转private func idOf(_ r: Int, _ c: Int) -> Int { r * width + c }private func rcOf(_ id: Int) -> (Int, Int) { (id / width, id % width) }// 一步移动：返回当前分数，若失败返回 -1func move(_ direction: String) -> Int {guard let (dr, dc) = dirMap[direction] else { return -1 }guard let headId = body.back() else { return -1 }let (hr, hc) = rcOf(headId)let nr = hr + drlet nc = hc + dc// 1) 越界？if nr < 0 || nr >= height || nc < 0 || nc >= width {return -1}let newHead = idOf(nr, nc)// 2) 是否吃到食物？let willEat = (foodIndex < food.count &&food[foodIndex][0] == nr &&food[foodIndex][1] == nc)// 3) 如果不会吃到，尾巴要移动：先从占用表移除尾巴if !willEat {if let tailId = body.front() {_ = body.popFront()occupied.remove(tailId)}}// 4) 自撞？if occupied.contains(newHead) {return -1}// 5) 头前进：加入蛇身与占用表body.pushBack(newHead)occupied.insert(newHead)// 6) 吃到食物：分数+1，食物指针后移if willEat {score += 1foodIndex += 1}return score}
}

关键细节逐条讲

• 为什么先“挪尾再查撞”？
  蛇不吃的时候，下一步尾巴会离开原位置。所以你可以“允许头移动到原尾巴位置”。实现上就表现为：先把尾巴从 occupied 里移除，再查新头是否在 occupied。这能避免错判“咬到自己”。

• 数据结构选型

  • Deque：我们只需要 O(1) 地在“尾部加头”、“头部去尾”，链表最直觉；自己实现很轻，避免 Array.removeFirst() 的 O(n)。
  • Set：哈希查重 O(1)，非常关键。
  • 一维编码位置：让 Set<Int> 更轻量，少了元组 hash 的开销。

• 食物逻辑

  • “吃到食物不移除尾巴”是增长的本质。
  • foodIndex 单调递增就行，省去额外数据结构。

• 方向映射
  简单 Dictionary，易于拓展（比如以后加入斜向就是改这儿）。

示例与运行结果

下面给一段可运行的 Demo，包含两组测试：一组是经典样例，一组是我自定义的压力测试（快速吃两个食物、触发自撞）。

// MARK: - Demo 1（LeetCode 常见用例）
do {let game = SnakeGame(3, 2, [[1,2],[0,1]])print("Demo 1")print(game.move("R")) // 0print(game.move("D")) // 0print(game.move("R")) // 1 (吃到 [1,2])print(game.move("U")) // 1print(game.move("L")) // 2 (吃到 [0,1])print(game.move("U")) // -1 (撞墙)print("----")
}// MARK: - Demo 2（连续吃食物 + 自撞）
do {let game = SnakeGame(4, 3, [[0,1],[0,2],[0,3]])print("Demo 2")print(game.move("R")) // 1print(game.move("R")) // 2print(game.move("R")) // 3print(game.move("D")) // 3print(game.move("L")) // 3print(game.move("U")) // -1（向上回到自己身体）print("----")
}

可能输出（你的控制台应该是一致的）：

Demo 1
0
0
1
1
2
-1
----
Demo 2
1
2
3
3
3
-1
----

你可以在 Playground 或命令行直接复制粘贴运行，感受一下每一步的状态变化。

时间复杂度

• 每次 move：
  全部是 O(1) 操作：

  • 链表尾插/头删 O(1)
  • Set 增删查 O(1)
  • 一次边界和食物判断 O(1)
    因此整题可以轻松达到 均摊 O(1)。

• 初始化：
  O(1)（食物数组只是引用，未做预处理）。

空间复杂度

• 蛇身链表：最多占用 O(k)（k 为当前蛇长）。
• 占用集合：同样 O(k)。
• 食物数组：O(f)（f 为食物个数）。
• 其他都是常数。

整体空间：O(k + f)。

总结

这道题表面是小游戏，实则是数据结构设计题。抓住三件事就能写得又快又稳：

1. 用 Deque + Set 保证 O(1) 移动与查重；
2. “不吃时先挪尾巴再查撞”这一步是避免误判的关键；
3. 一维编码位置提升哈希效率，让实现更简洁。

如果你以后要把它扩展成单机小游戏，渲染层（SwiftUI、SpriteKit）只需要消费 move 的结果，按照 Deque 里的坐标把节点画出来即可；引擎层完全复用本文代码。