Berbagi teknologi

Metode mundur Likou

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Apa itu kemunduran?

Saat mencari node tertentu, jika kami menemukan bahwa node saat ini (dan sub-nodenya) bukan target yang diperlukan, kami kembali ke node asli untuk melanjutkan pencarian, dan memulihkan status node saat ini yang telah diubah.
Ingat dua tip kecil:Yang pertama adalah meneruskan status dengan referensi (&), dan yang kedua adalah mengubah semua modifikasi status setelah rekursi selesai.
Umumnya ada dua situasi untuk melakukan modifikasi backtrack. Yang pertama adalah memodifikasi output terakhir, seperti permutasi dan kombinasi, yang lainnya adalah memodifikasi target akses.
Ingat, misalnya, mencari string dalam matriks.

46.Pengaturan penuh

tema

Diberikan array tanpa nomor duplikatnums, kembalikan itusemua kemungkinan permutasi .kamu bisadalam urutan apa punKembalikan jawaban.

Contoh 1:

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Contoh 2:

输入：nums = [0,1]
输出：[[0,1],[1,0]]

Contoh 3:

输入：nums = [1]
输出：[[1]]

petunjuk:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • numssemua bilangan bulat masukberbeda satu sama lain​​​​​​​
menjawab
Untuk menampilkan semua kombinasi array yang diurutkan, kita dapat menggunakan metode backtracking.
Tentukan dulu suatu posisi, lalu tukarkan dengan setiap posisi berikutnya. Setelah berganti, pergi ke lokasi berikutnya. Kemudian setelah rangkaian langkah ini selesai, Anda perlu mengganti yang diganti. Itu adalah metode kemunduran.
  1. class Solution {
  2. public:
  3.     vector<vector<int>> permute(vector<int>& nums) {
  4.         vector<vector<int>> ans;
  5.         back(nums,0,ans);
  6.         return ans;
  7.     }
  8.     void back(vector<int>& nums,int n,vector<vector<int>>& ans){
  9.         int i;
  10.         if(n==nums.size()-1)
  11.             ans.push_back(nums);
  12.         for(i=n;i<nums.size();i++){
  13.             swap(nums[i],nums[n]);
  14.             back(nums,n+1,ans);
  15.             swap(nums[i],nums[n]);
  16.         }
  17.     }
  18. };

77. Kombinasi

77. Kombinasi

tema

Diberikan dua bilangan bulatnDank, rentang pengembalian[1, n]semua mungkin masukkkombinasi angka.

Anda dapat menekanada pesananKembalikan jawaban.

Contoh 1:

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Contoh 2:

输入：n = 1, k = 1
输出：[[1]]

petunjuk:

  • 1 <= n <= 20
  • 1 <= k <= n

题解

Tetapkan hitungan dan hitung jumlahnya masing-masing. Saat count==k, masukkan ke dalam array. Berbeda dengan sebelumnya yang merupakan permutasi dan kombinasi. Ini seperti memilih sebuah array.

Mulai dari 1-n, siapkan array tambahan untuk menyimpan hasil setiap kali. Hitungan berubah secara dinamis. Setelah menetapkan i, hitungan bertambah satu, dan nomor dipilih dari (i+1, n) di dfs. Hitung-- setelah menelusuri kembali.

  1. class Solution {
  2. public:
  3.     vector<vector<int>> combine(int n, int k) {
  4.         vector<vector<int>> ans;
  5.         vector<int> c(k,0);
  6.         int count;
  7.         dfs(n,k,1,ans,c,count);
  8.         return ans;
  9.     }
  10.     void dfs(int n,int k,int level,vector<vector<int>>& ans,vector<int>& c,int& count){
  11.         int i;
  12.  
  13.         if(count==k){
  14.             ans.push_back(c);
  15.             return ;
  16.         }
  17.             
  18.         for(i=level;i<=n;i++){
  19.             c[count++]=i;
  20.             dfs(n,k,i+1,ans,c,count);
  21.             --count;
  22.         }
  23.     }
  24. };

79. Pencarian satuan

79. Pencarian kata

tema

diberikan am x nKisi karakter 2Dboarddan kata stringword .jikawordada di grid, kembalitrue; Jika tidak, kembalikanfalse 。

Kata-kata harus dibentuk dari huruf-huruf dalam sel yang berdekatan sesuai urutan abjad, di mana sel yang "berdekatan" adalah sel yang berdekatan secara horizontal atau vertikal. Huruf dalam sel yang sama tidak boleh digunakan berulang kali.

Contoh 1:

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

Contoh 2:

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

Contoh 3:

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false

petunjuk:

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • boardDanwordHanya terdiri dari huruf besar dan kecil bahasa Inggris

menjawab

Rutinitas serupa.

Metode dfs + backtracking pertama-tama menentukan kunjungan untuk menandai apakah lokasi telah ditandai selama setiap pencarian untuk mencegah lokasi yang sama dikunjungi berkali-kali.

Untuk suatu lokasi, penilaian batas perlu dilakukan untuk menentukan apakah lokasi tersebut melintasi batas. Kemudian tentukan apakah sudah dikunjungi, apakah berhasil ditemukan, dan apakah surat pada posisinya berbeda dengan surat sasaran.

