[Swift]LeetCode874.模拟行走机器人|WalkingRobotSimulation

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10600487.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

A robot on an infinite grid starts at point (0, 0) and faces north. The robot can receive one of three possible types of commands:

-2: turn left 90 degrees
-1: turn right 90 degrees
1 <= x <= 9: move forward x units

Some of the grid squares are obstacles.

The i-th obstacle is at grid point (obstacles[i][0], obstacles[i][1])

If the robot would try to move onto them, the robot stays on the previous grid square instead (but still continues following the rest of the route.)

Return the square of the maximum Euclidean distance that the robot will be from the origin.

Example 1:

Input: commands = []
Output: 25
Explanation: robot will go to (3, 4)

Example 2:

Input: commands = [[2,4]]
Output: 65
Explanation: robot will be stuck at (1, 4) before turning left and going to (1, 8)

Note:

0 <= commands.length <= 10000
0 <= obstacles.length <= 10000
-30000 <= obstacle[i][0] <= 30000
-30000 <= obstacle[i][1] <= 30000
The answer is guaranteed to be less than 2 ^ 31.

机器人在一个无限大小的网格上行走，从点 (0, 0) 处开始出发，面向北方。该机器人可以接收以下三种类型的命令：

-2：向左转 90 度
-1：向右转 90 度
1 <= x <= 9：向前移动 x 个单位长度

在网格上有一些格子被视为障碍物。

第 i 个障碍物位于网格点 (obstacles[i][0], obstacles[i][1])

如果机器人试图走到障碍物上方，那么它将停留在障碍物的前一个网格方块上，但仍然可以继续该路线的其余部分。

返回从原点到机器人的最大欧式距离的平方。

示例 1：

输入: commands = [4,-1,3], obstacles = []
输出: 25
解释: 机器人将会到达 (3, 4)

示例 2：

输入: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
输出: 65
解释: 机器人在左转走到 (1, 8) 之前将被困在 (1, 4) 处

提示：

0 <= commands.length <= 10000
0 <= obstacles.length <= 10000
-30000 <= obstacle[i][0] <= 30000
-30000 <= obstacle[i][1] <= 30000
答案保证小于 2 ^ 31

376ms

 1 class Solution {
 2     func robotSim(_ commands: [Int], _ obstacles: [[Int]]) -> Int {
 3         let obstacles = obstacles.reduce(into: Set<Int>()){$0.insert($1[0]*100_000+$1[1])}
 4         
 5         var x = 0; var y = 0
 6         var dx = 0; var dy = 1
 7         var maxDist = 0
 8         
 9         for command in commands {
10             switch command {
11             case -2:
12                 swap(&dx,&dy); dx = -dx; break
13             case -1:
14                 swap(&dx,&dy); dy = -dy; break
15             default:
16                 maxDist = max(maxDist,x*x+y*y)
17                 for _ in 0..<command {
18                     if !obstacles.contains((x+dx)*100_000+y+dy) {
19                         x += dx; y += dy
20                     } else {
21                         break
22                     }
23                 }
24             }
25         }
26         
27         maxDist = max(maxDist,x*x+y*y)
28         return maxDist
29     }
30 }

Runtime: 424 ms

Memory Usage: 19.4 MB

 1 class Solution {
 2     func robotSim(_ commands: [Int], _ obstacles: [[Int]]) -> Int {
 3         var set:Set<String> = Set<String>()
 4         for obs in obstacles
 5         {
 6             set.insert(String(obs[0]) + " " + String(obs[1]))
 7         }
 8         var dirs:[[Int]] = [[0, 1],[1, 0],[0, -1],[-1, 0]]
 9         var d:Int = 0
10         var x:Int = 0
11         var y:Int = 0
12         var result:Int = 0
13         for c in commands
14         {
15             if c == -1
16             {
17                 d += 1
18                 if d == 4 
19                 {
20                     d = 0
21                 }
22             }
23             else if c == -2
24             {
25                 d -= 1
26                 if d == -1
27                 {
28                     d = 3
29                 }
30             }
31             else
32             {
33                 var num = c
34                 while(num-- > 0 && !set.contains(String(x + dirs[d][0]) + " " + String(y + dirs[d][1])))
35                 {
36                     x += dirs[d][0]
37                     y += dirs[d][1]
38                 }
39             }
40              result = max(result, x * x + y * y)
41         }
42         return result
43     }
44 }
45 
46 /*扩展Int类，实现自增++、自减--运算符*/
47 extension Int{
48     //后缀--:先执行表达式后再自减
49     static postfix func --(num:inout Int) -> Int {
50         //输入输出参数num
51         let temp = num
52         //num减1
53         num -= 1
54          //返回减1前的数值
55         return temp
56     }
57 }

