Plus One
Negatif olmayan bir tam sayı, ondalık basamaklarından oluşan bir dizi olarak saklanır; en anlamlı basamak ilk sıradadır: 472, [4, 7, 2] şeklindedir. Sayıya bir ekleyin ve sonucu aynı biçimdeki basamaklarıyla döndürün. Sayı, 64 bitlik bir tamsayının tutabileceğinden çok daha fazla, 100 basamağa kadar çıkabilir.
Fonksiyon
- digitsinteger-array
- sayının basamakları, en anlamlı basamaktan başlayarak
- Döndürürinteger-array
- sayının rakamları, en anlamlı basamaktan başlayarak, bir fazlası
Kısıtlar
1 ≤ digits.length ≤ 1000 ≤ digits[i] ≤ 9digitsbaşında sıfır bulunmaz; tek istisna,[0]olan 0 sayısıdır.
Örnekler
- Girdi
- digits = [4, 3, 9]
- Çıktı
- [4, 4, 0]
- Açıklama
- Sayı 439'dur ve 439 + 1 = 440. Son basamak olan 9, 0'a dönüşür ve 3'e elde aktarır; böylece 3, 4 olur.
- Girdi
- digits = [9, 9]
- Çıktı
- [1, 0, 0]
- Açıklama
- 99 + 1 = 100. Her iki 9 da 0'a dönüşür ve geriye kalan elde yeni bir baştaki basamak olur; bu nedenle yanıt, girdiden bir basamak daha uzundur.
- Girdi
- digits = [0]
- Çıktı
- [1]
- Açıklama
- 0 sayısı
[0]olarak yazılır ve 0 + 1 = 1.
Gönderirken +13 gizli test
Ek soru
En az 1 olan bir sayıdan bir çıkarmak için ne yaparsın? Hangi basamaklar değişir ve [1, 0, 0] örneğindeki gibi sonuç baştaki basamağını ne zaman kaybeder?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Sayı 100 basamaklı olabilir; bu, herhangi bir yerleşik tam sayı türünün tutabileceğinden çok fazla. Toplamayı, kâğıt üzerinde yaptığın gibi basamaklar üzerinden yap. 1 ilk olarak nereye gider?
9'un altındaki bir rakama 1 eklemek elde oluşturmaz, bu yüzden solundaki hiçbir şey değişmez. Yalnızca 9, 0'a dönüşür ve bir elde aktarır.
Son basamaktan başlayarak sola doğru ilerle. Her 9'u 0'a dönüştür; 9'dan küçük ilk basamağa bir ekle ve bitir. Böyle bir basamak bulamazsan tüm basamaklar 9'dur: yanıt, ardından sıfırlar gelen 1'dir.
Çözüm
Basamakları sayıya dönüştürüp bir ekleyerek yeniden basamağa dönüştürmek burada başarısız olur: 100 basamak, 1.8 × 10^19 civarında sınırına ulaşan her 64 bitlik tam sayı türünün taşmasına neden olur. Bu yüzden kâğıt üzerinde yaptığın gibi, son basamaktan başlayıp eldeyi taşıyarak toplarsın. İşi kısaltan tek gözlem şudur: 1 eklemek yalnızca sondaki 9’ları değiştirir; bunlar 0 olur ve solundaki ilk basamak da değişir. Diğer tüm basamaklar olduğu gibi kalır.
Basamak basamak elde ile toplama
Sezgi
Sayıyı yazın ve okulda yaptığınız gibi son basamağının altına 1 ekleyin. Eklediğiniz 1 ile eldeyi başlatın. Sağdan başlayarak her basamakta sütun toplamı, basamak ile elde değerinin toplamıdır. Son basamağı, total % 10, cevaba yazılır; onlar basamağı olan total / 10 ise sonraki sütunun eldesidir.
Elde 1 olduğunda sütun toplamı en fazla 9 + 1 = 10 olur; dolayısıyla elde her zaman 0 veya 1'dir. İlk basamaktan sonra hâlâ elde varsa cevaba yeni bir baştaki basamak eklenir: 999 + 1 işlemi, 1000'in 1'i için dördüncü bir basamak gerektirir.
Cevap, hesaplama sırası bu olduğu için önce son basamaktan başlayarak oluşur. Basamakları bu sırayla toplayın ve sonunda ters çevirin. Bu işlem O(n) zaman ve en fazla n + 1 basamaklık yeni bir dizi gerektirir.
Algoritma
carrydeğerini 1 olarak ayarla ve yanıt için boş bir liste oluştur.- Son basamaktan ilk basamağa doğru her basamak için
total = digit + carrydeğerini hesapla. total % 10değerini yanıta ekle vecarrydeğerini aşağı yuvarlanmıştotal / 10olarak ayarla.- Döngüden sonra,
carry1 ise onu ekle. - Yanıtı ters çevir ve döndür.
def plusOne(digits):
result = [] # the answer, last digit first
carry = 1 # the one you are adding
for i in range(len(digits) - 1, -1, -1):
total = digits[i] + carry
result.append(total % 10)
carry = total // 10
if carry > 0:
result.append(carry)
result.reverse()
return result9'dan küçük ilk rakamda dur
Sezgi
Tam olarak 1 eklediğinizde elde ne olduğuna bakın. 9'dan küçük bir basamak bu değeri içine alır: 3, 4 olur, elde 0'a düşer ve daha soldaki tüm basamaklar değerlerini korur. Yalnızca 9, 0'a dönüşerek eldeyi aktarır. Yani 1 eklemek, sondaki 9'ları 0'a çevirmek ve ardından bunlardan hemen önceki basamağa 1 eklemek demektir.
Son basamaktan başlayarak sola doğru ilerleyin. 9 gördüğünüzde 0 yazıp devam edin. Diğer tüm basamaklarda değeri bir artırın ve hemen diziyi döndürün; çünkü solundaki hiçbir şey değişemez. [2, 9, 0, 9] için sondaki 9, 0 olur; 0, 1 olur ve ilk iki basamağa bakmadan [2, 9, 1, 0] ile durursunuz.
Döngü 9'dan küçük bir basamak bulamazsa tüm basamaklar 9'dur ve artık 0 olmuşlardır. Sayı 10^n - 1 idi; dolayısıyla sonuç, ardından n tane sıfır gelen bir 1'dir. Yeni bir dizi gereken tek durum budur. Diğer tüm durumlarda girdiyi yerinde değiştirirsiniz; bu nedenle ek alan O(1) olur ve döngü sondaki her 9 için bir kez, ardından bir adım daha çalışır.
Algoritma
- Dizinler üzerinde sondan başa doğru ilerleyin.
- Rakam 9'dan küçükse, onu bir artırın ve diziyi döndürün.
- Aksi takdirde rakam 9'dur: onu 0 olarak ayarlayın ve bir basamak sola ilerleyin.
- Döngü sona ererse, tüm rakamlar 9'dur: ardından
nsıfır gelen 1'i döndürün.
def plusOne(digits):
for i in range(len(digits) - 1, -1, -1):
if digits[i] < 9:
digits[i] += 1 # no carry leaves this digit, so the rest stays as it is
return digits
digits[i] = 0 # 9 + 1 = 10: write 0 and carry one to the left
# Every digit was 9: the answer is 1 followed by zeros.
return [1] + digits
Tuzaklar ve uç durumlar
Tuzaklar, tamsayı taşması ve tüm basamakların 9 olduğu durumdur.
- Diziyi tamsayıya çevirip geri dönüştürmek. Küçük testleri geçer, sonra 100 basamaklı sayılarda başarısız olur: 64 bitlik bir tamsayı en fazla 19 veya 20 basamak tutabilir; kayan noktalı sayı ise son basamakları daha da erken kaybeder.
- Ek basamağı unutmak.
[9, 9, 9], dört basamaklı[1, 0, 0, 0]hâline gelmelidir. Yalnızca mevcut basamakları yeniden yazan kod[0, 0, 0]döndürür. - Son basamak yerine ilk basamağa 1 eklemek. Dizi en anlamlı basamak başta olacak şekilde sıralanır; dolayısıyla birler basamağı sondadır.
- Bir basamağa 9'dan küçük bir değer geldiğinde eldeyi bitirmek için return etmeyi unutmak. Erken çıkışlı sürümde döngü devam eder ve olduğu gibi kalması gereken basamakları değiştirir.
[1, 9, 3]içinde yalnızca 3 değişebilir; sonuç[1, 9, 4]olur. - Dizilerin 1'den başladığı Lua ve R'de indeks sırasını karıştırmak: son basamak
nindeksindedir ve başa eklenecek yeni 1, 1. indeksin önüne gelir.
Sıkça sorulan sorular4
Plus One'ın zaman karmaşıklığı nedir?
Her iki yaklaşım da n basamak için O(n) zamanda çalışır; çünkü en kötü durumda, tüm basamaklar 9 olduğunda, her basamağa dokunulur. Erken çıkışlı sürüm sondaki 9’lardan sonra durur; bu nedenle 9’dan küçük bir basamakla biten bir sayı için tek adımda tamamlanır. Yanıtın başına yeni bir basamak eklenmesi gerekmediği sürece O(1) ek alan kullanır.
Rakamları neden bir tam sayıya dönüştürmüyoruz?
Sayı 100 basamaklı olabilir ve 64 bitlik bir tamsayı yaklaşık 1.8 × 10^19 değerinde, yani 20 basamakta sınırına ulaşır. Python ve Ruby'de tamsayıların boyutu sınırsızdır; bu nedenle dönüştürme bu dillerde işe yarar, ancak alıştırmanın amacını gizler ve diğer dillere aktarılmaz. Basamak basamak işlem yapmak hiçbir zaman taşmaya yol açmaz.
Sonuç hangi durumda girdiden daha fazla basamağa sahip olur?
Yalnızca her rakam 9 olduğunda. Bu durumda sayı 10^n - 1 olur ve bir eklemek 10^n sonucunu verir: ardından n sıfır gelen bir 1. Herhangi bir rakam 9'dan küçükse eldeyi alır, böylece uzunluk aynı kalır.
Basamak dizileri olarak saklanan iki sayıyı nasıl toplarsınız?
İlk yaklaşımdaki sütun yöntemini, her dizinin sonunda birer tane olacak şekilde iki indeksle kullanın. Her sütunda iki basamağı, eksik basamağı 0 kabul ederek, eldeyle birlikte toplayın. Her iki dizi de tükenene ve elde 0 olana kadar devam edin, ardından toplanan basamakları ters çevirin.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def plusOne(digits):
# Kodu buraya yazınDurum 1
Durum 2
Durum 3
Girdi
digits = [4, 3, 9]
Beklenen
[4, 4, 0]