Rumah > hujung hadapan web > tutorial js > Meditasi LeetCode: Jumlah Dua Integer

Meditasi LeetCode: Jumlah Dua Integer

Patricia Arquette
Lepaskan: 2025-01-04 06:43:40
asal
515 orang telah melayarinya

Penerangan yang diberikan untuk Jumlah Dua Integer adalah sangat mudah:

Diberi dua integer a dan b, kembalikan jumlah dua integer tanpa menggunakan operator dan -.

Contohnya:

Input: a = 1, b = 2
Output: 3
Salin selepas log masuk

Atau:

Input: a = 2, b = 3
Output: 5
Salin selepas log masuk

Dalam masalah terakhir siri ini, kami akan menutup dengan menambah dua integer menggunakan manipulasi bit dan bukannya operator tambah kesayangan kami.

Menambah dua bit, sama ada daripadanya hanya boleh 1 atau 0, tidak mempunyai banyak hasil yang berbeza-beza.
Jika kita menambah dua bit iaitu 1 dan 0 (atau, 0 dan 1), hasilnya akan menjadi 1. Jika kita menambah dua bit 0, hasilnya ialah 0. Jika, bagaimanapun, kita menambah dua 1 bit, kita mempunyai carry — yang bermaksud kita perlu menulis 0 dalam output, tetapi juga membawa 1.

Sebagai contoh, menambah 2 dan 3 akan menghasilkan 5, dan kami akan mempunyai nilai bawa semasa operasi:

LeetCode Meditations: Sum of Two Integers

Tanpa memikirkan nilai bawaan, output yang perlu kita miliki selepas menambah dua bit adalah serupa dengan apa yang kita akan ada selepas operasi XOR. Jika kita mempunyai bit yang berbeza (0 dan 1, atau, 1 dan 0), output akan menjadi 1, jika tidak 0 (menambah 0 dan 0, atau , 1 dan 1).

Jadi, operasi XOR boleh membantu kami dengan output.

Bagaimana dengan pembawa?

Kami mempunyai nilai bawa hanya apabila kedua-dua bit adalah 1 — yang kelihatan seperti operasi DAN.

Jadi, operasi DAN boleh membantu kami dengan membawa.

Juga ambil perhatian bahawa nilai bawa dianjak ke kiri, yang mana kami juga mempunyai operator anjakan kiri yang berguna.

Jadi, output dan carry kami boleh kelihatan seperti ini:

let output = a ^ b;
let carry = (a & b) << 1;
Salin selepas log masuk

Kami boleh terus mengubah suai dua nilai yang kami ada dan teruskan sehingga kami tidak mempunyai sebarang nilai bawaan. Kita boleh mengubah suai a menjadi output, dan b menjadi carry, dan mengembalikan a, yang memegang output akhir pada penghujungnya.

Secara keseluruhan, penyelesaian akhir mungkin kelihatan seperti ini dalam TypeScript:

function getSum(a: number, b: number): number {
  // while we still have carry
  while (b !== 0) {
    let output = a ^ b;
    let carry = (a & b) << 1;
    a = output;
    b = carry;
  }

  return a;
}
Salin selepas log masuk

Kerumitan masa dan ruang

Kedua-dua a dan b ialah nilai malar, dan kami juga tidak memerlukan struktur data tambahan yang saiznya akan berkembang secara berkadar dengan input, jadi kedua-dua masa dan kerumitan ruang kami akan tetap, O(1)O(1) O(1) .


Dan, itulah masalah terakhir siri Meditasi LeetCode! Kami akan menyelesaikannya dengan kesimpulan dalam siaran seterusnya — sehingga itu, selamat mengekod.

Atas ialah kandungan terperinci Meditasi LeetCode: Jumlah Dua Integer. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

sumber:dev.to
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Artikel terbaru oleh pengarang
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan