Car Fleet

Q: Car Fleet'in zaman karmaşıklığı nedir?

Konuma göre sıralama O(n log n) sürer ve yığınla yapılan geçiş O(n) sürer; bu nedenle toplam süre O(n log n) , bellek kullanımı ise O(n) olur. Her arabayı önündeki her arabayla karşılaştırmak O(n²) sürer.

Q: Varış zamanlarını kayan nokta kullanmadan nasıl karşılaştırırsınız?

Varış süresi dist / speed şeklindedir. Hızlar pozitif olduğundan, d1 / s1 > d2 / s2 eşitsizliği, tam olarak d1 × s2 > d2 × s1 olduğunda sağlanır. Her iki taraf da 10^12 değerine kadar tam sayılardır; bu nedenle bunları 64 bitlik bir türde hesaplayın. Böylece karşılaştırma kesin olur ve yuvarlamayı hesaba katmanız gerekmez.

OrtaYığın Sıralama

+10

Arabalar tek şeritli bir yolda target miline doğru ilerliyor. i numaralı araba position[i] milinde başlıyor ve saatte speed[i] mil hızla ilerliyor. Hiçbir araba başka bir arabayı geçemez: daha yavaş bir arabaya yetişen araba onun hemen arkasında kalır ve o andan itibaren iki araba tek bir filo olarak daha yavaş hızda birlikte ilerler.

Tek bir araba da bir filo sayılır ve varış noktasında bir filoya tam olarak ulaşan araba bu filoya katılır. Varış noktasına ulaşan filo sayısını döndür.

Fonksiyon

carFleet(target: integer, position: integer-array, speed: integer-array) → integer

targetinteger: her arabanın yöneldiği mil
positioninteger-array: her arabanın başlangıç kilometresi
speedinteger-array: her bir arabanın saatte mil cinsinden hızı
Döndürürinteger: hedefe ulaşan filo sayısı

Kısıtlar

n == position.length == speed.length
1 ≤ n ≤ 10⁴
1 ≤ target ≤ 10⁶
0 ≤ position[i] < target
1 ≤ speed[i] ≤ 10⁶
Tüm konumlar farklıdır.

Örnekler

Girdi: target = 20position = [14, 2, 8, 17, 0]speed = [3, 6, 4, 1, 2]
Çıktı: 2
Açıklama: Tek başlarına, 17, 14, 8 ve 2. millerdeki arabaların sırasıyla 3, 2, 3 ve 3 saate ihtiyacı vardır; bu nedenle 14’teki araba 17’dekini yakalar ve diğer ikisi onlara 20. milde ulaşır. 0’daki arabanın 10 saate ihtiyacı vardır ve tek başına varır.

Girdi: target = 9position = [0, 4, 7]speed = [1, 2, 3]
Çıktı: 3
Açıklama: 7, 4 ve 0. mildeki arabaların sırasıyla 2/3, 5/2 ve 9 saate ihtiyacı var. Her biri önündeki arabadan sonra varacağından kimse kimseye yetişemez: 3 filo.

Ek soru

Konumlar, target değerinden küçük tam sayılardır. Karşılaştırmalı sıralama kullanmadan, filoları O(n + target) sürede sayabilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Tek şeritte araçların sırası hiç değişmez ve her şeyi, her aracın tek başına ne zaman varacağı belirler: (target - position[i]) / speed[i]. Araçları hedefe en yakın olandan başlayıp geriye doğru incele. Bir araç, yalnızca önündeki filodan kesin olarak daha geç varacaksa yeni bir filo başlatır.

Öndeki her aracı kontrol et

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Bir araba, yalnız başına tam önündeki her arabadan kesinlikle daha erken varacaksa bir filonun önüne geçer. Önündeki arabalardan biri daha erken varmayacaksa, arabanız varış noktasına kadar ona veya filosuna yetişir. Hepsi daha erken varırsa, öndeki hiçbir şey onu yavaşlatamaz; çünkü bir filo, arabaları arasındaki en geç yalnız varış zamanında varır. Süreleri çapraz çarpma yoluyla tam olarak karşılaştırarak öndeki arabaları sayın.

Her araba n arabanın tümünü tarar: n = 10^4 için 10^8 kontrol.

Algoritma

fleets = 0 olarak ayarla.
Her araba i için, position[j] > position[i] koşulunu sağlayan her araba j'ye bak.
Herhangi bir j için (target - position[j]) × speed[i] ≥ (target - position[i]) × speed[j] ise, i arabası yakalanmıştır: onu atla.
Aksi takdirde i arabası bir filonun lideridir: fleets değerini 1 artır.
fleets değerini döndür.