428ms

 1 class Solution {
 2     func robotSim(_ commands: [Int], _ obstacles: [[Int]]) -> Int {
 3         var current = (0, 0)
 4         var directs = [(0, 1), (1, 0), (0, -1), (-1, 0) ]
 5         var i = 0
 6         var result = 0
 7         var obstacles = Set<[Int]>(obstacles)
 8         for command in commands {
 9             if command == -1 {
10                 i = (i + 1) % 4
11             } else if command == -2 {
12                 i = (i + 3) % 4
13             } else {
14                 for _ in 0..<command {
15                     let nextStep = (current.0 + (directs[i].0 * 1), current.1 + (directs[i].1 * 1))
16                     if !obstacles.contains([nextStep.0, nextStep.1]) {
17                         current = nextStep
18                         result = max(result, current.0 * current.0 + current.1 * current.1)
19                     } else {
20                         break
21                     }
22                 }
23             }
24         }
25         return result
26     }
27 }

436ms

 1 class Solution {
 2     func robotSim(_ commands: [Int], _ obstacles: [[Int]]) -> Int {
 3     var set = Set<[Int]>()
 4     for p in obstacles {
 5         set.insert(p)
 6     }
 7     var pos = [0, 0]
 8     var x = 0
 9     var y = 1
10     var maxDis = 0
11     
12     for c in commands {
13         //turn right 90 degree
14         if c == -1 {
15             if x == 0 {
16                 x = y
17                 y = 0
18             }
19             else {
20                 y = -x
21                 x = 0
22             }
23         }
24         //turn left 90 degree
25         else if c == -2 {
26             if x == 0 {
27                 x = -y
28                 y = 0
29             }
30             else {
31                 y = x
32                 x = 0
33             }
34         }
35         else {
36             for _ in 0..<c {
37                 pos[0] += 1 * x
38                 pos[1] += 1 * y
39                 if set.contains(pos) {
40                     pos[0] -= 1 * x
41                     pos[1] -= 1 * y
42                     break
43                 }
44             }
45         }
46         maxDis = max(maxDis, pos[0] * pos[0] + pos[1] * pos[1])
47     }
48     return maxDis
49   }
50 }

444ms

 1 class Solution {
 2     func robotSim(_ commands: [Int], _ obstacles: [[Int]]) -> Int {
 3         var obst = Set<String>()
 4         for o in obstacles {
 5             obst.insert("\(o[0])-\(o[1])")
 6         }
 7         var x = 0
 8         var y = 0
 9         var res = 0
10         let dirX = [0, 1, 0, -1]
11         let dirY = [1, 0, -1, 0]
12         var dir = 0
13         for c in commands {
14             if c == -2 {
15                 dir -= 1
16                 if dir < 0 { dir = 3 }
17             } else if c == -1 {
18                 dir += 1
19                 dir %= 4
20             } else {
21                 inner: for _ in 1...c {
22                     let newX = x + dirX[dir]
23                     let newY = y + dirY[dir]
24                     if !obst.contains("\(newX)-\(newY)") {
25                         x = newX
26                         y = newY
27                     } else {
28                         break inner
29                     }
30                 }
31                 res = max(res, x * x + y * y)
32             }
33         }
34         return res
35     }
36 }

