程序员面试金典 - 面试题 16.22. 兰顿蚂蚁（deque模拟）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了程序员面试金典 - 面试题 16.22. 兰顿蚂蚁（deque模拟），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2868字，纯文字阅读大概需要5分钟。
内容图文
1. 题目
一只蚂蚁坐在由白色和黑色方格构成的无限网格上。
开始时，网格全白，蚂蚁面向右侧。
每行走一步，蚂蚁执行以下操作。
- (1) 如果在白色方格上，则翻转方格的颜色，向右(顺时针)转 90 度，并向前移动一个单位。
- (2) 如果在黑色方格上，则翻转方格的颜色，向左(逆时针方向)转 90 度，并向前移动一个单位。
编写程序来模拟蚂蚁执行的前 K 个动作，并返回最终的网格。
网格由数组表示，每个元素是一个字符串，代表网格中的一行，
黑色方格由 ‘X’ 表示，白色方格由 ‘_’ 表示，
蚂蚁所在的位置由 ‘L’, ‘U’, ‘R’, ‘D’ 表示，分别表示蚂蚁 左、上、右、下 的朝向。
只需要返回能够包含蚂蚁走过的所有方格的最小矩形。
示例 1:
输入: 0
输出: ["R"]
示例 2:
输入: 2
输出:
[
"_X",
"LX"
]
示例 3:
输入: 5
输出:
[
"_U",
"X_",
"XX"
]
说明：
K <= 100000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/langtons-ant-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
兰顿蚂蚁解释
据说最后会变成这样的图形，有意思！！！
2.1 超时解
K = 100000, 超时，string.insert 操作造成数据搬移，性能不高
class Solution {
vector<string> ans = {"_"};
// 右 下 左 上
vector<char> dirCh = {'R','D','L','U'};
public:
vector<string> printKMoves(int K) {
int x = 0, y = 0, d = 0, columns = 1;
while(K--)
update(x,y,d,columns);//更新k步的地图
ans[x][y] = dirCh[d];//最后的位置填方向
return ans;
}
void update(int& x, int& y, int& d, int& columns)
{
char ch = ans[x][y];
ans[x][y] = (ch=='_' ? 'X' : '_');//反转颜色
d = (ch=='_' ? (d+1)%4 : (d+3)%4);//转向
if(d==0)//R
{
y++;
if(y == ans[x].size())//需要开新的地图，右侧加列
{
for(string& s : ans)
s += '_';
columns++;
}
}
else if(d==1)//D
{
x++;
if(x == ans.size())//需要开新的地图，下面加行
ans.push_back(string(columns,'_'));
}
else if(d==2)//L
{
y--;
if(y<0)//需要开新的地图，左侧加列
{
y = 0;
for(string& s : ans)
s = '_'+ s;
columns++;
}
}
else//U
{
x--;
if(x<0)//需要开新的地图，上面加行
{
x = 0;
ans.insert(ans.begin(),string(columns,'_'));
}
}
}
};
2.2 deque解题
- 采用双端队列，减少数据搬移操作
class Solution {
deque<deque<char>> ans = {{'_'}};
// 右 下 左 上
vector<char> dirCh = {'R','D','L','U'};
public:
vector<string> printKMoves(int K) {
int x = 0, y = 0, d = 0, columns = 1, i = 0;
while(K--)
update(x,y,d,columns);//更新k步的地图
ans[x][y] = dirCh[d];//最后的位置填方向
vector<string> res(ans.size());
string str;
for(auto& dq : ans)
{
str = "";
for(char ch : dq)
str += ch;
res[i++] = str;
}
return res;
}
void update(int& x, int& y, int& d, int& columns)
{
char ch = ans[x][y];
ans[x][y] = (ch=='_' ? 'X' : '_');//反转颜色
d = (ch=='_' ? (d+1)%4 : (d+3)%4);//转向
if(d==0)//R
{
y++;
if(y == ans[x].size())//需要开新的地图，右侧加列
{
for(auto& s : ans)
s.push_back('_');
columns++;
}
}
else if(d==1)//D
{
x++;
if(x == ans.size())//需要开新的地图，下面加行
ans.push_back(deque<char>(columns,'_'));
}
else if(d==2)//L
{
y--;
if(y<0)//需要开新的地图，左侧加列
{
y = 0;
for(auto& s : ans)
s.push_front('_');
columns++;
}
}
else//U
{
x--;
if(x<0)//需要开新的地图，上面加行
{
x = 0;
ans.push_front(deque<char>(columns,'_'));
}
}
}
};
516 ms 49.8 MB
内容总结
以上是互联网集市为您收集整理的程序员面试金典 - 面试题 16.22. 兰顿蚂蚁（deque模拟）全部内容，希望文章能够帮你解决程序员面试金典 - 面试题 16.22. 兰顿蚂蚁（deque模拟）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。