这是悦乐书的第 281 次更新, 第 298 篇原创
01 看题和准备
今天介绍的是 LeetCode 算法题中 Easy 级别的第 149 题 (顺位题号是 657). 在 2D 平面上有一个从位置(0,0) 开始的机器人. 给定其移动序列, 判断该机器人在完成移动后是否在 (0,0) 处结束. 移动序列由字符串表示, 字符 move [i]表示其第 i 个移动. 有效移动是 R(右),L(左),U(上)和 D(下). 如果机器人在完成所有移动后返回原点, 则返回 true. 否则, 返回 false.
注意: 机器人的 "朝向" 无关紧要. "R" 将始终使机器人向右移动一次,"L" 将始终向左移动一次等. 此外, 假设每次移动机器人的移动幅度相同.
例如:
输入:"UD"
输出: true
说明: 机器人向上移动一次, 然后向下移动一次. 所有动作都具有相同的幅度, 因此它最终位于它开始的原点. 因此, 我们返回 true.
输入:"LL"
输出: false
说明: 机器人向左移动两次. 它最终在原点的左边有两个 "moves". 我们返回 false, 因为它在移动结束时不在原点.
本次解题使用的开发工具是 eclipse,jdk 使用的版本是 1.8, 环境是 win7 64 位系统, 使用 Java 语言编写和测试.
02 第一种解法
题目的意思是根据给的移动步数, 判断机器人在移动完后是否还在原地. 要想始终在原地, 即向左和向右的步数相等, 并且向上和向下的步数也要相等. 因此, 我们直接使用记数, 将向左, 向右, 向上, 向下的步数都记录下来, 然后判断两两是否相等即可.
- public boolean judgeCircle(String moves) {
- if (moves.length()%2 != 0) {
- return false;
- }
- int L = 0;
- int R = 0;
- int U = 0;
- int D = 0;
- for (int i=0; i<moves.length(); i++) {
- if ("L".equals(moves.charAt(i)+"")) {
- L++;
- } else if ("R".equals(moves.charAt(i)+"")) {
- R++;
- } else if ("U".equals(moves.charAt(i)+"")) {
- U++;
- } else if ("D".equals(moves.charAt(i)+"")) {
- D++;
- }
- }
- return L == R && U == D;
- }
03 第二种解法
对上面的第一种解法, 我们还可以再简化下, 只使用两个临时变量, 因为可以将向左和向右相抵, 将向上和向下相抵, 最后判断这两变量是否等于 0 即可.
- public boolean judgeCircle(String moves) {
- if (moves.length()%2 != 0) {
- return false;
- }
- int x = 0, y = 0;
- for (char ch : moves.toCharArray()) {
- if (ch == 'L') {
- x--;
- } else if(ch == 'R'){
- x++;
- }else if(ch == 'D'){
- y++;
- } else if(ch == 'U'){
- y--;
- }
- }
- return x == 0 && y == 0;
- }
04 小结
此题本质上是一个记数题, 只要理解题目要表达的意思, 一切都很简单.
算法专题目前已日更超过四个月, 算法题文章 149 + 篇, 公众号对话框回复[数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/fd0e09c09883