OJ-leetcode-657.机器人能否回到原点（简单模拟）

喜欢ヅ旅行 2022-12-01 15:49 91阅读 0赞

**目录**

题目

思路1

代码

结果

思路2

代码

结果

更优秀题解

提升笔记

优化

代码

结果

全部代码

--------------------

# [题目][Link 1] #

在二维平面上，有一个机器人从原点 (0, 0) 开始。给出它的移动顺序，判断这个机器人在完成移动后是否在 (0, 0) 处结束。

移动顺序由字符串表示。字符 move\[i\] 表示其第 i 次移动。机器人的有效动作有 R（右），L（左），U（上）和 D（下）。如果机器人在完成所有动作后返回原点，则返回 true。否则，返回 false。

注意：机器人“面朝”的方向无关紧要。 “R” 将始终使机器人向右移动一次，“L” 将始终向左移动等。此外，假设每次移动机器人的移动幅度相同。

示例 1:

输入: "UD"  
输出: true  
解释：机器人向上移动一次，然后向下移动一次。所有动作都具有相同的幅度，因此它最终回到它开始的原点。因此，我们返回 true。

示例 2:

输入: "LL"  
输出: false  
解释：机器人向左移动两次。它最终位于原点的左侧，距原点有两次 “移动” 的距离。我们返回 false，因为它在移动结束时没有返回原点。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/robot-return-to-origin

# 思路1 #

字符统计

## 代码 ##

bool judgeCircle(string moves) {
    	int u = count(moves.begin(), moves.end(), 'U');
    	int d = count(moves.begin(), moves.end(), 'D');
    	int l = count(moves.begin(), moves.end(), 'L');
    	int r = count(moves.begin(), moves.end(), 'R');
    	if (u == d&&l == r)return true;
    	return false;
    }

## 结果 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70][] 效率低

# 思路2 #

简单模拟，我做过包含方向的模拟，更复杂一点，这个记录各个方向的步数即可，判断是否相等。或者减少变量，有加有减。

## 代码 ##

bool judgeCircle(string moves) {
    	int u,d,l,r;
    	u = d = l = r = 0;
    	for (char move : moves)
    	{
    		if (move == 'U')u += 1;
    		if (move == 'D')d += 1;
    		if (move == 'L')l += 1;
    		if (move == 'R')r += 1;
    	}
    	if (u == d&&l == r)return true;
    	return false;
    }

## 结果 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 1][] 效率稍高

我以为这样足够击败70%以上了，没想到这么低。找了半天，找到了更优秀的题解。

我的问题是变量多，增强for循环效率低。

# [更优秀题解][Link 2] #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 2][] 优秀题解内容

木桶原理进行统计，利用ASCLL表。

可优化部分:moves.length()的值不变，放到for循环外面更好。

# 提升笔记 #

1.switch效率低

2.统计时记得木桶原理

# 优化 #

## 代码 ##

class Solution {
    public:
    	bool judgeCircle(string moves) {
    		int count[86] = { 0 };
    		for (int i=moves.length();i>-1;--i)
    		{
    			++count[moves[i]];
    		}
    		return count['L'] == count['R'] && count['U'] == count['D'];
    	}
    };

##  结果 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 3][] 用时有问题

结果证明，leetcode用时有点问题呀，明显优化了，时间竟然比优秀题解翻倍了。。。

# 全部代码 #

#include<iostream>
    #include<vector>
    #include<string>
    #include<iostream>
    using namespace std;
    class Solution {
    public:
    	//字符统计
    	/*
    	bool judgeCircle(string moves) {
    		int u = count(moves.begin(), moves.end(), 'U');
    		int d = count(moves.begin(), moves.end(), 'D');
    		int l = count(moves.begin(), moves.end(), 'L');
    		int r = count(moves.begin(), moves.end(), 'R');
    		cout << u << " " << d << " " << l << " " << r << endl;
    		if (u == d&&l == r)return true;
    		return false;
    	}*/
    	//模拟
    	/*bool judgeCircle(string moves) {
    		int u,d,l,r;
    		u = d = l = r = 0;
    		for (char move : moves)
    		{
    			if (move == 'U')u += 1;
    			if (move == 'D')d += 1;
    			if (move == 'L')l += 1;
    			if (move == 'R')r += 1;
    		}
    		cout << u << " " << d << " " << l << " " << r << endl;
    		if (u == d&&l == r)return true;
    		return false;
    	}*/
    	//优化
    	bool judgeCircle(string moves) {
    		int count[86] = { 0 };
    		for (int i=moves.length();i>-1;--i)
    		{
    			++count[moves[i]];
    		}
    		cout << count['L'] << " " << count['R'] << " " << count['U'] << " " << count['D'] << endl;
    		return count['L'] == count['R'] && count['U'] == count['D'];
    	}
    };
    int main()
    {
    
    	Solution s;
    	cout << s.judgeCircle("LLRRUD");
    	return 0;
    }

更多内容：[OJ网站题目分类，分难度整理笔记（leetcode、牛客网）][OJ_leetcode]

喜欢本文的请动动小手点个赞，收藏一下，有问题请下方评论，转载请注明出处，并附有原文链接，谢谢！如有侵权，请及时联系。如果您感觉有所收获，自愿打赏，可选择支付宝18833895206（小于），您的支持是我不断更新的动力。

[Link 1]: https://leetcode-cn.com/problems/robot-return-to-origin
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70]: /images/20221123/5907c1ea4ae0463fb1c87e8a384a52fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 1]: /images/20221123/3bbf469c613d4fd0a6b527d87699b3a5.png
[Link 2]: https://leetcode-cn.com/problems/robot-return-to-origin/solution/cji-bai-9968-100-by-yudou/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 2]: /images/20221123/ad0a13c70c054e9f8d61c294a6765f61.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 3]: /images/20221123/fa7f909ede694010b910276d88571d71.png
[OJ_leetcode]: https://blog.csdn.net/lady_killer9/article/details/108273799