[Swift]LeetCode818. 赛车 | Race Car

概述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)

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 = 3Output: 2Explanation: The shortest instruction sequence is "AA".Your position goes from 0->1->3.

Example 2:input: target = 6Output: 5Explanation: 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.012                 var speed:Int = ele.113                 if pos == target {return res}14                 var newPos:Int = pos + speed15                 var newSpeed:Int = speed * 216                 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 = pos23                 newSpeed = (speed > 0) ? -1 : 124                 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 += 132         }33         return -134     }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 = 010         while !queue.isEmpty {11             for i in 0...queue.count - 1 {12                 let cur = queue.dequeue()!13                 if cur.0 == target {14                     return level15                 }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 += 132         }33         return -134     }35 }36 37 public struct Queue<T> {38     fileprivate var array = [T]()39     40     public var isEmpty: Bool {41         return array.isEmpty42     }43     44     public var count: Int {45         return array.count46     }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 nil55         } else {56             return array.removeFirst()57         }58     }59     60     public var front: T? {61         return array.first62     }63     64 }

总结

以上是内存溢出为你收集整理的[Swift]LeetCode818. 赛车 | Race Car全部内容，希望文章能够帮你解决[Swift]LeetCode818. 赛车 | Race Car所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。