LeetCode 面试题 16.22. 兰顿蚂蚁

一、题目

  一只蚂蚁坐在由白色和黑色方格构成的无限网格上。开始时，网格全白，蚂蚁面向右侧。每行走一步，蚂蚁执行以下操作。

  (1) 如果在白色方格上，则翻转方格的颜色，向右(顺时针)转 90 度，并向前移动一个单位。
  (2) 如果在黑色方格上，则翻转方格的颜色，向左(逆时针方向)转 90 度，并向前移动一个单位。

  编写程序来模拟蚂蚁执行的前 K 个动作，并返回最终的网格。

  网格由数组表示，每个元素是一个字符串，代表网格中的一行，黑色方格由 'X' 表示，白色方格由 '_' 表示，蚂蚁所在的位置由 'L', 'U', 'R', 'D' 表示，分别表示蚂蚁 左、上、右、下 的朝向。只需要返回能够包含蚂蚁走过的所有方格的最小矩形。

示例 1:

输入: 0
输出: [“R”]

示例 2:

输入: 2
输出:
[
“_X”,
“LX”
]

示例 3:

输入: 5
输出:
[
“U",
"X”,
“XX”
]

说明：

• K <= 100000

  点击此处跳转题目。

二、C# 题解

  题目比较简单，一步步实现就好。这里说明以下几点：

1. 使用 hashset 存储是否有黑格，会比使用 dictionary 存储每个位置的颜色要好，速度回更快。
2. 最后使用 char 数组存储中间数据，会比使用 stringbuilder 处理每一行数据要好，因为已经知道了矩阵规模，可以直接分配内存读写数据，而 stringbuilder 不能直接进行索引。

public class Solution {public static readonly int[,] DELTA_POS = {{ 1, 0 },{ 0, 1 },{ -1, 0 },{ 0, -1 },};public static readonly char[] DIRECTIONS = { 'R', 'U', 'L', 'D' };public IList<string> PrintKMoves(int K) {int i    = 0, j = 0;                        // 当前位置int dir  = 0;                               // 当前方向int minx = 0, miny = 0, maxx = 0, maxy = 0; // 最大边界HashSet<(int x, int y)> blackBlock = new HashSet<(int x, int y)>(); // 记录当前黑格位置while (K-- > 0) {// 更新方向、翻转黑白格if (blackBlock.Add((i, j))) dir = (dir + 3) % 4; // 白格才能加进去，加进去的同时完成了翻转颜色else {dir = (dir + 1) % 4;blackBlock.Remove((i, j)); // 黑格移出，变成白格}// 依据方向更新当前位置i += DELTA_POS[dir, 0];j += DELTA_POS[dir, 1];// 更新最大边界switch (dir) {case 0 when i > maxx:maxx = i;break;case 1 when j > maxy:maxy = j;break;case 2 when i < minx:minx = i;break;case 3 when j < miny:miny = j;break;}}IList<string> ans = new List<string>(); // 答案char[][] data = new char[maxy - miny + 1][]; // 中间记录数据// 全部初始化为白格for (var x = 0; x < data.Length; x++) {data[x] = new char[maxx - minx + 1];for (var y = 0; y < data[x].Length; y++)data[x][y] = '_';}// 黑格覆盖foreach (var tuple in blackBlock)data[tuple.y - miny][tuple.x - minx] = 'X';// 覆盖当前位置data[j - miny][i - minx] = DIRECTIONS[dir];// 添加答案for (var l = data.Length - 1; l >= 0; l--)ans.Add(new string(data[l]));return ans;}
}

• 时间：152 ms，击败 100.00% 使用 C# 的用户
• 内存：77.01 MB，击败 100.00% 使用 C# 的用户