Teknologian jakaminen

Likou-backtracking menetelmä

2024-07-12

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

Mitä on perääntyminen?

Kun etsit tiettyä solmua, jos havaitsemme, että nykyinen solmu (ja sen alisolmut) ei ole vaadittu kohde, palaamme alkuperäiseen solmuun jatkamaan hakua ja palauttamaan nykyisen solmun muokatun tilan.
Muista kaksi pientä vinkkiä:Ensimmäinen on välittää tila viitteellä (&), ja toinen on muuttaa kaikkia tilamuutoksia, kun rekursio on valmis.
Muokkauksille on yleensä kaksi tapaa, joista toinen on muuttaa tulosteen viimeistä bittiä, kuten permutaatio ja yhdistelmä.
Muista esimerkiksi merkkijonon etsiminen matriisista.

46. ​​Täysi järjestely

aihe

Annettu taulukko ilman päällekkäisiä numeroitanums, palauta sekaikki mahdolliset permutaatiot .sinä pystytmissä tahansa järjestyksessäPalauta vastaus.

Esimerkki 1:

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

Esimerkki 2:

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

Esimerkki 3:

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

vihje:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • numskaikki kokonaisluvut sisääneroavat toisistaan​​​​​​​
vastaus
Kaikkien taulukon lajiteltujen yhdistelmien tulostamiseksi voimme käyttää backtracking-menetelmää.
Määritä ensin sijainti ja vaihda se sitten jokaisen seuraavan sijainnin kanssa. Vaihdon jälkeen siirry seuraavaan paikkaan. Kun tämä vaihesarja on suoritettu, sinun on vaihdettava korvatut. Se on paluumenetelmä.
  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. Yhdistelmä

77. Yhdistelmä

aihe

Annettu kaksi kokonaislukuanjak, paluualue[1, n]kaikki mahdollinen sisäänknumeroiden yhdistelmä.

voit painaamikä tahansa tilausPalauta vastaus.

Esimerkki 1:

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

Esimerkki 2:

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

vihje:

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

题解

Aseta luku ja laske kunkin numero Kun count==k, laita se taulukkoon. Tämä eroaa aiemmista, jotka olivat permutaatioita ja yhdistelmiä. Tämä on vähän kuin taulukon valitseminen.

Alkaen 1-n, määritä ylimääräinen matriisi tallentaaksesi kunkin ajan tulokset. Luku muuttuu dynaamisesti i:n määrittämisen jälkeen, ja luku valitaan dfs:stä (i+1, n). Laske - taaksepäin jäljityksen jälkeen.

  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. Yksikköhaku

79. Sanahaku

aihe

annettu am x n2D merkkiruudukkoboardja merkkijono sanaword .joswordon olemassa ruudukossa, palaatrue; muussa tapauksessa palautafalse 。

Sanat on muodostettava vierekkäisten solujen kirjaimista aakkosjärjestyksessä, jossa "vierekkäiset" ovat ne, jotka ovat vierekkäin vaaka- tai pystysuunnassa. Saman solun kirjaimia ei saa käyttää toistuvasti.

Esimerkki 1:

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

Esimerkki 2:

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

Esimerkki 3:

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

vihje:

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • boardjawordKoostuu vain isoista ja pienistä englanninkielisistä kirjaimista

vastaus

Samanlainen rutiini.

Dfs+backtracking-menetelmä määrittelee ensin käynnin, jolla merkitään, onko sijainti merkitty jokaisen haun aikana, jotta samassa paikassa ei käyty useita kertoja.

Sijainnin osalta on tehtävä rajapäätös sen määrittämiseksi, ylittääkö se rajan. Määritä sitten, onko siinä vieraillut, onko se onnistuneesti löydetty ja onko tässä paikassa oleva kirjain erilainen kuin kohdekirjain.

dfs, etsi ympäriltäsi.

  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 kuningatar

51. Kuningatar N

aihe

Shakin sääntöjen mukaan kuningatar voi hyökätä nappulaa samalla rivillä tai sarakkeella tai samalla diagonaalilla.

n Queen-ongelmaTutkitaan, mitennkuningatar sijoitettun×nshakkilaudalla, jolloin kuningattaret eivät pysty hyökkäämään toisiaan vastaan.

Anna kokonaislukun, palauttaa kaikki erilaisian kuningatar ongelmas ratkaisu.

Jokainen ratkaisu sisältää erilaisenn Queen-ongelmaShakkinappuloiden sijoitussuunnitelma tässä suunnitelmassa'Q'ja'.'Ne edustavat kuningatarta ja vastaavasti tyhjää istuinta.

Esimerkki 1:

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

Esimerkki 2:

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

vihje:

  • 1 <= n <= 9

题意

N Queen vaatii kolme merkintätoimintoa, joista yksi on sarake, toinen on päälävistäjä ja toinen on toissijainen diagonaali.

Koska jokaisella rivillä on varmasti kuningatar, se kulkee rivi riviltä Kun viimeinen rivi on onnistuneesti ajettu ja kuningatar on sijoitettu onnistuneesti. Rivimerkintätoimintoa ei siis tarvitse asettaa.

Tällä hetkellä voimme aloittaa ensimmäiseltä riviltä ja kulkea sarakkeittain. Selvitä, onko sarake epätosi, onko päälävistäjä epätosi ja onko toissijainen diagonaali epätosi. Jos näin on, siirry seuraavaan sarakkeeseen. Jos ei, aseta asemaksi Q ja suorita sama haku seuraavalle riville. Backtracking menetelmä, muista palauttaa sijainti ja merkintätoiminnot haun jälkeen.

Tämä lävistäjä ja subdiagonaali. Se voidaan piirtää koordinaatteihin, joista toinen on y=x+b, toinen on y=-x+b.

Joten b=yx, jotta saadaan b&gt;0, joten lisäämme n. Toinen on 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. };

Tee yhteenveto

Selvitä paluumenetelmää varten ensin reunaehdot ja loppuehdot. Yleensä i-joukko on yhtä suuri kuin rivien lukumäärä.

Rajaehtona on yleensä olla ylittämättä rajaa.

Yleensä merkintätoiminto on asetettava. Siirry sitten rivi riviltä tai sijainti sijainnilta, ja vierailtu tunnistetoiminto asetetaan arvoon tosi. Jatka sitten seuraavalle tai seuraavalle riville (yleensä rekursiivisesti). Palauta sitten yllä oleva merkintätoiminto ja taulu viimeistelyn jälkeen (yleensä yksi asetetaan vastaukseksi). Jos se vastaa, push_back ans-taulukkoon.

Henkilökohtainen profiili

Hän on omistautunut teknologian tutkimukselle yli 30 vuoden ajan ja hallitsee useita kieliä, kuten java, linux, javascript, php, css jne. Hän on tehnyt paljon työtä avoimen lähdekoodin alalla Kehittäjän dokumentaatioasema, jossa voit jakaa joitakin teknologian kehittämisen ongelmia myöhempää käyttöä varten

yhteystietoni

Mail