题目难度: 中等
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
一只蚂蚁坐在由白色和黑色方格构成的无限网格上。开始时，网格全白，蚂蚁面向右侧。每行走一步，蚂蚁执行以下操作。
(1) 如果在白色方格上，则翻转方格的颜色，向右(顺时针)转 90 度，并向前移动一个单位。 (2) 如果在黑色方格上，则翻转方格的颜色，向左(逆时针方向)转 90 度，并向前移动一个单位。
编写程序来模拟蚂蚁执行的前 K 个动作，并返回最终的网格。
网格由数组表示，每个元素是一个字符串，代表网格中的一行，黑色方格由 'X' 表示，白色方格由 '_' 表示，蚂蚁所在的位置由 'L', 'U', 'R', 'D' 表示，分别表示蚂蚁 左、上、右、下 的朝向。只需要返回能够包含蚂蚁走过的所有方格的最小矩形。
示例 1:
- 输入: 0
- 输出: ["R"]
示例 2:
- 输入: 2
- 输出:
[
"_X",
"LX"
]
示例 3:
- 输入: 5
- 输出:
[
"_U",
"X_",
"XX"
]
说明：
- K <= 100000
题目思考
- 需要哪些信息来维护当前状态?
解决方案
思路
- 分析题目, 显然我们需要使用一个字典维护当前经过的网格值, 同时还要维护当前坐标以及方向
- 而为了得到最终包含蚂蚁走过的所有方格的最小矩形, 我们还需要维护四个边界, 这样最后只需要输出这个边界内的所有网格值即可
- 接下来我们只需要按照题目要求的动作模拟即可: 翻转+转向+移动
- 具体实现方面, 我们可以使用一个环状列表存储逆时针顺序的方向, 这样只需要维护当前方向下标, 逆时针旋转时下标+1, 顺时针则下标-1, 这里可以通过取模的方式模拟环
- 而颜色的话可以将白色视为默认值 0, 而黑色为 1, 这样每次翻转只需要用 1 减当前数值即可
- 下面的代码对必要步骤有详细的解释, 方便大家理解
复杂度
- 时间复杂度
O(K): 需要循环 K 次 - 空间复杂度
O(K): 需要存储网格信息, 经过的网格数不大于 K
代码
class Solution:
def printKMoves(self, K: int) -> List[str]:
# grid存储当前经过的网格值, 0白1黑
grid = collections.defaultdict(int)
# 四个边界值
lor, hir, loc, hic = 0, 0, 0, 0
# 当前位置和方向
cr, cc, cd = 0, 0, 0
# directions存储逆时针顺序的四个方向以及其对应的行列delta值
# 例如向右移动是R, 对应的行不变, 列增1
directions = [("R", (0, 1)), ("D", (1, 0)), ("L", (0, -1)), ("U", (-1, 0))]
for _ in range(K):
if grid[cr, cc] == 0:
# 白色, 逆时针旋转方向
cd = (cd + 1) % 4
else:
# 黑色, 顺时针旋转方向
cd = (cd + 3) % 4
# 翻转颜色
grid[cr, cc] = 1 - grid[cr, cc]
dx, dy = directions[cd][1]
# 按照新方向移动一个单位
cr, cc = cr + dx, cc + dy
# 更新边界值
lor = min(lor, cr)
hir = max(hir, cr)
loc = min(loc, cc)
hic = max(hic, cc)
res = []
# 从上到下遍历每一行的网格值
for r in range(lor, hir + 1):
res.append("")
# 从左到右遍历每一列的网格值
for c in range(loc, hic + 1):
if (r, c) == (cr, cc):
# 当前蚂蚁所在位置, 使用其当前方向的字符
res[-1] += directions[cd][0]
else:
# 根据存储的值来决定是_还是X
res[-1] += "_" if grid[r, c] == 0 else "X"
return res
大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号