Summary Ranges
Farklı tam sayılardan oluşan sıralı bir nums dizisi alırsınız. Her değer tam olarak bir aralığa ait olacak şekilde diziyi, ardışık tam sayılardan oluşan mümkün olan en az sayıda aralığa bölün. a..b aralığını "a->b" metniyle, tek bir değer içeriyorsa "a" olarak yazın. Aralıkları artan sırada döndürün.
Fonksiyon
- numsinteger-array
- sıralanmış farklı tam sayılardan oluşan dizi
- Döndürürstring-array
- aralıkları, en küçük değerlerden en büyük değerlere doğru metin olarak
Kısıtlar
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109numsartan sırada sıralanmıştır ve yinelenen öğe içermez.
Örnekler
- Girdi
- nums = [0, 1, 2, 5, 6, 9]
- Çıktı
- ["0->2", "5->6", "9"]
- Açıklama
0, 1, 2birbirini takip eder, bu nedenle"0->2"aralığını oluştururlar. 2'den 5'e sıçrama yeni bir aralık başlatır:"5->6"ve 9 tek başına"9"olarak kalır.
- Girdi
- nums = [-3, -1, 0, 1, 4, 7, 8]
- Çıktı
- ["-3", "-1->1", "4", "7->8"]
- Açıklama
- -3'ün komşusu yoktur (-2 eksiktir),
-1, 0, 1bir dizi oluşturur, 4 tek başınadır ve7, 8listeyi tamamlar. Negatif değerler de aynı şekilde çalışır: -1'i -1 + 1 = 0 izler.
Gönderirken +16 gizli test
Ek soru
nums yinelenen değerler içerebilseydi, örneğin [1, 2, 2, 3], yine de "1->3" yazdırması için neyi değiştirirdin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Dizi sıralanmıştır. İki komşu değer ne zaman aynı aralığa aittir?
Yalnızca
nums[i+1] == nums[i] + 1olduğunda aynı aralığa aittirler. Diğer tüm komşu çiftler bir aralığın sonunu ve sonrakinin başlangıcını belirtir.Geçerli aralığın nerede başladığını hatırla. Sonraki değer geçerli değerden bir fazlaysa ilerlemeye devam et; ardışıklık bozulduğunda veya dizi sona erdiğinde, aralığı başlangıç değerinden geçerli değere kadar yaz ve sonraki aralığı bir sonraki değerden başlat.
Çözüm
Değerler sıralı ve birbirinden farklı olduğu için, ardışık tam sayılardan oluşan bir aralık dizide her zaman bir komşu dizisidir ve bir aralık, iki komşu arasındaki fark 1’den büyük olduğunda tam olarak sona erer. Diziyi bu tür her boşlukta bölmek, en az sayıda aralık elde etmenizi sağlar; çünkü hiçbir aralık bir boşluğu aşamaz. Geriye dikkatli bir kayıt tutma işi kalır: her dizinin başlangıcı, son eleman ve metin biçimi.
Her değerin iki komşusunu da kontrol et
Sezgi
Her seferinde tek bir değere bakıp iki soru sorun. Burada bir aralık açılıyor mu? Evet, bu ilk değerse veya önceki değer bir eksiği değilse. Burada bir aralık kapanıyor mu? Evet, bu son değerse veya sonraki değer bir fazlası değilse.
[0, 1, 2, 5, 6, 9] içinde bir aralık 0, 5 ve 9'da açılır, 2, 6 ve 9'da kapanır. Geçerli aralığın açıldığı değeri hatırlayın. Bir aralık nums[i] değerinde kapandığında "start->nums[i]" yazın; aralık 9'da olduğu gibi aynı değerde açılıp kapanıyorsa yalnızca "start" yazın.
Her değer bir kez ziyaret edilir ve iki komşusuna bakılır; bu nedenle zaman karmaşıklığı O(n) olur. Çıktı dışında, hatırladığınız tek bir başlangıç değeri vardır; bu nedenle ek alan kullanımı O(1) olur.
Algoritma
start = nums[0]olarak ayarla.- Her
iindeksi için:i > 0ise venums[i] != nums[i-1] + 1koşulu sağlanıyorsastart = nums[i]olarak ayarla. ison indeksse veyanums[i+1] != nums[i] + 1koşulu sağlanıyorsa aralık burada sona erer.start == nums[i]ise"start", aksi hâlde"start->nums[i]"ekle.- Son indeksten sonra listeyi döndür.
def summaryRanges(nums):
n = len(nums)
ranges = []
start = nums[0]
for i in range(n):
# A range opens where the value before is not one less.
if i > 0 and nums[i] != nums[i - 1] + 1:
start = nums[i]
# A range closes where the value after is not one more.
if i == n - 1 or nums[i + 1] != nums[i] + 1:
ranges.append(str(start) if start == nums[i] else f"{start}->{nums[i]}")
return rangesHer bir çalışma boyunca iki işaretçi
Sezgi
Her aralığı dizinin bir bloğu olarak ele al ve iki ucunu bul. i işaretçisi aralığın ilk değerinde durur. j işaretçisi i konumundan başlar ve sonraki değer tam olarak bir fazlası olduğu sürece sağa ilerler; böylece aralığın son değerinde durur.
[-3, -1, 0, 1, 4, 7, 8] için: i, -3 konumundayken ilerleyemez; çünkü -1, -2 değildir. Bu nedenle aralık "-3" olur. Ardından i, -1 konumuna atlar ve j, 0 ve 1 üzerinden ilerleyip 4'ten önce durur: "-1->1". Sonra "4" ve "7->8" gelir. Her aralıktan sonra i, bir sonraki aralığın ilk değeri olan j+1 konumuna ilerler.
Aralık sayısı olabilecek en az sayıdadır: aralarında boşluk bulunan iki değer asla aynı aralıkta yer alamaz ve yöntem yalnızca boşluklarda ayırır. Her iki işaretçi de yalnızca ileri hareket eder; bu nedenle iç döngü tüm aralıklar boyunca toplamda n kez çalışır. Böylece zaman karmaşıklığı O(n), ek alan kullanımı ise O(1) olur.
Algoritma
i = 0olarak ayarla.j = iolarak ayarla vej+1 < nvenums[j+1] == nums[j] + 1olduğu sürecej'yi sağa ilerlet.i == jolduğunda"nums[i]", aksi hâlde"nums[i]->nums[j]"ekle.i = j + 1olarak ayarla veisona ulaşana kadar tekrarla.- Listeyi döndür.
def summaryRanges(nums):
ranges = []
n = len(nums)
i = 0
while i < n:
# i is the first value of a run; push j to its last value.
j = i
while j + 1 < n and nums[j + 1] == nums[j] + 1:
j += 1
ranges.append(str(nums[i]) if i == j else f"{nums[i]}->{nums[j]}")
# The next run starts right after this one.
i = j + 1
return ranges
Tuzaklar ve uç durumlar
Mantık birkaç satıra sığar; hatalar uç durumlarda ortaya çıkar.
- Son aralığı unutmak. Bir aralığı yalnızca bir boşlukla karşılaştığında yazan döngü, son aralığı hiçbir zaman yazmaz; bu yüzden
[0, 1, 2, 5, 6, 9]içindeki"9"kaybolur. Son indekste de bir aralığı kapatın. - Tek bir değer için
"a->a"yazmak. Tek değerlik bir aralık"a"olarak yazılır. - Büyük değerleri bilimsel gösterimde yazdırmak. R,
1000000000gibi bir double değerini1e+09biçimine dönüştürür; değerleri paste etmeden önce tam sayılara dönüştürün.
Sıkça sorulan sorular4
Summary Ranges'ın zaman karmaşıklığı nedir?
O(n). Her değer bir kez ziyaret edilir ve her aralık bir kez yazılır. Çıktı listesi dışında ek alan O(1)'dir: geçerli aralığın başlangıcı ve bir veya iki indeks.
Her boşlukta kesmek neden en az aralığı verir?
Bir aralık ardışık tam sayıları içerir; bu nedenle aralarında eksik bir sayı bulunan iki değeri içeremez. Bu yüzden sıralı dizideki her boşluk iki aralığı birbirinden ayırmalıdır ve g boşluk varsa en az g+1 aralığa ihtiyacın vardır. Yalnızca boşluklardan kesmek tam olarak g+1 aralık verir.
Yalnızca bir sayı içeren bir aralığı nasıl ele alırsınız?
Aralığın aynı değerle başlayıp bittiğini kontrol et. Öyleyse bu değeri tek başına yaz; örneğin "9". Değilse başlangıç değerini, oku ve bitiş değerini yaz; örneğin "5->6". İki işaretçi kullanıldığında kontrol i == j olur.
Summary Ranges için girdinin sıralanmış olması gerekir mi?
Evet. Yöntem yalnızca komşu öğeleri karşılaştırır, bu nedenle ardışık tam sayıların yan yana olmasına dayanır. Sıralanmamış bir girdi için önce sıralama yap; bu, tüm işlemin O(n log n) olmasını sağlar. Ya da değerleri bir karma kümesine ekleyip, en uzun ardışık dizi probleminde olduğu gibi, her aralığı en küçük değerinden başlayarak genişlet.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def summaryRanges(nums):
# Kodu buraya yazınDurum 1
Durum 2
Girdi
nums = [0, 1, 2, 5, 6, 9]
Beklenen
["0->2", "5->6", "9"]