LeetCode 353. 贪吃蛇

Categories:

题目描述
思路分析
1. 解法一：队列 + 哈希集合模拟（推荐）
相似题目

题目描述

✅ 353. 贪吃蛇

思路分析

解法一：队列 + 哈希集合模拟（推荐）

核心思路：

用双端队列维护蛇身，从头到尾保存每个格子的编号。

用哈希集合记录当前蛇身占用的格子，便于 O(1) 判断自撞。

移动时若未吃到食物，先移除尾巴再检查碰撞，避免误判“头撞到刚移动的尾巴”。

复杂度分析：

时间复杂度：O(1) 均摊，每次移动常数操作。

空间复杂度：O(k)，其中 k 为蛇身长度。

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;

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;
    }
}

import "container/list"

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
}

相似题目

题目	难度	考察点
146. LRU 缓存	中等	设计 + 哈希表
355. 设计推特	中等	数据结构设计
362. 敲击计数器	中等	队列
641. 设计循环双端队列	中等	双端队列
707. 设计链表	中等	设计

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/94878234