Partage de technologie

Méthode Likou-backtracking

2024-07-12

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

Qu’est-ce que le retour en arrière ?

Lors de la recherche d'un certain nœud, si nous constatons que le nœud actuel (et ses sous-nœuds) n'est pas la cible requise, nous revenons au nœud d'origine pour continuer la recherche et restaurer l'état modifié du nœud actuel.
N'oubliez pas deux petits conseils :La première consiste à transmettre le statut par référence (&) et la seconde consiste à modifier toutes les modifications de statut une fois la récursivité terminée.
Il existe généralement deux situations pour revenir en arrière sur les modifications. L'une consiste à modifier la dernière sortie, telle que la permutation et la combinaison ; l'autre consiste à modifier la cible d'accès.
N'oubliez pas, par exemple, de rechercher une chaîne dans une matrice.

46.Arrangement complet

sujet

Étant donné un tableau sans numéros en doublenums, retourne sontoutes les permutations possibles .tu peuxdans n'importe quel ordreRenvoyez la réponse.

Exemple 1:

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

Exemple 2 :

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

Exemple 3 :

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

indice:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • numstous les entiers dansdifférents l'un de l'autre​​​​​​​
répondre
Pour afficher toutes les combinaisons triées du tableau, nous pouvons utiliser la méthode de retour en arrière.
Déterminez d’abord une position, puis échangez-la avec chaque position suivante. Après avoir changé, passez à l'emplacement suivant. Ensuite, une fois cette série d’étapes terminée, vous devez remplacer ceux remplacés. C’est la méthode du retour en arrière.
  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. Combinaison

77. Combinaison

sujet

Étant donné deux entiersnetk, plage de retour[1, n]tout est possible danskcombinaison de chiffres.

tu peux appuyeraucun ordreRenvoyez la réponse.

Exemple 1:

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

Exemple 2 :

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

indice:

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

题解

Définissez un nombre et calculez le nombre de chacun. Lorsque count==k, placez-le dans le tableau. Ceci est différent des précédents, qui étaient des permutations et des combinaisons. C'est un peu comme sélectionner un tableau.

À partir de 1-n, configurez un tableau supplémentaire pour stocker les résultats de chaque fois. Le nombre change dynamiquement. Après avoir attribué i, le nombre augmente de un et un nombre est sélectionné parmi (i+1, n) dans dfs. Comptez-- après retraçage.

  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. Recherche d'unité

79. Recherche de mots

sujet

Donné unm x nGrille de personnages 2Dboardet un mot chaîneword .siwordexiste dans la grille, renvoietrue; Sinon, retournezfalse 。

Les mots doivent être formés à partir de lettres situées dans des cellules adjacentes par ordre alphabétique, les cellules « adjacentes » étant celles qui sont adjacentes horizontalement ou verticalement. Les lettres d’une même cellule ne peuvent pas être utilisées à plusieurs reprises.

Exemple 1:

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

Exemple 2 :

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

Exemple 3 :

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

indice:

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • boardetwordComposé uniquement de lettres anglaises majuscules et minuscules

répondre

Routine similaire.

La méthode dfs + backtracking définit d'abord une visite pour marquer si l'emplacement a été marqué lors de chaque recherche afin d'éviter que le même emplacement ne soit visité plusieurs fois.

Pour un emplacement, un jugement de limite doit être effectué pour déterminer s'il traverse la frontière. Déterminez ensuite s'il a été visité, s'il a été trouvé avec succès et si la lettre à la position est différente de la lettre cible.

dfs, cherchez autour.

  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 Reine

51. Reine N

sujet

Selon les règles des échecs, une reine peut attaquer une pièce sur la même ligne ou colonne ou sur la même diagonale.

n Problème de reineCe qui est étudié, c'est commentnreine placée dansn×nsur l'échiquier et empêcher les reines de s'attaquer les unes les autres.

Donne-toi un entiern, renvoie tous différentsn problème de reinela solution.

Chaque solution contient un différentn Problème de reineLe plan de placement des pièces d'échecs, dans ce plan'Q'et'.'Ils représentent respectivement la reine et le siège vide.

Exemple 1:

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

Exemple 2 :

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

indice:

  • 1 <= n <= 9

题意

N Queen nécessite trois fonctions d'étiquetage, l'une est la colonne, l'autre est la diagonale principale et l'autre est la diagonale secondaire.

Parce qu'il y aura certainement une reine placée dans chaque ligne, elle est parcourue ligne par ligne. Lorsque la dernière ligne est parcourue avec succès et que la reine est placée avec succès, cela suffit. Il n’est donc pas nécessaire de définir la fonction de marquage des lignes.

À ce stade, nous pouvons commencer par la première ligne et parcourir les colonnes. Déterminez si la colonne est fausse, si la diagonale principale est fausse et si la diagonale secondaire est fausse. Si tel est le cas, passez à la colonne suivante. Sinon, définissez la position sur Q, puis effectuez la même recherche pour la ligne suivante. Méthode de retour en arrière, pensez à restaurer les fonctions de position et de marquage après la recherche.

Cette diagonale et sous-diagonale. Il peut être dessiné sur les coordonnées, l'une est y=x+b, l'autre est y=-x+b.

Donc b=yx, pour faire b&gt;0, donc on ajoute n. L'autre est 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. };

Résumer

Pour la méthode de retour en arrière, recherchez d’abord les conditions aux limites et les conditions finales. Généralement, le i défini est égal au nombre de lignes.

La condition aux limites est généralement de ne pas franchir la frontière.

Généralement, une fonction de marquage doit être définie. Accédez ensuite ligne par ligne ou position par position, et la fonction de balise visitée est définie sur true. Passez ensuite à la ligne suivante ou suivante (généralement de manière récursive). Ensuite, restaurez la fonction de marquage ci-dessus et le tableau après avoir terminé (généralement, une sera définie comme réponse). Si cela correspond, push_back vers le tableau ans.

Profil personnel

Il se consacre à la recherche technologique depuis plus de 30 ans et maîtrise divers langages tels que java, linux, javascript, php, css, etc. Il a apporté de nombreuses contributions dans le domaine de l'open source. station de documentation pour les développeurs pour partager certains problèmes de développement technologique pour référence future.

mes coordonnées

Mail