[Swift]LeetCode818. 赛车 | Race Car
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10565497.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
Your car starts at position 0 and speed +1 on an infinite number line. (Your car can go into negative positions.)
Your car drives automatically according to a sequence of instructions A (accelerate) and R (reverse).
When you get an instruction "A", your car does the following: position += speed, speed *= 2.
When you get an instruction "R", your car does the following: if your speed is positive then speed = -1 , otherwise speed = 1. (Your position stays the same.)
For example, after commands "AAR", your car goes to positions 0->1->3->3, and your speed goes to 1->2->4->-1.
Now for some target position, say the lengthof the shortest sequence of instructions to get there.
Example 1: Input: target = 3 Output: 2 Explanation: The shortest instruction sequence is "AA". Your position goes from 0->1->3.
Example 2: Input: target = 6 Output: 5 Explanation: The shortest instruction sequence is "AAARA". Your position goes from 0->1->3->7->7->6.
Note:
1 <= target <= 10000.
你的赛车起始停留在位置 0，速度为 +1，正行驶在一个无限长的数轴上。（车也可以向负数方向行驶。）
你的车会根据一系列由 A（加速）和 R（倒车）组成的指令进行自动驾驶 。
当车得到指令 "A" 时, 将会做出以下操作： position += speed, speed *= 2。
当车得到指令 "R" 时, 将会做出以下操作：如果当前速度是正数，则将车速调整为 speed = -1 ；否则将车速调整为 speed = 1。 (当前所处位置不变。)
例如，当得到一系列指令 "AAR" 后, 你的车将会走过位置 0->1->3->3，并且速度变化为 1->2->4->-1。
现在给定一个目标位置，请给出能够到达目标位置的最短指令列表的长度。
示例 1: 输入: target = 3 输出: 2 解释: 最短指令列表为 "AA" 位置变化为 0->1->3
示例 2: 输入: target = 6 输出: 5 解释: 最短指令列表为 "AAARA" 位置变化为 0->1->3->7->7->6
说明:
1 <= target（目标位置） <= 10000。
Runtime: 1992 ms
Memory Usage: 33.9 MB
1 class Solution {
2 func racecar(_ target: Int) -> Int {
3 var res:Int = 0
4 var q:[(Int,Int)] = [(0, 1)]
5 var visited:Set<String> = ["0,1"]
6 while(!q.isEmpty)
7 {
8 for i in stride(from:q.count,to:0,by:-1)
9 {
10 var ele = q.removeFirst()
11 var pos:Int = ele.0
12 var speed:Int = ele.1
13 if pos == target {return res}
14 var newPos:Int = pos + speed
15 var newSpeed:Int = speed * 2
16 var key:String = String(newPos) + "," + String(newSpeed)
17 if !visited.contains(key) && newPos > 0 && newPos < (target * 2)
18 {
19 visited.insert(key)
20 q.append((newPos, newSpeed))
21 }
22 newPos = pos
23 newSpeed = (speed > 0) ? -1 : 1
24 key = String(newPos) + "," + String(newSpeed)
25 if !visited.contains(key) && newPos > 0 && newPos < (target * 2)
26 {
27 visited.insert(key)
28 q.append((newPos, newSpeed))
29 }
30 }
31 res += 1
32 }
33 return -1
34 }
35 }2312ms
1 import Foundation
2 class Solution {
3
4 func racecar(_ target: Int) -> Int {
5 var queue = Queue<(Int, Int)>()
6 queue.enqueue((0,1))
7 var visited = Set<String>()
8 visited.insert("0_1")
9 var level = 0
10 while !queue.isEmpty {
11 for i in 0...queue.count - 1 {
12 let cur = queue.dequeue()!
13 if cur.0 == target {
14 return level
15 }
16 let next1 = (cur.0 + cur.1, cur.1 << 1)
17 let key1 = "\(next1.0)_\(next1.1)"
18
19 if !visited.contains(key1) && 0 < next1.0 && next1.0 < target << 1 {
20 queue.enqueue(next1)
21 visited.insert(key1)
22 }
23
24 let next2 = (cur.0, cur.1 > 0 ? -1 : 1)
25 let key2 = "\(next2.0)_\(next2.1)"
26 if !visited.contains(key2) && 0 < next2.0 && next2.0 < target << 1 {
27 queue.enqueue(next2)
28 visited.insert(key2)
29 }
30 }
31 level += 1
32 }
33 return -1
34 }
35 }
36
37 public struct Queue<T> {
38 fileprivate var array = [T]()
39
40 public var isEmpty: Bool {
41 return array.isEmpty
42 }
43
44 public var count: Int {
45 return array.count
46 }
47
48 public mutating func enqueue(_ element: T) {
49 array.append(element)
50 }
51
52 public mutating func dequeue() -> T? {
53 if isEmpty {
54 return nil
55 } else {
56 return array.removeFirst()
57 }
58 }
59
60 public var front: T? {
61 return array.first
62 }
63
64 }