Plus One

Q: Plus One'ın zaman karmaşıklığı nedir?

Her iki yaklaşım da n basamak için O(n) zamanda çalışır; çünkü tüm basamakların 9 olduğu durumda her basamağa dokunulur. Erken çıkışlı sürüm, sondaki 9'lardan sonra durur ve yanıtın başına yeni bir basamak eklenmesi gerektiği durum dışında O(1) ek alan kullanır.

KolayMatematik ve simülasyon

+10

Negatif olmayan bir tam sayı, onluk basamaklarından oluşan bir dizi olarak saklanır: digits. En anlamlı basamak ilk sıradadır: 472, [4, 7, 2] şeklindedir. Sayıya bir ekleyin ve sonucun basamaklarını aynı biçimde döndürün. Sayı en fazla 100 basamaklı olabilir; bu, 64 bitlik bir tamsayının tutabileceğinden çok daha fazladır.

Fonksiyon

plusOne(digits: integer-array) → integer-array

digitsinteger-array: sayının rakamları, en anlamlı basamaktan başlayarak
Döndürürinteger-array: sayının rakamları, en anlamlı basamaktan başlayarak, bir eklenmiş hâli

Kısıtlar

1 ≤ digits.length ≤ 100
0 ≤ digits[i] ≤ 9
digits başında sıfır bulunmaz; 0 sayısının kendisi ise [0] şeklindedir.

Ö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; 3 de 4 olur.

Girdi: digits = [0]
Çıktı: [1]
Açıklama: 0 sayısı [0] olarak yazılır ve 0 + 1 = 1.

Ek soru

Bunun yerine, en az 1 olan bir sayıdan bir çıkarmayı nasıl yaparsınız? Sonuç, [1, 0, 0] örneğindeki gibi baştaki basamağını ne zaman kaybeder?

Çözüm

100 basamaklı bir sayı, yaklaşık 1.8 × 10^19 civarında sınırı aşan her 64 bitlik tamsayıda taşmaya neden olur; bu yüzden sayıyı dönüştürüp toplayamazsın. Kâğıt üzerinde yaptığın gibi, en sağdaki basamaktan başlayıp eldeyi kullanarak topla. 1 eklemek yalnızca sondaki 9'ları (bunlar 0 olur) ve onların solundaki basamağı değiştirir.

Basamak basamak eldeyle toplama

Sezgi

Eklediğin 1 değerindeki eldeyle başla. Sağdan başlayarak her basamakta sütun toplamı, basamak ile elde değerinin toplamıdır: total % 10 yanıta eklenir ve total / 10 sonraki elde olur. Toplam en fazla 9 + 1 = 10 olduğundan elde 0 veya 1 olur. İlk basamaktan sonra kalan elde, 999 + 1 = 1000 örneğindeki gibi yeni bir baştaki basamağa dönüşür.

Yanıtı önce son basamağından başlayarak oluşturursun; bu yüzden basamakları bu sırayla topla ve sonunda tersine çevir. Bu işlem O(n) zaman alır ve en fazla n + 1 basamak içeren yeni bir dizi oluşturur.

Algoritma

carry değerini 1 olarak ayarlayın ve yanıt için boş bir liste başlatın.
Son basamaktan ilk basamağa kadar her basamak için total = digit + carry değerini hesaplayın.
total % 10 değerini yanıta ekleyin ve carry değerini aşağı yuvarlanmış total / 10 olarak ayarlayın.
Döngüden sonra, carry 1 ise onu ekleyin.
Yanıtı ters çevirin ve döndürün.

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 result

9'dan küçük ilk rakamda dur

Sezgi

9'dan küçük bir basamak 1 eldeyi alır: bir artar ve solundaki her basamak değerini korur. Yalnızca 9 eldeyi aktarır ve 0'a dönüşür. Böylece 9'dan küçük ilk basamakta durup giriş dizisini yerinde değiştirilmiş hâliyle döndürebilirsin. [2, 9, 0, 9] için son 9, 0 olur; 0, 1 olur ve ilk iki basamağı okumadan [2, 9, 1, 0] döndürürsün.

Hiçbir basamak 9'dan küçük değilse sayı 10^n - 1 idi ve yanıt, ardından n tane sıfır gelen 1'dir. Yeni bir dizi gerektiren tek durum budur; dolayısıyla diğer durumlarda ek alan O(1)'dir.

Algoritma

Dizinlerde sondan başa doğru ilerle.
Rakam 9'dan küçükse, onu bir artır ve diziyi döndür.
Aksi hâlde rakam 9'dur: onu 0 yap ve bir basamak sola ilerle.
Döngü sona ererse, her rakam 9'dur: 1'in ardından n sıfır döndür.

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

Diziyi tamsayıya dönüştürüp tekrar diziye çevirmek. 64 bitlik bir tamsayı en fazla 19 veya 20 basamak tutabilir; bu nedenle 100 basamak taşmaya neden olur ve kayan noktalı sayı son basamakları daha da erken kaybeder.
Ek basamağı unutmak. [9, 9, 9], [1, 0, 0, 0] hâline gelmelidir; yalnızca mevcut basamakları yeniden yazan kod [0, 0, 0] döndürür.
İlk basamağa 1 eklemek. Dizi en anlamlı basamak başta olacak şekilde sıralanmıştır; bu nedenle birler basamağı son öğedir.
9'dan küçük bir basamak eldeyi aldığında döngüden çıkmamak. Böylece döngü, değişmeden kalması gereken basamakları değiştirir: [1, 9, 3], [1, 9, 4] hâline gelmelidir.
Lua ve R'de diziler 1'den başlar; bu nedenle son basamak n - 1 değil, n indeksindedir.

Sıkça sorulan sorular3

Plus One'ın zaman karmaşıklığı nedir?

Her iki yaklaşım da n basamak için O(n) zamanda çalışır; çünkü tüm basamakların 9 olduğu durumda her basamağa dokunulur. Erken çıkışlı sürüm, sondaki 9'lardan sonra durur ve yanıtın başına yeni bir basamak eklenmesi gerektiği durum dışında 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 sınırsız tamsayılar bulunur, bu nedenle dönüştürme bu dillerde işe yarar; ancak kod diğer dillere taşınamaz. Basamak basamak çalışmak hiçbir zaman taşmaya yol açmaz.

Rakam dizileri olarak saklanan iki sayıyı nasıl toplarsınız?

Her dizinin sonunda bir indeks olacak şekilde sütun yöntemini kullanın. Her sütunda iki basamağı, eksik basamağı 0 kabul ederek, eldeyle birlikte toplayın. Her iki dizinin elemanları tükendiğinde ve elde 0 olduğunda durun, ardından biriktirilen basamakları ters çevirin.

def plusOne(digits):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argüman

digits = [4, 3, 9]

Beklenen Çıktı

[4, 4, 0]