. Nombor Leksikografi

386. Nombor Leksikografi

Kesukaran: Sederhana

Topik: Carian Pertama Kedalaman, Cuba

Diberi integer n, kembalikan semua nombor dalam julat [1, n] diisih mengikut susunan leksikografi.

Anda mesti menulis algoritma yang berjalan dalam masa O(n) dan menggunakan ruang tambahan O(1).

Contoh 1:

• Input: n = 13
• Output: [1,10,11,12,13,2,3,4,5,6,7,8,9]

Contoh 2:

• Input: n = 2
• Output: 4
• Penjelasan: [1,2]

Kekangan:

• 1 <= n <= 5 * 10⁴

Penyelesaian:

Kita boleh mendekatinya menggunakan strategi seperti Depth-First Search (DFS).

Wawasan Utama:

• Tertib leksikografi pada asasnya ialah traversal prapesanan di atas pokok n-ary maya, di mana nod akar bermula pada 1, dan setiap nod mempunyai sehingga 9 anak, yang dibentuk dengan menambahkan digit (0 hingga 9).
• Kami boleh mensimulasikan traversal prapesanan ini dengan bermula dengan 1 dan menambahkan nombor berulang kali, memastikan kami tidak melebihi n yang diberikan.

Pendekatan:

1. Mulakan dengan nombor 1 dan cuba pergi lebih dalam dengan mendarab dengan 10 (iaitu, nombor leksikografi seterusnya dengan digit seterusnya).
2. Jika pergi lebih dalam (darab dengan 10) tidak mungkin (iaitu, melebihi n), tambahkan nombor, pastikan ia tidak memperkenalkan lompatan yang tidak sah merentasi puluhan (iaitu, dari 19 hingga 20).
3. Kami berundur apabila nombor semasa tidak dapat dipanjangkan lagi dan beralih ke nombor sah seterusnya.
4. Teruskan sehingga semua nombor hingga n diproses.

Mari laksanakan penyelesaian ini dalam PHP: 386. Nombor Leksikografi

<?php
/**
 * @param Integer $n
 * @return Integer[]
 */
function lexicalOrder($n) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage
$n1 = 13;
print_r(lexicalOrder($n1));

$n2 = 2;
print_r(lexicalOrder($n2));
?>




<h3>
  
  
  Penjelasan:
</h3>

<ul>
<li>Kami mengekalkan nombor semasa dan cuba pergi sedalam mungkin dengan mendarabkannya dengan 10 untuk mendapatkan nombor leksikografi seterusnya.</li>
<li>Apabila kita tidak boleh mendarab (kerana ia akan melebihi n), kita menambah bilangannya. Kami mengendalikan kes di mana kenaikan membawa kepada nombor seperti 20, 30, dsb., dengan menyemak sifar tertinggal dan melaraskan nombor semasa dengan sewajarnya.</li>
<li>Gelung berterusan sehingga kami telah menambah semua nombor hingga n dalam susunan leksikografi.</li>
</ul>

<h3>
  
  
  Contoh Panduan:
</h3>

<h4>
  
  
  Input: n = 13
</h4>

<ol>
<li>Mula pada 1.</li>
<li>Darab 1 dengan 10 -> 10.</li>
<li>Tambah 11, 12, 13.</li>
<li>Undur ke 2 dan teruskan peningkatan sehingga 9.</li>
</ol>

<h4>
  
  
  Output:
</h4>



<pre class="brush:php;toolbar:false">[1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]

Input: n = 2

1. Mula pada 1.
2. Alih ke 2.

Output:

[1, 2]

Kerumitan Masa:

• O(n) memandangkan setiap nombor daripada 1 hingga n diproses tepat sekali.

Kerumitan Ruang:

• O(1) ruang tambahan digunakan (tidak menghiraukan ruang yang digunakan untuk tatasusunan hasil).

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 . Nombor Leksikografi. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!