Her k'lık bloğu ters çevir
Görev tanımı
Problem
Bir liste ve pozitif bir k tam sayısı verildiğinde, k değerlik her ardışık bloğun içindeki değerlerin sırasını ters çevir: önce ilk k, sonra sonraki k, böyle devam. Uzunluk k'nın katı değilse son blok k'dan kısadır ve olduğu gibi kalır. In-place (yerinde) ve O(1) ek alanla çalış, aynı listeyi döndür.
Örnekler
Input: nums = [1, 2, 3, 4, 5, 6, 7, 8], k = 3
Output: [3, 2, 1, 6, 5, 4, 7, 8]
Neden: iki tam blok ters çevrilir; 7 ve 8 kısa bir blok oluşturur
Input: nums = [1, 2, 3, 4], k = 4
Output: [4, 3, 2, 1]
Neden: tek blok bütün listeyi kaplar
Input: nums = [5, 6], k = 3
Output: [5, 6]
Neden: edge case: hiç tam blok yok
İpuçları
0 / 3
Listeyi kafanda 0 indeksinden başlayarak k'lık parçalara böl. Her tam parça, diğerlerinden bağımsız küçük bir ters çevirmedir.
Yerinde ters çevirme için yalnız değerlerin yerini değiştiren ve birbirine doğru ilerleyen iki indeks gerekir. Geriye kalan soru, her parçanın nerede başlayıp nerede bittiği.
Blok başlangıçları 0, k, 2k diye ilerleyen bir döngü kur; bloğu sonun ötesine taşacak bir başlangıçtan önce dur. Her blokta iki uçtaki değerlerin yerini değiştir ve iki indeksi buluşana kadar içe kaydır.
- Hedef zaman
- O(n)
- Hedef alan
- O(1)
Kısıtlar
- k is a positive integer
- a final block shorter than k stays as it is
- in place with O(1) extra space
Çözüm
Blok başlangıçları 0, k, 2k diye ilerler ve bir blok yalnız k değerinin hepsi mevcutsa ters çevrilir; bunu len(nums) - k + 1 aralık sınırı sağlar. Her blok, değerlerin yerini değiştirip (swap) ortada buluşan iki indeksle ters çevrilir, böylece ikinci bir liste kurulmaz. Her değerin yeri en fazla bir kez değişir. Zaman O(n), alan O(1).
def reverse_blocks(nums, k):
for start in range(0, len(nums) - k + 1, k): # full blocks only
lo, hi = start, start + k - 1
while lo < hi: # swap the ends, walk inward
nums[lo], nums[hi] = nums[hi], nums[lo]
lo += 1
hi -= 1
return nums
print(reverse_blocks([1, 2, 3, 4, 5, 6, 7, 8], 3)) # -> [3, 2, 1, 6, 5, 4, 7, 8]
print(reverse_blocks([1, 2, 3, 4], 4)) # -> [4, 3, 2, 1]
print(reverse_blocks([5, 6], 3)) # -> [5, 6]Kodda değil de fikirde mi takıldın? In-place ters çevirme bunu anlatıyor.