Reverse the Digits
Negatif olmayan bir tam sayı n veriliyor. Ondalık basamaklarını ters sırayla yazarak elde ettiğiniz sayıyı döndürün. Baştaki sıfırlar atılır; bu nedenle 120, 21 olur.
Fonksiyon
- ninteger
- tersine çevrilecek negatif olmayan tam sayı
- Döndürürinteger
- n sayısının rakamları, ters sırada bir sayı olarak
Kısıtlar
0 ≤ n < 109- Ters çevrilmiş sayı da işaretli 32 bitlik bir tamsayıya sığar.
Örnekler
- Girdi
- n = 1234
- Çıktı
- 4321
- Açıklama
1234sayısının rakamları 1, 2, 3 ve 4'tür. Sondan okunduğunda 4, 3, 2 ve 1 olur; bu da4321'dir.
- Girdi
- n = 120
- Çıktı
- 21
- Açıklama
- Tersten okunduğunda,
120rakamları 0, 2 ve 1'i verir. Baştaki sıfır bir sayıda sayılmaz, bu nedenle cevap21'dir.
- Girdi
- n = 0
- Çıktı
- 0
- Açıklama
0tek bir basamağa sahiptir ve ters çevrildiğinde yine0olur.
Gönderirken +13 gizli test
Ek soru
n herhangi bir 32 bitlik tam sayı olabilirse, ters çevrilmiş hâli sığmayabilir. Çarpma işlemi taşmaya yol açmadan önce bunu nasıl tespit edersin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Bir sayının son basamağını hangi aritmetik işlem verir ve hangi işlem bu basamağı siler?
n % 10son basamaktır ven / 10(tam sayı bölmesi) bu basamağı atar. Bir sayınındbasamağını başka bir sayı olanr'nin sonuna eklemek içinr * 10 + dhesaplayın.result = 0ile başla.n,0'dan büyük olduğu sürece son basamağınıresult'ın sonuna ekle ve bu basamağın'den çıkar. Baştaki sıfırlar hiçbir zaman görünmez, çünkü0 * 10 + 0yine0olur.
Çözüm
Ondalık metni ters çevirmek çoğu dilde tek satırda yapılır ve bu, ilk yanıt olarak gayet uygundur. Görüşmeciler genellikle aynı sonucu dizeler kullanmadan elde etmenizi isteyerek devam eder. Aritmetik yöntem iki işleme dayanır: n % 10 son basamağı okur ve n / 10 (tamsayı bölmesi) bu basamağı kaldırır.
Ondalık metni tersine çevir
Sezgi
Bir sayının rakamları, ondalık gösterimindeki karakterlerin aynısıdır. n değerini metne dönüştür, karakterleri ters çevir ve metni tekrar sayı olarak oku. 1234, "1234" olur; ardından "4321" olur ve son olarak 4321 elde edilir.
Baştaki sıfırlar kendiliğinden halledilir. 120 değerini ters çevirmek "021" metnini verir; bunu sayı olarak ayrıştırmak baştaki sıfırı yok sayar ve 21 değerini döndürür.
10^9 değerinden küçük bir sayı en fazla 9 basamaklıdır ve işlem miktarı ile ek metnin uzunluğu basamak sayısıyla birlikte artar; bu da O(log n) olur.
Algoritma
ndeğerini ondalık metne dönüştür.- Karakterleri tersine çevir.
- Tersine çevrilmiş metni tam sayı olarak ayrıştır ve döndür.
def reverseDigits(n):
# int() ignores the leading zeros that trailing zeros turn into.
return int(str(n)[::-1])Aritmetikle basamakları yığına ekleme ve yığından çıkarma
Sezgi
n sayısının sonundaki rakamları teker teker alıp her birini yeni bir sayının sonuna ekle. n % 10, n sayısının son basamağıdır ve tamsayı bölmesiyle n / 10 bu basamağı düşürür. d basamağını result sayısının sonuna eklemek için, mevcut değeri bir basamak sola kaydır ve d basamağını birler basamağına koy: result * 10 + d.
1234 için result, 4, 43, 432, 4321 olurken n, 123, 12, 1, 0 olur. Döngü, n değeri 0 olduğunda durur; bu nedenle rakam sayısı kadar çalışır.
Başta sıfırlar hiçbir zaman görünmez. 120 için alınan ilk rakam 0’dır ve 0 * 10 + 0 yine 0 olduğundan geride iz bırakmaz. n = 0 için döngü hiç çalışmaz ve sonuç 0 olur. Yalnızca iki tamsayı tutulur, bu nedenle ek alan O(1)’dir.
Algoritma
result = 0olarak ayarla.ndeğeri0'dan büyük olduğu sürece son basamağın % 10ile hesapla.result = result * 10 + digitolarak ayarla.- Tam sayı bölmesi kullanarak
n = n / 10ile basamağı kaldır. resultdeğerini döndür.
def reverseDigits(n):
result = 0
while n > 0:
result = result * 10 + n % 10 # push the last digit of n
n //= 10 # drop it from n
return result
Tuzaklar ve uç durumlar
Hataların çoğu bölmeden ve döngünün bitiş koşulundan kaynaklanır.
- Tamsayı bölmesi gereken yerde normal bölme kullanmak. JavaScript, Python 3 ve Lua'da
n / 10,123.4sonucunu verir; bu nedenlenbir daha hiçbir zaman tam sayı olmaz veresultkesirlerle dolar.Math.floor,//veya dilinizin tamsayı bölmesini kullanın. - Döngüyü
while n >= 10şeklinde yazmak. Bu, son basamağa gelmeden durur; dolayısıyla1234,432olarak geri döner. - Ters çevrilmiş metni sayıya dönüştürmeden döndürmek.
"021",21sayısı değildir ve beklenen yanıtla karşılaştırma başarısız olur. - R'de bir double değerini
as.characterile biçimlendirmek.nbir double olarak saklandığında,100000000değerini1e+08olarak yazdırır ve ters çevrilmiş metin80+e1olur.format(n, scientific = FALSE)kullanın.
Sıkça sorulan sorular4
Bir sayıyı dizgeye dönüştürmeden basamaklarını nasıl tersine çevirirsiniz?
Sayı 0 olana kadar iki adımı tekrarla: son basamağı n % 10 ile al ve result = result * 10 + digit ile sonuca ekle, ardından tamsayı bölmesi kullanarak n = n / 10 ile basamağı düşür. 1234 için sonuç 4, 43, 432 ve 4321 olarak büyür.
Sayıyı ters çevirdiğinizde sondaki sıfırlara ne olur?
Bunlar, bir sayıda bulunmayan baştaki sıfırlar hâline gelir ve bu yüzden kaybolurlar. 120 sayısını ters çevirmek 21 sonucunu verir; 100000000 sayısını ters çevirmek ise 1 sonucunu verir. Aritmetik döngü bunları kendiliğinden atar, çünkü boş bir sonuca 0 eklemek sonucu yine 0 bırakır.
Tam sayıyı tersine çevirmenin zaman karmaşıklığı nedir?
Döngü her ondalık basamak için bir kez çalışır ve n sayısı yaklaşık log10(n) + 1 basamağa sahiptir; bu nedenle zaman karmaşıklığı O(log n)'dir. Aritmetik sürüm O(1) ek alan kullanır; dizge sürümü ise basamakları metin olarak saklar ve bu da O(log n) alan gerektirir.
Bir tamsayının basamaklarını ters çevirmek taşmaya yol açabilir mi?
Evet, girdi herhangi bir 32 bit tam sayı olabiliyorsa. 1000000009 sığar, ancak tersi olan 9000000001 sığmaz. Burada n, 10^9 değerinden küçüktür; bu nedenle tersinin en fazla 9 basamağı vardır ve her zaman sığar. Daha büyük girdilerde, her çarpmadan önce result > (INT_MAX - digit) / 10 koşulunu kontrol edin.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def reverseDigits(n):
# Kodu buraya yazınDurum 1
Durum 2
Durum 3
Girdi
n = 1234
Beklenen
4321