[Swift]LeetCode853.车队|CarFleet

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

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

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

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

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

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

N cars are going to the same destination along a one lane road. The destination is target miles away.

Each car i has a constant speed speed[i] (in miles per hour), and initial position position[i] miles towards the target along the road.

A car can never pass another car ahead of it, but it can catch up to it, and drive bumper to bumper at the same speed.

The distance between these two cars is ignored - they are assumed to have the same position.

A car fleet is some non-empty set of cars driving at the same position and same speed. Note that a single car is also a car fleet.

If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.

How many car fleets will arrive at the destination?

Example 1:

Input: target = [2,4,1,1,3]
Output: 3
Explanation:
The cars starting at 10 and 8 become a fleet, meeting each other at 12.
The car starting at 0 doesn't catch up to any other car, so it is a fleet by itself.
The cars starting at 5 and 3 become a fleet, meeting each other at 6.
Note that no other cars meet these fleets before the destination, so the answer is 3.

Note:

0 <= N <= 10 ^ 4
0 < target <= 10 ^ 6
0 < speed[i] <= 10 ^ 6
0 <= position[i] < target
All initial positions are different.

N 辆车沿着一条车道驶向位于 target 英里之外的共同目的地。

每辆车 i 以恒定的速度 speed[i] （英里/小时），从初始位置 position[i] （英里）沿车道驶向目的地。

一辆车永远不会超过前面的另一辆车，但它可以追上去，并与前车以相同的速度紧接着行驶。

此时，我们会忽略这两辆车之间的距离，也就是说，它们被假定处于相同的位置。

车队是一些由行驶在相同位置、具有相同速度的车组成的非空集合。注意，一辆车也可以是一个车队。

即便一辆车在目的地才赶上了一个车队，它们仍然会被视作是同一个车队。

会有多少车队到达目的地?

示例：

输入：target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
输出：3
解释：
从 10 和 8 开始的车会组成一个车队，它们在 12 处相遇。
从 0 处开始的车无法追上其它车，所以它自己就是一个车队。
从 5 和 3 开始的车会组成一个车队，它们在 6 处相遇。
请注意，在到达目的地之前没有其它车会遇到这些车队，所以答案是 3。

提示：

0 <= N <= 10 ^ 4
0 < target <= 10 ^ 6
0 < speed[i] <= 10 ^ 6
0 <= position[i] < target
所有车的初始位置各不相同。

232ms

 1 class Solution {
 2 
 3     func carFleet(_ target: Int, _ position: [Int], _ speed: [Int]) -> Int {
 4         let cars = zip(position, speed).map{Car(position: $0.0, speed: $0.1)}.sorted{$0.position > $1.position}
 5 
 6         var fleets = 0
 7         var currentTime = 0.0
 8         for c in cars {
 9             let carTime = c.time(toTarget: target)
10             if carTime > currentTime {
11                 currentTime = carTime
12                 fleets += 1
13             }
14         }
15         return fleets
16     }
17 }
18 
19 struct Car {
20     let position : Int
21     let speed : Int
22     
23     func time(toTarget target: Int) -> Double {
24         return Double(target - position) / Double(speed)
25     }
26 }

240ms

 1 class Solution {
 2     func carFleet(_ target: Int, _ position: [Int], _ speed: [Int]) -> Int {
 3         guard position.count == speed.count else { return -1 }
 4         let n = position.count
 5         var cars = [Car]()
 6         for i in 0..<n {
 7             cars.append(Car(position: position[i], time: (Float)(target - position[i]) / Float(speed[i])))
 8         }
 9         cars.sort(by:{
10             $0.position < $1.position
11         })
12         var t = n - 1
13         var ret = 0
14         while (t > 0) {
15             if cars[t].time < cars[t-1].time {
16                 ret += 1
17             } else {
18                 cars[t-1].time = cars[t].time
19             }
20             t -= 1
21         }
22         return ret + (t == 0 ? 1: 0)
23     }
24     
25     struct Car {
26         let position: Int
27         var time: Float
28     }
29 }

Runtime: 248 ms

Memory Usage: 19.4 MB

 1 class Solution {
 2     func carFleet(_ target: Int, _ position: [Int], _ speed: [Int]) -> Int {
 3         var map:[Int:Double] = [Int:Double]()
 4         for i in 0..<position.count
 5         {
 6            map[target - position[i]] = Double(speed[i])   
 7         }
 8         var res:Int = 0
 9         var cur:Double = 0.0
10         var nums = Set(map.keys).sorted(by:<)
11         for key in nums
12         {
13             var time:Double = Double(key) / map[key,default:0]
14             if time > cur
15             {
16                 cur = time
17                 res += 1
18             }
19         }
20         return res
21     }
22 }

252ms

 1 class Solution {
 2     func carFleet(_ target: Int, _ position: [Int], _ speed: [Int]) -> Int {
 3         var orders: [Int: Double] = [:]
 4         for (index, pos) in position.enumerated() {
 5             let steps = Double(target - pos) / Double(speed[index])
 6             orders[pos] = steps
 7         }
 8         
 9         var stack: [Double] = []
10         for pair in orders.sorted(by: { $0.key > $1.key }) {
11             if stack.isEmpty {
12                 stack.append(pair.value)
13             } else {
14                 if stack.last! < pair.value {
15                     stack.append(pair.value)
16                 }
17             }
18         }
19         return stack.count
20     }
21 }

280ms

 1 class Solution {
 2     func carFleet(_ target: Int, _ position: [Int], _ speed: [Int]) -> Int {
 3         var times: [Int: Double] = [:]
 4         let n = position.count
 5         for i in 0..<n {
 6             let time = Double(target - position[i])/Double(speed[i])
 7             times[position[i]] = time
 8         }
 9         var res = 0
10         var prevTime = 0.0
11         for (_, time) in times.sorted(by: { $0.key > $1.key }) {
12             if time > prevTime {
13                 res += 1
14                 prevTime = time
15             }
16         }
17         return res
18     }
19 }

288ms

 1 class Solution {
 2     func carFleet(_ target: Int, _ position: [Int], _ speed: [Int]) -> Int {
 3         var fleets = 0
 4         var max = -1.0
 5 
 6         var distribution = [Double](repeating: -1, count: target+1)
 7 
 8         for i in 0..<position.count {
 9             distribution[position[i]] = Double(target - position[i])/Double(speed[i])
10         }
11 
12         var i = distribution.count - 1
13         while i>=0 {
14             if distribution[i] > max {
15                 max = distribution[i]
16                 fleets += 1
17             }
18             i -= 1
19         }
20         return fleets
21     }
22 }