Palindrome Number

Q: Negatif bir sayı palindrom mudur?

Hayır. Tersten okunduğunda -121 , 121- olur ve eksi işaretinin diğer uçta eşleşen bir karakteri yoktur. Bu nedenle her negatif tam sayı false döndürür.

Q: Palindrom Sayının zaman karmaşıklığı nedir?

Her iki yaklaşım da O(log x) zamanda çalışır; çünkü x sayısı yaklaşık log10(x) basamak içerir ve her basamak bir kez işlenir. Dize yaklaşımı metin için O(log x) ek alan kullanırken, yarısını ters çevirme yaklaşımı O(1) alan kullanır.

KolayMatematik ve simülasyon

+10

Bir sayı, rakamları soldan sağa ve sağdan sola aynı şekilde okunduğunda (örneğin 1221) palindromdur. Bir tamsayı x verildiğinde, palindromsa true, değilse false döndürün. Negatif bir sayı hiçbir zaman palindrom sayılmaz, çünkü eksi işaretinin diğer uçta bir eşleşeni yoktur.

Fonksiyon

isPalindrome(x: integer) → boolean

xinteger: kontrol edilecek tam sayı, negatif olabilir
Döndürürboolean: true, x her iki yönde de aynı şekilde okunuyorsa; aksi takdirde false

Kısıtlar

-2³¹ ≤ x ≤ 2³¹-1
Her negatif sayı false değerini döndürür.

Örnekler

Girdi: x = 121
Çıktı: true
Açıklama: Tersten okunduğunda 121 hâlâ 121'dir, bu yüzden yanıt true.

Girdi: x = -121
Çıktı: false
Açıklama: Tersten okunduğunda, -121 121- olur; bu farklı bir metindir, dolayısıyla yanıt false olur.

Ek soru

Tam sayıyı bir dizgeye dönüştürmeden çözebilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Bir sayı, tersiyle aynı olduğunda palindromdur. Metin olarak bu, tek bir karşılaştırmadır. Metin kullanmadan, ters çevrilmiş sayının tamamını yeniden oluşturmak taşmaya neden olabilir; bu yüzden rakamların yalnızca ikinci yarısını ters çevir ve ilk yarıyla karşılaştır.

Karakter dizgesini tersiyle karşılaştırın

Sezgi

Sayıyı metin olarak yazın ve tersiyle karşılaştırın. Negatif sayılar için özel bir duruma gerek yoktur: -121 eksi işaretiyle başlar ve bir rakamla biter, bu nedenle tersi olan 121- ile hiçbir zaman eşit olmaz.

Metinde her rakam için bir karakter bulunur; bunların sayısı yaklaşık log10(x) kadardır ve burada en fazla 11'dir. Bunun karşılığında ek bir metin dizisi gerekir.

Algoritma

x'i bir dizeye, s'ye dönüştür.
s'yi ters çevir.
s'nin tersiyle eşit olup olmadığını döndür.

def isPalindrome(x):
    s = str(x)
    # A minus sign sits only at the front, so a negative never matches its reverse.
    return s == s[::-1]

Sayının yarısını ters çevir

Sezgi

x % 10 son basamağı verir ve 10’a tam sayı bölmesi bu basamağı kaldırır. x sayısının sonundaki basamakları ikinci bir sayı olan half üzerine taşıyarak kaldırdığınız basamakların tersini oluşturursunuz. half, x sayısının geriye kalan kısmından büyük veya ona eşit olana kadar durun: basamakların yarısını almış olursunuz. 1221 için işlem x = 12 ve half = 12 değerleriyle biter; bu bir palindromdur. Basamak sayısı tek olduğunda half orta basamağı da içerir: 12321 için işlem x = 12 ve half = 123 değerleriyle biter; bu nedenle x ile half / 10 değerlerini karşılaştırırsınız.

Döngüden önce iki durumu ele alın. Negatif bir sayı hiçbir zaman palindrom değildir. 0 ile biten bir sayının 0 ile başlaması gerekir; bunu yalnızca 0 yapar. Bu kontrol olmadan 10 için işlem x = 0 ve half = 1 değerleriyle biter ve x == half / 10 yanlışlıkla doğru olur. half hiçbir zaman 6 basamağı aşmaz, bu nedenle herhangi bir tam sayı türüne sığar.

Algoritma

x negatifse veya 0 ile bitip 0 değilse false döndür.
half = 0 olarak ayarla.
x > half olduğu sürece half = half * 10 + x % 10 olarak ayarla ve x'i tam sayı bölmesiyle 10'a böl.
x == half (basamak sayısı çift) veya x == half / 10 (basamak sayısı tek) ise true döndür.

def isPalindrome(x):
    if x < 0:
        return False
    original, reversed_num = x, 0
    while x > 0:
        reversed_num = reversed_num * 10 + x % 10
        x //= 10
    return original == reversed_num

Tuzaklar ve uç durumlar

Negatif sayıları göz ardı etmek. Kalanın işaretini koruduğu dillerde -121 sayısını ters çevirmek -121 sonucunu verir ve kontrol başarılı olur. -1 // 10 işleminin -1 olduğu Python'da while x != 0 döngüsü hiç bitmez.
0 ile biten sayıları reddetmemek. Yarı ters çevirme yöntemi bu durumda 10 sayısını kabul eder. 0 kendi başına bir palindromdur.
Sayının tamamını 32 bitlik bir tamsayıda ters çevirmek. 2147483647 sayısının tersi sığmaz.
Dilin kesirli bölme yaptığı yerlerde / kullanmak. JavaScript'te Math.floor(x / 10), Python'da //, R'de %/% ve Dart'ta ~/ kullanın.
Döngü x değerini değiştirdikten sonra sayının tamamının tersini x ile karşılaştırmak. Orijinal sayının bir kopyasını saklayın.

Sıkça sorulan sorular3

Negatif bir sayı palindrom mudur?

Hayır. Tersten okunduğunda -121, 121- olur ve eksi işaretinin diğer uçta eşleşen bir karakteri yoktur. Bu nedenle her negatif tam sayı false döndürür.

Sayıyı neden yalnızca tersine çeviriyoruz?

Her basamağı ters çevirmek 32 bitlik bir tamsayıda taşmaya neden olabilir: 2147483647 sayısının tersi, en büyük int değerinden büyüktür. Basamakların yarısı her zaman sığar ve döngü işin yarısını yapar.

Palindrom Sayının zaman karmaşıklığı nedir?

Her iki yaklaşım da O(log x) zamanda çalışır; çünkü x sayısı yaklaşık log10(x) basamak içerir ve her basamak bir kez işlenir. Dize yaklaşımı metin için O(log x) ek alan kullanırken, yarısını ters çevirme yaklaşımı O(1) alan kullanır.

def isPalindrome(x):
    # Kodu buraya yazın

Test #1

Test #2

Argüman

x = 121

Beklenen Çıktı

true