Değerleri aralıklara sıkıştır
Görev tanımı
Problem
Sana birbirinden farklı tam sayılardan oluşan sıralı bir liste veriliyor. Onu ardışık tam sayı bloklarından oluşan mümkün olan en kısa listeyle, sırasıyla tarif et. Bir blok birden fazla değer kapsıyorsa "a->b", tek bir değer tutuyorsa yalnız "a" olarak yaz.
Örnekler
Input: nums = [0, 1, 2, 4, 5, 7]
Output: ["0->2", "4->5", "7"]
Input: nums = [-3, -1, 0]
Output: ["-3", "-1->0"]
Neden: negatif değerler de aynı kurala uyar
Input: nums = []
Output: []
Neden: edge case: değer yoksa blok da yok
İpuçları
0 / 3
Liste sıralı ve tekrarsız olduğu için bir blok yalnız komşu iki eleman arasında kırılabilir.
Bir blok tam olarak her sonraki değer bir öncekinden bir fazla olduğu sürece devam eder. Geri kalan her şey mevcut bloğun nerede başladığının hesabını tutmak.
Mevcut bloğun başladığı indeksi tut. Sonraki değer tam olarak bir büyük olduğu sürece bir bitiş indeksini uzat. Sonra bloğu tek bir değer ya da başlangıç ok bitiş olarak yaz ve bir sonraki bloğa hemen ardından başla.
- Hedef zaman
- O(n)
- Hedef alan
- O(n)
Kısıtlar
- the list is sorted ascending
- the values are distinct integers
Çözüm
Sıralı ve farklı girdi, bir bloğun tam olarak iki komşunun birden fazla farklılaştığı yerde kırıldığı anlamına gelir; bu yüzden soldan sağa tek bir tarama her sınırı bulur. Dış döngü bir bloğun başladığı yeri işaretler, iç döngü değerler ardışık kaldıkça bitişini uzatır, sonra indeks çifti iki biçimden hangisi uyuyorsa onunla yazılır. Her indeks iç döngü tarafından toplamda bir kez ziyaret edilir; zaman O(n), çıktı dışında alan O(1).
def condense(nums):
out, i = [], 0
while i < len(nums):
j = i
while j + 1 < len(nums) and nums[j + 1] == nums[j] + 1:
j += 1 # the run is still consecutive
out.append(str(nums[i]) if i == j else f"{nums[i]}->{nums[j]}")
i = j + 1 # next run starts after this one
return out
print(condense([0, 1, 2, 4, 5, 7])) # -> ['0->2', '4->5', '7']
print(condense([-3, -1, 0])) # -> ['-3', '-1->0']
print(condense([])) # -> []Kodda değil de fikirde mi takıldın? Aralık temelleri ve sıralama bunu anlatıyor.