LeetCode 面试题 16.22. 兰顿蚂蚁

Categories:

题目描述
思路分析
1. 解法一：模拟 + 哈希表动态扩展（推荐）
相似题目

题目描述

✅ 面试题 16.22. 兰顿蚂蚁

思路分析

解法一：模拟 + 哈希表动态扩展（推荐）

核心思路：

兰顿蚂蚁规则：白格子 → 右转，黑格子 → 左转，翻转颜色后前进一步

使用哈希集合记录黑色格子坐标，初始全为白色

用方向数组 dirs 表示上下左右四个方向，右转为 (dir+1)%4，左转为 (dir+3)%4

记录蚂蚁走过的最小/最大行列坐标，最终构建最小包围矩形并输出字符串数组

复杂度分析：

时间复杂度：O(n + R×C)，其中 n 为步数，R 和 C 为结果矩形的行列数

空间复杂度：O(n)，哈希表存储黑色格子数量最多为 n

class Solution {
    public List<String> printKMoves(int K) {
        // 方向：上、右、下、左（顺时针顺序方便右转/左转）
        int[] dr = {-1, 0, 1, 0};
        int[] dc = {0, 1, 0, -1};

        Set<String> black = new HashSet<>();
        int r = 0, c = 0, dir = 0;

        // 记录边界
        int minR = 0, maxR = 0, minC = 0, maxC = 0;

        for (int i = 0; i < K; i++) {
            String key = r + "," + c;

            if (black.contains(key)) {
                // 黑色格子：左转，翻为白色
                dir = (dir + 3) % 4;
                black.remove(key);
            } else {
                // 白色格子：右转，翻为黑色
                dir = (dir + 1) % 4;
                black.add(key);
            }

            // 前进一步
            r += dr[dir];
            c += dc[dir];

            // 更新边界
            minR = Math.min(minR, r);
            maxR = Math.max(maxR, r);
            minC = Math.min(minC, c);
            maxC = Math.max(maxC, c);
        }

        // 构建结果矩形
        int rows = maxR - minR + 1;
        int cols = maxC - minC + 1;
        List<String> result = new ArrayList<>();

        for (int i = 0; i < rows; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < cols; j++) {
                String key = (i + minR) + "," + (j + minC);
                sb.append(black.contains(key) ? 'X' : '_');
            }
            result.add(sb.toString());
        }

        // 标记蚂蚁位置
        int antRow = r - minR;
        int antCol = c - minC;
        char[] antLine = result.get(antRow).toCharArray();
        antLine[antCol] = dirChar(dir);
        result.set(antRow, new String(antLine));

        return result;
    }

    // 方向对应的字符表示
    private char dirChar(int dir) {
        // 上、右、下、左
        char[] chars = {'^', '>', 'v', '<'};
        return chars[dir];
    }
}

func printKMoves(K int) []string {
    // 方向：上、右、下、左（顺时针顺序方便右转/左转）
    dr := []int{-1, 0, 1, 0}
    dc := []int{0, 1, 0, -1}
    dirChars := []byte{'^', '>', 'v', '<'}

    type Point struct{ r, c int }
    black := make(map[Point]bool)

    r, c, dir := 0, 0, 0
    minR, maxR, minC, maxC := 0, 0, 0, 0

    for i := 0; i < K; i++ {
        p := Point{r, c}

        if black[p] {
            // 黑色格子：左转，翻为白色
            dir = (dir + 3) % 4
            delete(black, p)
        } else {
            // 白色格子：右转，翻为黑色
            dir = (dir + 1) % 4
            black[p] = true
        }

        // 前进一步
        r += dr[dir]
        c += dc[dir]

        // 更新边界
        if r < minR {
            minR = r
        }
        if r > maxR {
            maxR = r
        }
        if c < minC {
            minC = c
        }
        if c > maxC {
            maxC = c
        }
    }

    // 构建结果矩形
    rows := maxR - minR + 1
    cols := maxC - minC + 1
    grid := make([][]byte, rows)
    for i := range grid {
        grid[i] = make([]byte, cols)
        for j := range grid[i] {
            grid[i][j] = '_'
        }
    }

    // 填充黑色格子
    for p := range black {
        grid[p.r-minR][p.c-minC] = 'X'
    }

    // 标记蚂蚁位置和方向
    grid[r-minR][c-minC] = dirChars[dir]

    result := make([]string, rows)
    for i, row := range grid {
        result[i] = string(row)
    }

    return result
}

相似题目

题目	难度	考察点
874. 模拟行走机器人	中等	模拟、哈希表
54. 螺旋矩阵	中等	模拟、矩阵
59. 螺旋矩阵 II	中等	模拟、矩阵
289. 生命游戏	中等	模拟、矩阵
36. 有效的数独	中等	哈希表、矩阵
498. 对角线遍历	中等	模拟、矩阵

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/82379274