題目

https://leetcode.com/problems/car-fleet/

題解

看了答案

分析

我們首先對(duì)這些車輛按照它們的起始位置降序排序，并且用 (target - position) / speed 計(jì)算出每輛車在不受其余車的影響時(shí)，行駛到終點(diǎn)需要的時(shí)間。對(duì)于相鄰的兩輛車 S 和 F，F 的起始位置大于 S，如果 S 行駛到終點(diǎn)需要的時(shí)間小于等于 F，那么 S 一定會(huì)在終點(diǎn)前追上 F 并形成車隊(duì)。這是因?yàn)樵谧飞?F 之前，S 的行駛速度并不會(huì)減小，而 F 卻有可能因?yàn)樽飞锨懊娴能囕v而速度減小，因此 S 總能在終點(diǎn)前追上 F。

算法

將車輛按照起始位置降序排序后，我們順序掃描這些車輛。如果相鄰的兩輛車，前者比后者行駛到終點(diǎn)需要的時(shí)間短，那么后者永遠(yuǎn)追不上前者，即從后者開始的若干輛車輛會(huì)組成一個(gè)新的車隊(duì)；如果前者不比后者行駛到終點(diǎn)需要的時(shí)間短，那么后者可以在終點(diǎn)前追上前者，并和前者形成車隊(duì)。此時(shí)我們將后者到達(dá)終點(diǎn)的時(shí)間置為前者到達(dá)終點(diǎn)的時(shí)間。

代碼

最近轉(zhuǎn) golang 了…

type Car struct {pos inttime float32 }func carFleet(target int, position []int, speed []int) int {n := len(position)cars := make([]Car, n)for i := 0; i < n; i++ {cars[i].pos = position[i]cars[i].time = float32(target-position[i]) / float32(speed[i])}// sort by timesort.Slice(cars, func(i, j int) bool {return cars[i].pos > cars[j].pos})fmt.Println(cars)// 離得近、所需時(shí)間長(zhǎng) 和 離的遠(yuǎn)、所需時(shí)間短 在一個(gè)車隊(duì)result := 1preTime := cars[0].timefor _, car := range cars {if car.time > preTime {result++preTime = car.time}}return result }

總結(jié)

以上是生活随笔為你收集整理的leetcode 853. Car Fleet | 853. 车队（Golang）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。