langtons-ant-lcci

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

本书是原谷歌资深面试官的经验之作，帮助了许多想要加入脸书、苹果、谷歌等 IT 名企的求职者拿到 Dream offer。本专题的 100+ 编程面试题是在原书基础上精心挑选出来的，帮助你轻松应战 IT 名企技术面试。

英文版：Cracking the Coding Interview，源自硅谷程序员的面试红宝书

LCCI

An ant is sitting on an infinite grid of white and black squares. It initially faces right. All squares are white initially.

At each step, it does the following:

(1) At a white square, flip the color of the square, turn 90 degrees right (clockwise), and move forward one unit.

(2) At a black square, flip the color of the square, turn 90 degrees left (counter-clockwise), and move forward one unit.

Write a program to simulate the first K moves that the ant makes and print the final board as a grid.

The grid should be represented as an array of strings, where each element represents one row in the grid. The black square is represented as <code>&#39;X&#39;</code>, and the white square is represented as <code>&#39;_&#39;</code>, the square which is occupied by the ant is represented as <code>&#39;L&#39;</code>, <code>&#39;U&#39;</code>, <code>&#39;R&#39;</code>, <code>&#39;D&#39;</code>, which means the left, up, right and down orientations respectively. You only need to return the minimum matrix that is able to contain all squares that are passed through by the ant.

Example 1:

<pre>
Input: 0
Output: [&quot;R&quot;]
</pre>

Example 2:

<pre>
Input: 2
Output:
[
&nbsp; &quot;_X&quot;,
&nbsp; &quot;LX&quot;
]
</pre>

Example 3:

<pre>
Input: 5
Output:
[
&nbsp; &quot;_U&quot;,
&nbsp; &quot;X_&quot;,
&nbsp; &quot;XX&quot;
]
</pre>

Note: 

<ul>
	<li><code>K &lt;= 100000</code></li>
</ul>

printKMoves

Langtons Ant LCCI

Array

Hash Table

String

Matrix

Simulation

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

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

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

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

示例 1：

<pre>
输入：0
输出：["R"]
</pre>

示例 2：

<pre>
输入：2
输出：
[
&nbsp; "_X",
&nbsp; "LX"
]
</pre>

示例 3：

<pre>
输入：5
输出：
[
&nbsp; "_U",
&nbsp; "X_",
&nbsp; "XX"
]
</pre>

说明：

<ul>
	<li><code>K &lt;= 100000</code></li>
</ul>