java - 面试时简单贪吃蛇游戏的数据结构设计

Question

这不是一个实际的问题，我只是想在这里讨论和学习数据结构设计，听说现场面试时谷歌问过这个问题。请告诉我如何改进我的设计，谢谢!

一开始我想使用双端队列来存储蛇 body 部位的 x,y 坐标对。

deque<pair<x, y>> snakeBodyParts;

因为当蛇移动时很容易向前推 - 根据旧头部位置和当前方向创建新的坐标对作为新头部，然后弹回以移除尾部。这样 move，eat，check head hit wall 都是 O(1) 操作，很容易用 deque 实现。但是检查新的头部位置是否与蛇的 body 重叠需要遍历所有 body 部位的位置 - O(L) 时间复杂度，L 是 body 部位的数量。

为了改进它，我考虑将所有坐标放入 unordered_set(C++) 或 hashset(Java) 中，同时仍然保留我的旧双端队列，它可以给我 O(1) 来检查头部是否现在撞到 body 。但我不知道这是否是个好主意，因为它几乎使内存和代码量翻倍，每当我向双端队列添加/删除时，我都需要对我的哈希集执行此操作。

unordered_set<pair<int, int>, pair_hash> bodyPartsSet;

我也考虑过创建我自己的结构，类似于链表，除了它指向前一个节点:

SnakeBodyNode {
    int x;
    int y;
    SnakeBodyNode * prev;
}

然后我还需要两个指向 head 和 tail 的指针以及一个 direction 变量。

SnakeBodyNode * head;
SnakeBodyNode * tail;
char dir;

但是我看不出这有什么好处，仍然需要哈希得到 O(1) 来检查头部是否撞到 body ..

我的 deque + hash 设计有什么缺陷吗？或者谁有更好的想法可以分享？

Answer 1

我只会使用 unordered_set。您的顾虑是:

• 快速插入新头 - 这是 unordered_set 的 O(1)。
• 快速删除现有的尾部 - 这是 unordered_set 的 O(1)。
• 没有重复(检查头部是否与 body 相交)——这是有保证的对于 unordered_set(它不允许重复)。

当插入一个新的头部时，你不需要做任何特别的事情来检查它是否与 body 相交；如果这样做，你会得到一个错误。