456ms

 1 class Solution {
 2     func robotSim(_ commands: [Int], _ obstacles: [[Int]]) -> Int {
 3         var direction = 0
 4         var coordinate = (0, 0)
 5         var result = 0
 6         var obstacleSet = Set<String>()
 7         for obstacle in obstacles {
 8             obstacleSet.insert("\(obstacle[0]) \(obstacle[1])")
 9         }
10         
11         for command in commands {
12             if command == -1 {
13                 direction += 1
14                 if direction == 4 {
15                     direction = 0
16                 }
17             } else if command == -2 {
18                 direction -= 1
19                 if direction == -1 {
20                     direction = 3
21                 }
22             } else if command >= 1 && command <= 9 {
23                 var bestMovement = 0
24                 for i in 1...command {
25                     var targetPoint = ""
26                     if direction == 0 {
27                         targetPoint = "\(coordinate.0) \(coordinate.1 + i)"
28                     } else if direction == 1 {
29                         targetPoint = "\(coordinate.0 + i) \(coordinate.1)"
30                     } else if direction == 2 {
31                         targetPoint = "\(coordinate.0) \(coordinate.1 - i)"
32                     } else if direction == 3 {
33                         targetPoint = "\(coordinate.0 - i) \(coordinate.1)"
34                     }
35                     
36                     if obstacleSet.contains(targetPoint) {
37                         break
38                     } else {
39                         bestMovement = i
40                     }
41                 }
42                 
43                 if direction == 0 {
44                     coordinate.1 += bestMovement
45                 } else if direction == 1 {
46                     coordinate.0 += bestMovement
47                 } else if direction == 2 {
48                     coordinate.1 -= bestMovement
49                 } else if direction == 3 {
50                     coordinate.0 -= bestMovement
51                 }
52                 result = max(result, coordinate.0 * coordinate.0 + coordinate.1 * coordinate.1)
53             }
54         }
55         
56         return result
57     }
58 }

496ms

 1 class Solution {
 2   func robotSim(_ commands: [Int], _ obstacles: [[Int]]) -> Int {
 3     let obstaSet = Set(obstacles)
 4     
 5     var maxDist = 0
 6     
 7     var pos = [0,0]
 8     var posI = 1
 9     var dir = 1
10     
11     for command in commands {
12       if command == -2 {
13         if posI == 1 {
14           dir *= -1
15         }
16         posI ^= 1
17       } else if command == -1 {
18         if posI == 0 {
19           dir *= -1
20         }
21         posI ^= 1
22       } else {
23         for _ in 1...command {
24           pos[posI] += dir
25           
26           if obstaSet.contains(pos) {
27             pos[posI] -= dir
28             break
29           }
30         }
31         
32         maxDist = max(maxDist, pos[0] * pos[0] + pos[1] * pos[1])
33       }
34     }
35     
36     return maxDist
37   }
38 }

940ms

 1 class Solution {
 2     func robotSim(_ commands: [Int], _ obstacles: [[Int]]) -> Int {
 3         enum MoveType{
 4             case left
 5             case right
 6             case up
 7             case down
 8         }
 9         func modifi(_ type: inout MoveType, _ num: Int) {
10             if num == -1 {
11                 switch type {
12                 case .down:
13                     type = .left
14                 case .up:
15                     type = .right
16                 case .left:
17                     type = .up
18                 case .right:
19                     type = .down
20                 }
21             }
22             if num == -2 {
23                 switch type {
24                 case .down:
25                     type = .right
26                 case .up:
27                     type = .left
28                 case .left:
29                     type = .down
30                 case .right:
31                     type = .up
32                 }
33             }
34         }
35         var type: MoveType = .up
36         var x = 0
37         var y = 0
38         let set: Set<String> = Set(obstacles.map({"\($0[0])=\($0[1])"}))
39         var result = 0
40         
41         for i in (0..<commands.count) {
42             let temp = commands[i]
43             if temp == -1 || temp == -2 {
44                 modifi(&type, temp)
45             }else {
46                 switch type {
47                 case .left:
48                     for _ in (1...temp) {
49                         let move = "\(x - 1)=\(y)"
50                         if set.contains(move) {
51                             break
52                         }else {
53                             x -= 1
54                         }
55                     }
56                 case .right:
5