专栏首页Michael阿明学习之路程序员面试金典 - 面试题 16.22. 兰顿蚂蚁(deque模拟)

程序员面试金典 - 面试题 16.22. 兰顿蚂蚁(deque模拟)

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 984. 不含 AAA 或 BBB 的字符串(贪心)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/string-without-aaa-or-bbb ...

    Michael阿明
  • LeetCode 831. 隐藏个人信息

    定义名称 name 是长度大于等于 2 (length ≥ 2),并且只包含小写字母 a-z 和大写字母 A-Z 的字符串。

    Michael阿明
  • LeetCode 187. 重复的DNA序列(哈希/位运算)

    所有 DNA 都由一系列缩写为 A,C,G 和 T 的核苷酸组成,例如:“ACGAATTCCG”。 在研究 DNA 时,识别 DNA 中的重复序列有时会对研究...

    Michael阿明
  • LeetCode 216. Combination Sum III(DFS)

    题意:从1-9中选出k个数之和等于n,这个k个数不能有相同的,输出所有可能的k个数字的集合,结果也不能重复

    ShenduCC
  • 【CodeForces 699A】Launch of Collider

    饶文津
  • 牛客网平台常州大学新生寒假训练会试

    Zoctopus
  • Leetcode【54、59、885】

    这道题做法很直接,就是从最外层到最内层一层一层按照顺时针螺旋输出各个数字即可。如下图所示:

    echobingo
  • Spring Boot 2.X(十四):日志功能 Logback

    Logback 是由 SLF4J 作者开发的新一代日志框架,用于替代 log4j。

    朝雾轻寒
  • Spring Boot 2.X(十四):日志功能 Logback

    Logback 是由 SLF4J 作者开发的新一代日志框架,用于替代 log4j。

    朝雾轻寒
  • 【CCF】最小差值

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk

扫码关注云+社区

领取腾讯云代金券