Compartir tecnología

Método de retroceso de Likou

2024-07-12

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

¿Qué es retroceder?

Al buscar un determinado nodo, si encontramos que el nodo actual (y sus subnodos) no es el objetivo requerido, volvemos al nodo original para continuar la búsqueda y restaurar el estado modificado del nodo actual.
Recuerda dos pequeños consejos:La primera es pasar el estado por referencia (&) y la segunda es cambiar todas las modificaciones de estado una vez completada la recursividad.
Generalmente hay dos situaciones para las modificaciones de retroceso: una es modificar el último bit de salida, como la permutación y combinación, la otra es modificar el objetivo de acceso.
Recuerde, por ejemplo, buscar una cadena en una matriz.

46.Arreglo completo

tema

Dada una matriz sin números duplicadosnums, devolver sutodas las permutaciones posibles .puedeen cualquier ordenDevolver respuesta.

Ejemplo 1:

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

Ejemplo 2:

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

Ejemplo 3:

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

pista:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • numstodos los números enteros endiferentes uno del otro​​​​​​​
respuesta
Para generar todas las combinaciones ordenadas de la matriz, podemos utilizar el método de retroceso.
Primero determine una posición y luego cámbiela con cada posición posterior. Después de cambiar, vaya a la siguiente ubicación. Luego, una vez completada esta serie de pasos, deberá reemplazar los reemplazados. Ese es el método de retroceso.
  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. combinación

77. combinación

tema

Dados dos números enterosnyk, rango de retorno[1, n]todo lo posible enkcombinación de números.

puedes presionarcualquier ordenDevolver respuesta.

Ejemplo 1:

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

Ejemplo 2:

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

pista:

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

题解

Establezca un recuento y calcule el número de cada uno. Cuando count==k, colóquelo en la matriz. Este es diferente a los anteriores, que eran permutaciones y combinaciones. Esto es un poco como seleccionar una matriz.

A partir de 1-n, configure una matriz adicional para almacenar los resultados de cada vez. El recuento cambia dinámicamente después de asignar i, el recuento aumenta en uno y se selecciona un número de (i+1, n) en dfs. Contar... después de retroceder.

  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. Búsqueda de unidades

79. Búsqueda de palabras

tema

dado unm x nCuadrícula de personajes 2Dboardy una palabra de cadenaword .siwordexiste en la grilla, regresatrue; De lo contrario, regresefalse 。

Las palabras deben formarse a partir de letras en celdas adyacentes en orden alfabético, donde las celdas "adyacentes" son aquellas que están adyacentes horizontal o verticalmente. No se permite el uso repetido de letras en la misma celda.

Ejemplo 1:

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

Ejemplo 2:

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

Ejemplo 3:

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

pista:

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • boardywordCompuesto únicamente por letras inglesas mayúsculas y minúsculas.

respuesta

Rutina similar.

El método dfs+backtracking primero define una visita para marcar si la ubicación se ha marcado durante cada búsqueda para evitar que la misma ubicación sea visitada varias veces.

Para una ubicación, se debe realizar un juicio de límites para determinar si cruza el límite. Luego determine si ha sido visitado, si se ha encontrado con éxito y si la letra en esta posición es diferente de la letra de destino.

dfs, busca alrededor.

  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 Reina

51. Reina N.

tema

Según las reglas del ajedrez, una reina puede atacar una pieza de la misma fila o columna o de la misma diagonal.

n problema de la reinaLo que se estudia es cómonreina colocada enn×nen el tablero de ajedrez y hacer que las reinas no puedan atacarse entre sí.

darte un numero enteron, devuelve todo diferentenorte problema de la reinas solución.

Cada solución contiene un diferenten problema de la reinaEl plan de colocación de piezas de ajedrez, en este plan.'Q'y'.'Representan a la reina y el asiento vacío respectivamente.

Ejemplo 1:

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

Ejemplo 2:

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

pista:

  • 1 <= n <= 9

题意

N Queen requiere tres funciones de etiquetado, una es la columna, una es la diagonal principal y la otra es la diagonal secundaria.

Debido a que definitivamente habrá una reina colocada en cada fila, se recorre fila por fila. Cuando la última fila se atraviesa con éxito y la reina se coloca con éxito, es suficiente. Por lo tanto, no es necesario configurar la función de marcado de filas.

En este momento podemos comenzar desde la primera fila y recorrer por columnas. Determine si la columna es falsa, si la diagonal principal es falsa y si la diagonal secundaria es falsa. Si es así, vaya a la siguiente columna. Si no, establezca la posición en Q y luego realice la misma búsqueda para la siguiente fila. Método de retroceso, recuerde restaurar la posición y las funciones de marcado después de la búsqueda.

Esta diagonal y subdiagonal. Se puede dibujar en las coordenadas, una es y=x+b, la otra es y=-x+b.

Entonces b=yx, para hacer b&gt;0, entonces sumamos n. El otro es 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. };

Resumir

Para el método de retroceso, primero encuentre las condiciones de contorno y las condiciones finales. Generalmente, el conjunto i es igual al número de filas.

La condición de contorno generalmente es no cruzar el límite.

Generalmente, es necesario configurar una función de marcado. Luego acceda línea por línea o posición por posición, y la función de etiqueta visitada se establece en verdadero. Luego continúe con la siguiente o la siguiente línea (generalmente de forma recursiva). Luego restaure la función de marcado anterior y el tablero después de terminar (generalmente se establecerá uno como respuesta). Si coincide, retroceda a la matriz ans.

Perfil personal

Se ha dedicado a la investigación de tecnología durante más de 30 años y domina varios lenguajes como java, linux, javascript, php, css, etc. Ha realizado muchas contribuciones en el campo del código abierto. Estación de documentación para desarrolladores para compartir algunos problemas en el desarrollo de tecnología para referencia futura.

Mi información de contacto

Correo