本篇為LeetCode上演算法的簡單問題，Robot Return to Origin。
題目如下：
There is a robot starting at position (0, 0), the origin, on a 2D plane. Given a sequence of its moves, judge if this robot ends up at (0, 0) after it completes its moves.
The move sequence is represented by a string, and the character moves[i] represents its ith move. Valid moves are R (right), L (left), U (up), and D (down). If the robot returns to the origin after it finishes all of its moves, return true. Otherwise, return false.
Note: The way that the robot is "facing" is irrelevant. "R" will always make the robot move to the right once, "L" will always make it move left, etc. Also, assume that the magnitude of the robot's movement is the same for each move.
Example 1:Input: "UD" Output: true Explanation: The robot moves up once, and then down once. All moves have the same magnitude, so it ended up at the origin where it started. Therefore, we return true.
Example 2:Input: "LL" Output: false Explanation: The robot moves left twice. It ends up two "moves" to the left of the origin. We return false because it is not at the origin at the end of its moves.
一個機器人從2D平片的位置(0, 0)開始移動，輸入一連串字串代表移動的方向，分別為R(右)，L(左)，U(上)，D(下)，如果最後位置回到(0, 0)，返回true，否則返回false。另外不考慮面向的問題。
解法順序為，給定原點起始位置x = 0, y = 0，x代表左右移動值，y代表上下移動值。然後迴圈代表移動方向的輸入字串參數，並判斷每個字的移動方向，若是往上(U)則y + 1，往下(D)則y - 1，往右(R)則x + 1，往左(L)則x - 1。最後在判斷x及y是否為0。
下面是一開始的解法。
public static boolean judgeCircle(String moves) {
int x = 0, y = 0;
for (char move : moves.toCharArray()) {
if(move == 'U') { y++; }
if(move == 'D') { y--; }
if(move == 'R') { x++; }
if(move == 'L') { x--; }
}
return x == 0 && y == 0;
}
但上面的效能表現僅排名在63%左右。
參考討論區的答案修改如下。
public static boolean judgeCircle(String moves) {
int x = 0, y = 0;
for(char c : moves.toCharArray()) {
switch(c) {
case 'U': y++;break;
case 'D': y--;break;
case 'R': x++;break;
case 'L': x--;break;
}
}
return x == 0 && y == 0;
}
這個表現排名在93%。從這題學到如果在迴圈中進行邏輯判斷時，如果每一個判斷的動作是互斥的，則應該在動作完成後停止往下繼續判斷，如此可減少一些不必要的計算。
不過一開始我想用狀態模式(State Pattern)來寫，因為符合依不同的狀態而進行不同的行為，及很多if else的狀況。
public class App {
public static void main(String[] args) {
System.out.println(judgeCircle("RRRRLLLLUUD"));
}
public static boolean judgeCircle(String moves) {
int x = 0; int y = 0;
Postion postion = new Postion(x, y);
for (char move : moves.toCharArray()) {
postion.move(move);
}
return postion.getX() == 0 && postion.getY() == 0;
}
}
class Postion {
int x, y = 0;
public Postion(int x, int y) {
this.x = x;
this.y = y;
}
public void move(char c) {
MoveEnum.genMove(c).move(this);
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
}
interface Move {
public void move(Postion postion);
class Up implements Move {
@Override
public void move(Postion postion) {
postion.setY(postion.getY() + 1);
}
}
class Down implements Move {
@Override
public void move(Postion postion) {
postion.setY(postion.getY() - 1);
}
}
class Right implements Move {
@Override
public void move(Postion postion) {
postion.setX(postion.getX() + 1);
}
}
class Left implements Move {
@Override
public void move(Postion postion) {
postion.setX(postion.getX() - 1);
}
}
}
enum MoveEnum {
UP('U'), DOWN('D'), RIGHT('R'), LEFT('L');
private char move;
private MoveEnum(char move) {
this.move = move;
}
public static Move genMove(char c) {
switch (getEnum(c)) {
case UP: return new Move.Up();
case DOWN: return new Move.Down();
case RIGHT: return new Move.Right();
case LEFT: return new Move.Left();
}
return null;
}
public static MoveEnum getEnum(char c) {
for (MoveEnum e : MoveEnum.values()) {
if (e.move == c) {
return e;
}
}
return null;
}
}
假如今天多了深度z軸的方向，例如IN(I)代表往內移動，OUT(O)代表往外移動，則修改如下。
public class App {
public static void main(String[] args) {
System.out.println(judgeCircle("IIOODDURLRI"));
}
public static boolean judgeCircle(String moves) {
int x = 0, y = 0, z = 0;
Postion postion = new Postion(x, y, z);
for (char move : moves.toCharArray()) {
postion.move(move);
}
return postion.getX() == 0 && postion.getY() == 0 && postion.getZ() == 0;
}
}
class Postion {
int x, y, z = 0;
public Postion(int x, int y) {
this.x = x;
this.y = y;
}
public Postion(int x, int y, int z) {
this.x = x;
this.y = y;
this.z = z;
}
public void move(char c) {
MoveEnum.genMove(c).move(this);
}
public int getX() { return x; }
public void setX(int x) { this.x = x; }
public int getY() { return y; }
public void setY(int y) { this.y = y; }
public int getZ() { return z; }
public void setZ(int z) { this.z = z; }
}
interface Move {
public void move(Postion postion);
class Up implements Move {
@Override
public void move(Postion postion) {
postion.setY(postion.getY() + 1);
}
}
class Down implements Move {
@Override
public void move(Postion postion) {
postion.setY(postion.getY() - 1);
}
}
class Right implements Move {
@Override
public void move(Postion postion) {
postion.setX(postion.getX() + 1);
}
}
class Left implements Move {
@Override
public void move(Postion postion) {
postion.setX(postion.getX() - 1);
}
}
class In implements Move {
@Override
public void move(Postion postion) {
postion.setZ(postion.getZ() - 1);
}
}
class Out implements Move {
@Override
public void move(Postion postion) {
postion.setZ(postion.getZ() + 1);
}
}
}
enum MoveEnum {
UP('U'), DOWN('D'), RIGHT('R'), LEFT('L'), IN('I'), OUT('O');
private char move;
private MoveEnum(char move) {
this.move = move;
}
public static Move genMove(char c) {
switch (getEnum(c)) {
case UP: return new Move.Up();
case DOWN: return new Move.Down();
case RIGHT: return new Move.Right();
case LEFT: return new Move.Left();
case IN: return new Move.In();
case OUT: return new Move.Out();
}
return null;
}
public static MoveEnum getEnum(char c) {
for (MoveEnum e : MoveEnum.values()) {
if (e.move == c) {
return e;
}
}
return null;
}
}
參考：
沒有留言:
張貼留言