題目

給你一個在 XY 平面上的 width x height 的網格圖，左下角 的格子為 (0, 0) ，右上角 的格子為 (width - 1, height - 1) 。

網格圖中相鄰格子為四個基本方向之一（"North"，"East"，"South" 和 "West"）。

一個機器人 初始 在格子 (0, 0) ，方向為 "East" 。

機器人可以根據指令移動指定的 步數 。每一步，它可以執行以下操作。

沿著當前方向嘗試 往前一步 。

如果機器人下一步將到達的格子 超出了邊界 ，機器人會 逆時針 轉 90 度，然後再嘗試往前一步。

如果機器人完成了指令要求的移動步數，它將停止移動並等待下一個指令。

請你實現 Robot 類：

Robot(int width, int height) 初始化一個 width x height 的網格圖，機器人初始在 (0, 0) ，方向朝 "East" 。

void move(int num) 給機器人下達前進 num 步的指令。

int[] getPos() 返回機器人當前所處的格子位置，用一個長度為 2 的陣列 [x, y] 表示。

String getDir() 返回當前機器人的朝向，為 "North" ，"East" ，"South" 或者 "West" 。

示例 1：輸入：["Robot", "move", "move", "getPos", "getDir", "move", "move", "move", "getPos", "getDir"]

[[6, 3], [2], [2], [], [], [2], [1], [4], [], []]

輸出：[null, null, null, [4, 0], "East", null, null, null, [1, 2], "West"]

解釋：Robot robot = new Robot(6, 3); // 初始化網格圖，機器人在 (0, 0) ，朝東。

robot.move(2); // 機器人朝東移動 2 步，到達 (2, 0) ，並朝東。

robot.move(2); // 機器人朝東移動 2 步，到達 (4, 0) ，並朝東。

robot.getPos(); // 返回 [4, 0]

robot.getDir(); // 返回 "East"

robot.move(2); // 朝東移動 1 步到達 (5, 0) ，並朝東。

// 下一步繼續往東移動將出界，所以逆時針轉變方向朝北。

// 然後，往北移動 1 步到達 (5, 1) ，並朝北。

robot.move(1); // 朝北移動 1 步到達 (5, 2) ，並朝 北 （不是朝西）。

robot.move(4); // 下一步繼續往北移動將出界，所以逆時針轉變方向朝西。

// 然後，移動 4 步到 (1, 2) ，並朝西。

robot.getPos(); // 返回 [1, 2]

robot.getDir(); // 返回 "West"

提示：2 <= width, height <= 100

1 <= num <= 105

move ，getPos 和 getDir 總共 呼叫次數不超過 104 次。

解題思路分析

1、模擬；時間複雜度O(n)，空間複雜度O(1)

var m = map[int]string{0: "East", 1: "North", 2: "West", 3: "South"}
var dx = []int{1, 0, -1, 0}
var dy = []int{0, 1, 0, -1}

type Robot struct {
   w, h, x, y, dir, total int
}

func Constructor(width int, height int) Robot {
   return Robot{w: width, h: height, total: 2*width + 2*height - 4}
}

func (this *Robot) Step(num int) {
   num = num % this.total
   if num == 0 && this.x == 0 && this.y == 0 && this.dir == 0 {
      this.dir = 3 // 注意特判
   }
   for ; num > 0; num-- {
      newX, newY := this.x+dx[this.dir], this.y+dy[this.dir]
      if 0 <= newX && newX < this.w && 0 <= newY && newY < this.h {
         this.x = newX
         this.y = newY
      } else {
         this.dir = (this.dir + 1) % 4
         this.x = this.x + dx[this.dir]
         this.y = this.y + dy[this.dir]
      }
   }
}

func (this *Robot) GetPos() []int {
   return []int{this.x, this.y}
}

func (this *Robot) GetDir() string {
   return m[this.dir%4]
}

2、預處理；時間複雜度O(n)，空間複雜度O(n)

var m = map[int]string{0: "East", 1: "North", 2: "West", 3: "South"}

type Robot struct {
   arr    [][2]int
   dir    []int
   isMove bool
   index  int
}

func Constructor(width int, height int) Robot {
   arr := make([][2]int, 0)
   dir := make([]int, 0)
   for i := 0; i < width; i++ {
      arr = append(arr, [2]int{i, 0})
      dir = append(dir, 0)
   }
   for i := 1; i < height; i++ {
      arr = append(arr, [2]int{width - 1, i})
      dir = append(dir, 1)
   }
   for i := width - 2; i >= 0; i-- {
      arr = append(arr, [2]int{i, height - 1})
      dir = append(dir, 2)
   }
   for i := height - 2; i > 0; i-- {
      arr = append(arr, [2]int{0, i})
      dir = append(dir, 3)
   }
   dir[0] = 3 // 第0個朝南
   return Robot{arr: arr, dir: dir, isMove: false}
}

func (this *Robot) Step(num int) {
   this.isMove = true
   this.index = (this.index + num) % len(this.arr)
}

func (this *Robot) GetPos() []int {
   return []int{this.arr[this.index][0], this.arr[this.index][1]}
}

func (this *Robot) GetDir() string {
   if this.isMove == false {
      return "East"
   }
   return m[this.dir[this.index]]
}

總結

Medium題目，可以先預處理成陣列計算，也可以模擬計算，但是要注意第一個點的方向