Skip to content

Latest commit

 

History

History
187 lines (148 loc) · 5.33 KB

README.md

File metadata and controls

187 lines (148 loc) · 5.33 KB

1041. 困于环中的机器人

English Version

题目描述

在无限的平面上，机器人最初位于 (0, 0) 处，面朝北方。注意:

  • 北方向 是y轴的正方向。
  • 南方向 是y轴的负方向。
  • 东方向 是x轴的正方向。
  • 西方向 是x轴的负方向。

机器人可以接受下列三条指令之一：

  • "G"：直走 1 个单位
  • "L"：左转 90 度
  • "R"：右转 90 度

机器人按顺序执行指令 instructions，并一直重复它们。

只有在平面中存在环使得机器人永远无法离开时，返回 true。否则，返回 false。

 

示例 1：

输入：instructions = "GGLLGG"
输出：true
解释：机器人最初在(0,0)处，面向北方。
“G”:移动一步。位置:(0,1)方向:北。
“G”:移动一步。位置:(0,2).方向:北。
“L”:逆时针旋转90度。位置:(0,2).方向:西。
“L”:逆时针旋转90度。位置:(0,2)方向:南。
“G”:移动一步。位置:(0,1)方向:南。
“G”:移动一步。位置:(0,0)方向:南。
重复指令，机器人进入循环:(0,0)——>(0,1)——>(0,2)——>(0,1)——>(0,0)。
在此基础上，我们返回true。

示例 2：

输入：instructions = "GG"
输出：false
解释：机器人最初在(0,0)处，面向北方。
“G”:移动一步。位置:(0,1)方向:北。
“G”:移动一步。位置:(0,2).方向:北。
重复这些指示，继续朝北前进，不会进入循环。
在此基础上，返回false。

示例 3：

输入：instructions = "GL"
输出：true
解释：机器人最初在(0,0)处，面向北方。
“G”:移动一步。位置:(0,1)方向:北。
“L”:逆时针旋转90度。位置:(0,1).方向:西。
“G”:移动一步。位置:(- 1,1)方向:西。
“L”:逆时针旋转90度。位置:(- 1,1)方向:南。
“G”:移动一步。位置:(- 1,0)方向:南。
“L”:逆时针旋转90度。位置:(- 1,0)方向:东方。
“G”:移动一步。位置:(0,0)方向:东方。
“L”:逆时针旋转90度。位置:(0,0)方向:北。
重复指令，机器人进入循环:(0,0)——>(0,1)——>(- 1,1)——>(- 1,0)——>(0,0)。
在此基础上，我们返回true。

 

提示：

  • 1 <= instructions.length <= 100
  • instructions[i] 仅包含 'G', 'L', 'R'

解法

定义 cur 表示初始方向（上），值为 0，cur + 1，cur + 2，cur + 3 分别表示 左、下、右。

direction[4] 分别表示机器人在四个方向上行走的距离。

只要机器人最后的方向与初始方向 0 不一样，或者最后回到原点，返回 true。

Python3

class Solution:
    def isRobotBounded(self, instructions: str) -> bool:
        cur, direction = 0, [0] * 4
        for ins in instructions:
            if ins == 'L':
                cur = (cur + 1) % 4
            elif ins == 'R':
                cur = (cur + 3) % 4
            else:
                direction[cur] += 1
        return cur != 0 or (
            direction[0] == direction[2] and direction[1] == direction[3]
        )

Java

class Solution {
    public boolean isRobotBounded(String instructions) {
        int[] direction = new int[4];
        int cur = 0;
        for (char c : instructions.toCharArray()) {
            if (c == 'L') {
                cur = (cur + 1) % 4;
            } else if (c == 'R') {
                cur = (cur + 3) % 4;
            } else {
                ++direction[cur];
            }
        }
        return cur != 0 || (direction[0] == direction[2] && direction[1] == direction[3]);
    }
}

C++

class Solution {
public:
    bool isRobotBounded(string instructions) {
        vector<int> direction(4);
        int cur = 0;
        for (char c : instructions) {
            if (c == 'L')
                cur = (cur + 1) % 4;
            else if (c == 'R')
                cur = (cur + 3) % 4;
            else
                ++direction[cur];
        }
        return cur != 0 || (direction[0] == direction[2] && direction[1] == direction[3]);
    }
};

Go

func isRobotBounded(instructions string) bool {
	direction := make([]int, 4)
	cur := 0
	for _, ins := range instructions {
		if ins == 'L' {
			cur = (cur + 1) % 4
		} else if ins == 'R' {
			cur = (cur + 3) % 4
		} else {
			direction[cur]++
		}
	}
	return cur != 0 || (direction[0] == direction[2] && direction[1] == direction[3])
}

...