Cari cara yang cekap

Hai, Rakyat! Hari ini saya menyelesaikan tiga masalah pada LeetCode : Laluan Unik, matriks Lingkaran dan N-Queens. Mari kita hadapi masalah ini.

Masalah laluan unik

Kami diberi dua nombor, mewakili bilangan baris dan bilangan lajur. Tugas kami adalah untuk mencari jumlah laluan unik untuk mencapai kedudukan (m-1,n-1) dari (0,0). Untuk menyelesaikan masalah ini, kita boleh mengikuti pendekatan rekursif. Kita boleh bermula dari (0,0) mencari langkah secara rekursif untuk mengembara ke kanan dan bawah sehingga kita mencapai kedudukan yang diperlukan. Untuk mencari jumlah laluan unik, kami akan menambah langkah yang betul ke langkah bawah dan mengembalikannya. Walau bagaimanapun, terdapat isu kecil dengan pendekatan ini: penyelesaian mungkin berulang beberapa kali. Untuk mengatasinya, pendekatan alternatif ialah menggunakan matriks DP. Kami mencipta matriks DP dengan bilangan baris dan lajur yang sama sebagai input dan kami memulakan semua kedudukan matriks DP dengan 1. Akhir sekali, kami mengembalikan nilai dalam sel lats matriks DP sebagai jumlah nombor di luar laluan unik.

Matriks Lingkaran

Kami diberikan dengan matriks dan kami perlu mengembalikan senarai yang mengandungi unsur-unsur matriks dalam susunan lingkaran. Untuk menyelesaikan masalah ini, kita boleh menggunakan had pengindeksan sebagai syarat untuk menjalankan gelung. Kita melintasi dari kiri ke kanan matriks kita boleh menggunakan satu untuk gelung. Kemudian, kami bergerak dari sudut kanan atas ke sudut kanan bawah dengan gelung lain. Kami melintasi dari sudut kanan bawah ke sudut kiri bawah menggunakan gelung ketiga. Akhir sekali, kami bergerak dari sudut kiri bawah ke sudut kiri atas dengan gelung keempat. Dengan cara ini, kami menggunakan empat gelung berbeza untuk melintasi keempat-empat arah, mengawalnya dengan had pengindeksan.

N-Queens

Kami diberi nombor input n, kami perlu mencari bilangan cara untuk meletakkan n ratu dalam matriks nxn supaya tiada dua ratu akan menyerang satu sama lain. Ini bermakna tiada dua ratu harus berada dalam baris, lajur atau pepenjuru yang sama. Untuk menyelesaikan masalah ini, kita boleh menggunakan konsep rekursi dan backtracking. Mula-mula kita boleh melakukan rekursi untuk mengulangi proses beberapa kali. kerana, kita perlu mencari semua cara yang mungkin untuk meletakkan ratu. Backtracking dilakukan apabila kita tidak menemui kedudukan yang betul untuk meletakkan ratu maka kita boleh menggantikan 'Q' dengan '.' dan ulangi proses untuk kedudukan seterusnya.

Kami boleh mengoptimumkan penyelesaian di atas dengan menggunakan tiga senarai. Satu senarai adalah untuk menjejaki bilangan baris. katakan kita mempunyai n baris, kita akan meletakkan n sifar dalam senarai dan menggantikan sifar masing-masing dengan satu jika baris tertentu itu mempunyai ratu. Ini akan mengelakkan pengunduran yang tidak perlu. Begitu juga, senarai kedua adalah untuk pepenjuru bawah, dan senarai ketiga adalah untuk pepenjuru atas. Kedua-dua senarai pepenjuru mempunyai elemen 2n-1 semuanya pada mulanya ditetapkan kepada sifar. Semasa kami merentasi matriks untuk meletakkan ratu, kami mengemas kini senarai baris atau pepenjuru masing-masing dengan menggantikan 0 dengan 1 apabila ratu diletakkan. Ini menunjukkan bahawa tiada lagi ratu boleh diletakkan dalam pepenjuru atau baris tersebut. Dengan cara ini, pendekatan ini berfungsi dengan cekap.

Saya harap pengalaman saya akan membantu.

Atas ialah kandungan terperinci Cari cara yang cekap. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!