Reverse the Digits

Q: Bisakah membalikkan bilangan bulat menyebabkan overflow?

Ya, jika input dapat berupa bilangan bulat 32-bit apa pun: 1000000009 muat, tetapi kebalikannya, 9000000001 , tidak muat. Di sini n kurang dari 10^9 , jadi bilangan kebalikannya memiliki paling banyak 9 digit dan selalu muat.

PemulaMatematika dan simulasi

+10

Kamu mendapatkan bilangan bulat nonnegatif n. Kembalikan bilangan yang diperoleh dengan menuliskan digit desimalnya dalam urutan terbalik. Nol yang berada di bagian depan akan dihilangkan, jadi 120 menjadi 21.

Fungsi

reverseDigits(n: integer) → integer

ninteger: bilangan bulat nonnegatif yang akan dibalik
Mengembalikaninteger: digit-digit n dalam urutan terbalik, sebagai sebuah bilangan

Batasan

0 ≤ n < 10⁹
Angka hasil pembalikan juga muat dalam bilangan bulat bertanda 32-bit.

Contoh

Input: n = 1234
Output: 4321
Penjelasan: Digit dari 1234 adalah 1, 2, 3, dan 4. Jika dibaca dari belakang, digitnya adalah 4, 3, 2, dan 1, yaitu 4321.

Input: n = 120
Output: 21
Penjelasan: Jika dibaca dari belakang, 120 menghasilkan digit 0, 2, dan 1. Nol di depan tidak dihitung dalam angka, jadi jawabannya adalah 21.

Input: n = 0
Output: 0
Penjelasan: 0 memiliki satu digit, dan jika dibalik hasilnya 0 lagi.

Pertanyaan lanjutan

Jika n bisa berupa bilangan bulat 32-bit apa pun, nilai kebalikannya mungkin tidak muat. Bagaimana kamu mendeteksinya sebelum perkalian menyebabkan overflow?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Membalik teks desimal hanya membutuhkan satu baris di sebagian besar bahasa dan merupakan jawaban pertama yang bagus. Pewawancara biasanya kemudian meminta hasil yang sama tanpa menggunakan string. Versi aritmetika ini menggunakan dua operasi: n % 10 membaca digit terakhir dan n / 10 (pembagian bilangan bulat) menghapusnya.

Balikkan teks desimal

Intuisi

Digit-digit suatu angka adalah karakter dalam teks desimalnya. Ubah n menjadi teks, balik urutan karakternya, lalu parse hasilnya: 1234 menjadi "1234", "4321", lalu 4321. Nol di depan akan teratasi dengan sendirinya, karena parsing "021" menghasilkan 21.

Jumlah operasi dan panjang teks sama-sama bertambah seiring jumlah digit, yaitu O(log n), paling banyak 9 digit di sini.

Algoritma

Ubah n menjadi teks desimal.
Balik urutan karakter.
Uraikan teks yang sudah dibalik sebagai bilangan bulat, lalu kembalikan.

def reverseDigits(n):
    # int() ignores the leading zeros that trailing zeros turn into.
    return int(str(n)[::-1])

Ambil dan tambahkan digit dengan operasi aritmetika

Intuisi

Ambil digit dari akhir n dan tambahkan satu per satu ke akhir result: result * 10 + d menggeser isi saat ini satu tempat ke kiri dan menempatkan d di posisi satuan. Untuk 1234, result menjadi 4, 43, 432, 4321, sementara n menjadi 123, 12, 1, 0. Perulangan berjalan sekali untuk setiap digit.

Nol di depan tidak pernah muncul: untuk 120, digit pertama yang diambil adalah 0, dan 0 * 10 + 0 tetap bernilai 0. Untuk n = 0, perulangan tidak berjalan dan jawabannya adalah 0. Hanya dua bilangan bulat yang disimpan, jadi ruang ekstra adalah O(1).

Algoritma

Tetapkan result = 0.
Selama n lebih besar dari 0, hitung digit terakhir n % 10.
Tetapkan result = result * 10 + digit.
Buang digit tersebut dengan n = n / 10, menggunakan pembagian bilangan bulat.
Kembalikan result.

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

Jebakan dan kasus tepi

Menggunakan pembagian biasa saat kamu memerlukan pembagian bilangan bulat. Dalam JavaScript, Python 3, dan Lua, n / 10 menghasilkan 123.4, sehingga n tidak pernah menjadi bilangan bulat lagi dan result terisi dengan pecahan. Gunakan Math.floor, //, atau pembagian bilangan bulat dalam bahasamu.
Menulis perulangan dengan kondisi while n >= 10. Perulangan berhenti sebelum digit terakhir, sehingga 1234 menghasilkan 432.
Mengembalikan teks yang sudah dibalik tanpa mengubahnya menjadi angka. "021" bukan angka 21, sehingga perbandingan dengan jawaban yang diharapkan gagal.
Memformat double di R dengan as.character. Saat n disimpan sebagai double, nilainya dicetak sebagai 1e+08, bukan 100000000, dan teks yang sudah dibalik menjadi 80+e1. Gunakan format(n, scientific = FALSE).

Pertanyaan yang sering diajukan3

Apa yang terjadi pada nol di akhir saat kamu membalik angka?

Angka-angka itu akan menjadi nol di depan, yang tidak dimiliki oleh sebuah angka, jadi angka-angka itu menghilang. Membalik 120 menghasilkan 21, dan membalik 100000000 menghasilkan 1. Perulangan aritmetika menghilangkannya sendiri, karena menambahkan 0 ke hasil yang kosong membuatnya tetap bernilai 0.

Berapa kompleksitas waktu untuk membalikkan bilangan bulat?

Perulangan berjalan sekali untuk setiap digit desimal, dan sebuah angka n memiliki sekitar log10(n) + 1 digit, sehingga kompleksitas waktunya adalah O(log n). Versi aritmetika menggunakan ruang ekstra O(1); versi string menyimpan digit sebagai teks, sehingga kompleksitas ruangnya O(log n).

Bisakah membalikkan bilangan bulat menyebabkan overflow?

Ya, jika input dapat berupa bilangan bulat 32-bit apa pun: 1000000009 muat, tetapi kebalikannya, 9000000001, tidak muat. Di sini n kurang dari 10^9, jadi bilangan kebalikannya memiliki paling banyak 9 digit dan selalu muat.

def reverseDigits(n):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

n = 1234

Output yang diharapkan