dfs, cari di sekitar.

  1. class Solution {
  2. public:
  3.     bool exist(vector<vector<char>>& board, string word) {
  4.         if(board.empty())
  5.             return false;
  6.         int m=board.size(),n=board[0].size();
  7.         vector<vector<bool>> visit(m,vector<bool>(n,false));
  8.         int i,j;
  9.         bool find=false;
  10.         for(i=0;i<m;i++){
  11.             for(j=0;j<n;j++)
  12.                 back(i,j,board,word,find,visit,0);
  13.         }
  14.         return find;
  15.     }
  16.     void back(int i,int j,vector<vector<char>>& board,string& word,
  17.     bool& find,vector<vector<bool>>& visit,int level){
  18.         if(i<0||i>=board.size()||j<0||j>=board[0].size())
  19.             return ;
  20.       
  21.         if(visit[i][j]||find||board[i][j]!=word[level])
  22.             return ;
  23.         if(level==word.size()-1){
  24.             find=true;
  25.             return ;
  26.         }
  27.         visit[i][j]=true;
  28.         back(i+1,j,board,word,find,visit,level+1);
  29.         back(i-1,j,board,word,find,visit,level+1);
  30.         back(i,j+1,board,word,find,visit,level+1);
  31.         back(i,j-1,board,word,find,visit,level+1);
  32.         visit[i][j]=false;
  33.     }
  34. };

51.N Ratu

51. Ratu N

tema

Menurut aturan catur, seorang ratu dapat menyerang bidak pada baris atau kolom yang sama atau pada diagonal yang sama.

n Masalah RatuYang dipelajari adalah bagaimana caranyanratu ditempatkan din×ndi papan catur, dan membuat para ratu tidak bisa saling menyerang.

Memberi Anda bilangan bulatn, mengembalikan semua berbedaN masalah ratusolusinya.

Setiap solusi mengandung yang berbedan Masalah RatuRencana penempatan bidak catur, dalam rencana ini'Q'Dan'.'Mereka masing-masing mewakili ratu dan kursi kosong.

Contoh 1:

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

Contoh 2:

输入：n = 1
输出：[["Q"]]

petunjuk:

  • 1 <= n <= 9

题意

N Queen memerlukan tiga fungsi pelabelan, satu adalah kolom, satu adalah diagonal utama, dan yang lainnya adalah diagonal sekunder.

Karena pasti akan ada ratu yang ditempatkan di setiap baris, maka itu dilalui baris demi baris. Bila baris terakhir berhasil dilalui dan ratu berhasil ditempatkan, itu sudah cukup. Jadi tidak perlu mengatur fungsi penandaan baris.

Saat ini kita bisa mulai dari baris pertama dan melintasi kolom. Tentukan apakah kolom tersebut salah, apakah diagonal utama salah, dan apakah diagonal sekunder salah. Jika ya, lanjutkan ke kolom berikutnya. Jika tidak, atur posisinya ke Q, lalu lakukan pencarian yang sama untuk baris berikutnya. Metode mundur, ingatlah untuk mengembalikan posisi dan fungsi penandaan setelah pencarian.

Ini diagonal dan subdiagonal. Dapat digambarkan pada koordinatnya, yang satu adalah y=x+b, yang lainnya adalah y=-x+b.

Jadi b=yx, untuk membuat b&gt;0, maka kita tambahkan n. Yang lainnya adalah y+x.

  1. class Solution {
  2. public:
  3.     vector<vector<string>> solveNQueens(int n) {
  4.         vector<vector<string>> ans;
  5.         if(n==0)
  6.             return {};
  7.         vector<string> board(n,string(n,'.'));
  8.         vector<bool> c(n,false),l(2*n-1,false),r(2*n-1,false);
  9.         back(n,ans,board,c,l,r,0);
  10.         return ans;
  11.     }
  12.     void back(int n,vector<vector<string>>& ans,vector<string>& board,vector<bool>& c,
  13.     vector<bool>& l,vector<bool>& r,int row){
  14.         if(row==n){
  15.             ans.push_back(board);
  16.             return ;
  17.         }
  18.         int i;
  19.         for(i=0;i<n;i++){
  20.             if(c[i]||l[row-i+n]||r[row+i]){
  21.                 continue;
  22.             }
  23.             board[row][i]='Q';
  24.             c[i]=l[row-i+n]=r[row+i]=true;
  25.             back(n,ans,board,c,l,r,row+1);
  26.             board[row][i]='.';
  27.             c[i]=l[row-i+n]=r[row+i]=false;
  28.         }
  29.     }
  30. };

Meringkaskan

Untuk metode backtracking, cari dulu syarat batas dan syarat akhir. Umumnya, set i sama dengan jumlah baris.

Syarat batas umumnya tidak melewati batas.

Umumnya, fungsi penandaan perlu diatur. Kemudian akses baris demi baris atau posisi demi posisi, dan fungsi tag yang dikunjungi disetel ke true. Kemudian lanjutkan ke baris berikutnya atau selanjutnya (biasanya secara rekursif). Kemudian kembalikan fungsi penandaan dan papan di atas setelah selesai (biasanya akan ditetapkan satu sebagai jawabannya). Jika cocok, push_back ke array ans.

Profil pribadi

Ia telah mengabdikan dirinya untuk meneliti teknologi selama lebih dari 30 tahun, dan mahir dalam berbagai bahasa seperti java, linux, javascript, php, css, dll. Ia telah memberikan banyak kontribusi di bidang open source stasiun dokumentasi pengembang untuk berbagi beberapa masalah dalam pengembangan teknologi untuk referensi di masa mendatang. Semua orang memeriksanya

informasi kontak saya

Surat