. Pertukaran Maksimum

670. Pertukaran Maksimum

Kesukaran: Sederhana

Topik: Matematik, Tamak

Anda diberi nombor integer. Anda boleh menukar dua digit paling banyak sekali untuk mendapatkan nombor nilai maksimum.

Kembalikan nombor nilai maksimum yang anda boleh dapat.

Contoh 1:

• Input: nombor = 2736
• Output: 7236
• Penjelasan: Tukar nombor 2 dan nombor 7.

Contoh 2:

• Input: nombor = 9973
• Output: 9973
• Penjelasan: Tiada pertukaran.

Kekangan:

• 0 <= bilangan <= 10⁸

Penyelesaian:

Kita boleh mengikut pendekatan tamak. Berikut ialah penjelasan langkah demi langkah dan penyelesaiannya:

Pendekatan:

1. Tukar Nombor kepada Tatasusunan: Memandangkan digit perlu ditukar, menukar nombor kepada tatasusunan digit memudahkan untuk mengakses dan memanipulasi digit individu.
2. Jejak Kejadian Paling Kanan Setiap Digit: Simpan kedudukan paling kanan setiap digit (0-9) dalam tatasusunan.
3. Cari Peluang Swap Terbaik: Lintas digit nombor dari kiri ke kanan, dan untuk setiap digit, semak sama ada terdapat digit yang lebih tinggi yang muncul kemudian. Jika ya, tukarkannya untuk memaksimumkan bilangannya.
4. Lakukan Tukar dan Putus: Sebaik sahaja pertukaran optimum ditemui, lakukan pertukaran dan putuskan gelung.
5. Tukar Tatasusunan Kembali kepada Nombor: Selepas pertukaran, tukarkan tatasusunan digit kembali kepada nombor dan kembalikannya.

Mari laksanakan penyelesaian ini dalam PHP: 670. Pertukaran Maksimum

  
  
  Penjelasan:




Langkah 1: strval($num) menukar integer menjadi rentetan dan str_split($numStr) membahagikannya kepada tatasusunan digit.

Langkah 2: Tatasusunan terakhir menjejaki indeks paling kanan setiap digit dari 0 hingga 9.

Langkah 3: Kami mengulangi setiap digit dan mencari digit yang lebih besar yang boleh ditukar.

Langkah 4: Jika digit yang lebih besar yang sesuai ditemui (yang muncul kemudian dalam nombor), digit tersebut ditukar.

Langkah 5: Tatasusunan yang diubah suai ditukar kembali kepada rentetan dan kemudian kepada integer menggunakan intval().



  
  
  Kerumitan:




Kerumitan Masa: O(n), dengan n ialah bilangan digit dalam nombor. Ini kerana kami membuat hantaran melalui nombor untuk mengisi tatasusunan terakhir dan satu lagi hantaran untuk mencari pertukaran yang optimum.

Kerumitan Ruang: O(1) (mengabaikan saiz input) kerana tatasusunan terakhir ditetapkan dengan 10 elemen.


Penyelesaian ini cekap mencari nilai maksimum dengan menukar digit sekali sahaja, seperti yang diperlukan.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:


LinkedIn
GitHub



          

            
  

            
        
Atas ialah kandungan terperinci . Pertukaran Maksimum. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!