def carFleet(target, position, speed):
    n = len(position)
    fleets = 0
    for i in range(n):
        dist = target - position[i]
        caught = False
        for j in range(n):
            # Car j is ahead and would not arrive before car i: car i catches it.
            # (target - position[j]) / speed[j] >= dist / speed[i], without division.
            if position[j] > position[i] and (target - position[j]) * speed[i] >= dist * speed[j]:
                caught = True
                break
        if not caught:
            fleets += 1
    return fleets

Konuma göre sırala ve filoları üst üste yığ

Sezgi

Konuma göre sıralandığında, hedefe en yakından başlayarak mevcut aracın önündeki arabalar, tam olarak daha önce görülmüş, zaten filolarda olan arabalardır. Filoları bir yığında tutun; her birini, filonun varış zamanını belirleyen öndeki arabasının mesafesi ve hızı olarak saklayın.

Yalnızca en üstteki önemlidir. Her eklenen filo, altındaki filodan kesinlikle daha geç varır; bu nedenle zamanlar alttan üste doğru artar ve en üsttekinden daha geç olan, öndeki her arabadan da daha geç varır.

Sıralı 1. örnekte arabalar 17, 14, 8, 2 ve 0 konumlarındadır; mesafe bölü hız değerleri 3/1, 6/3, 12/4, 18/6, 20/2 şeklindedir. (3, 1) ekleyin. 14 konumundaki araba katılır; çünkü 6 × 1 > 3 × 3 yanlıştır. 8 konumundaki araba aynı zamana denk gelir, 12 × 1 = 3 × 4, ve katılır; 2 konumundaki araba da aynı şekilde katılır. 0 konumundaki araba için 20 × 1 > 3 × 2: ekleyin.

Algoritma

Araba indekslerini konuma göre, en büyükten en küçüğe sıralayın.
Boş bir filo yığınıyla başlayın.
Her araba için dist = target - position[i] değerini hesaplayın.
Yığın boşsa veya dist × topSpeed > topDist × speed[i] ise (dist, speed[i]) değerini yığına ekleyin; aksi takdirde araba en üstteki filoya katılır.
Yığının boyutunu döndürün.

def carFleet(target, position, speed):
    # Visit the cars from the one closest to the target backward.
    order = sorted(range(len(position)), key=lambda i: position[i], reverse=True)
    # One entry per fleet: (distance, speed) of the car at its front, which sets its arrival time.
    stack = []
    for i in order:
        dist, spd = target - position[i], speed[i]
        # dist / spd > top_dist / top_spd, compared without division:
        # this car arrives after the fleet ahead, so it never catches it.
        if not stack or dist * stack[-1][1] > stack[-1][0] * spd:
            stack.append((dist, spd))
    return len(stack)

Tuzaklar ve uç durumlar

Tam eşitliği yeni bir konvoy saymak. 1. örnekte 8 ve 2 mil konumundaki arabalar, 20. mildeki konvoyla buluşup ona katılır. Yalnızca zaman kesin olarak daha geç olduğunda yığına ekleyin.
Çapraz çarpımda taşma. 10^6 × 10^6 = 10^12 32 bite sığmaz: Java, C, C++, C# ve Rust'ta çarpmadan önce 64 bite genişletin; R'de double kullanın.
Yanlış yönde sıralama yapmak. Hedefe en uzak arabadan başlayarak her arabayı arkasındaki arabalarla karşılaştırırsınız; bu arabalar onu asla engelleyemez.
position değerini tek başına sıralamak. İndeksleri veya (konum, hız) çiftlerini sıralayın; böylece her hız kendi arabasıyla eşleşmiş kalır.

Sıkça sorulan sorular3

Car Fleet'in zaman karmaşıklığı nedir?

Konuma göre sıralama O(n log n) sürer ve yığınla yapılan geçiş O(n) sürer; bu nedenle toplam süre O(n log n), bellek kullanımı ise O(n) olur. Her arabayı önündeki her arabayla karşılaştırmak O(n²) sürer.

Car Fleet neden bir yığın kullanır?

Arabaları önden gezerken, her yeni araba yalnızca hemen önündeki, en son oluşturulan filoyla karşılaştırılmalıdır. Bir yığın, bu filoyu en üstte tutar. Yalnızca en üstteki okunduğundan, iki değişken de işe yarar; yığın ayrıca filoların kendilerini de elinde tutar.

Varış zamanlarını kayan nokta kullanmadan nasıl karşılaştırırsınız?

Varış süresi dist / speed şeklindedir. Hızlar pozitif olduğundan, d1 / s1 > d2 / s2 eşitsizliği, tam olarak d1 × s2 > d2 × s1 olduğunda sağlanır. Her iki taraf da 10^12 değerine kadar tam sayılardır; bu nedenle bunları 64 bitlik bir türde hesaplayın. Böylece karşılaştırma kesin olur ve yuvarlamayı hesaba katmanız gerekmez.

def carFleet(target, position, speed):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argümanlar

target = 20
position = [14, 2, 8, 17, 0]
speed = [3, 6, 4, 1, 2]

Beklenen Çıktı