• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode818.赛车|RaceCar

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

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

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
记录自己的iOS开发--001【用swift REPL编写程序】发布时间:2022-07-14
下一篇:
typescript参照C#/java/swift学习小结发布时间:2022-07-14
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap