Compartilhamento de tecnologia

Método de retrocesso Likou

2024-07-12

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

O que é retrocesso?

Ao pesquisar um determinado nó, se descobrirmos que o nó atual (e seus subnós) não é o alvo necessário, voltamos ao nó original para continuar a pesquisa e restaurar o estado modificado do nó atual.
Lembre-se de duas pequenas dicas:A primeira é passar o status por referência (&) e a segunda é alterar todas as modificações de status após a conclusão da recursão.
Geralmente há duas situações para retroceder modificações. Uma é modificar a última saída, como permutação e combinação; a outra é modificar o alvo de acesso.
Lembre-se, por exemplo, de procurar uma string em uma matriz.

46. ​​Arranjo completo

tema

Dado um array sem números duplicadosnums, devolva seutodas as permutações possíveis .você podeem qualquer ordemResposta de retorno.

Exemplo 1:

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

Exemplo 2:

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

Exemplo 3:

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

dica:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • numstodos os inteiros emdiferentes um do outro​​​​​​​
responder
Para gerar todas as combinações classificadas do array, podemos usar o método de retrocesso.
Primeiro determine uma posição e depois troque-a com cada posição subsequente. Após a mudança, vá para o próximo local. Então, após a conclusão desta série de etapas, você precisará substituir os substituídos. Esse é o método de retrocesso.
  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. Combinação

77. Combinação

tema

Dados dois inteirosnek, intervalo de retorno[1, n]tudo possível emkcombinação de números.

você pode pressionarqualquer ordemResposta de retorno.

Exemplo 1:

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

Exemplo 2:

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

dica:

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

题解

Defina uma contagem e calcule o número de cada um. Quando count==k, coloque-o no array. Isto é diferente dos anteriores, que eram permutações e combinações. Isso é um pouco como selecionar um array.

A partir de 1-n, configure um array adicional para armazenar os resultados de cada vez. A contagem muda dinamicamente após atribuir i, a contagem aumenta em um e um número é selecionado de (i+1, n) em dfs. Contar-- após 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. Pesquisa de unidade

79. Pesquisa de palavras

tema

dado umm x nGrade de caracteres 2Dboarde uma palavra de stringword .sewordexiste na grade, retornatrue; Caso contrário, retornefalse 。

As palavras devem ser formadas a partir de letras em células adjacentes em ordem alfabética, onde células “adjacentes” são aquelas adjacentes horizontalmente ou verticalmente. Não é permitido usar letras na mesma célula repetidamente.

Exemplo 1:

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

Exemplo 2:

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

Exemplo 3:

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

dica:

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • boardewordComposto apenas por letras inglesas maiúsculas e minúsculas

responder

Rotina semelhante.

O método dfs + backtracking primeiro define uma visita para marcar se o local foi marcado durante cada pesquisa para evitar que o mesmo local seja visitado várias vezes.

Para um local, é necessário fazer um julgamento de limite para determinar se ele cruza o limite. Em seguida, determine se foi visitado, se foi encontrado com sucesso e se a letra na posição é diferente da letra alvo.

dfs, pesquise por aí.

  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úcleo de Educação Infantil

51. Rainha N

tema

De acordo com as regras do xadrez, uma rainha pode atacar uma peça na mesma linha ou coluna ou na mesma diagonal.

n Problema da rainhaO que se estuda é comonrainha colocada emn×nno tabuleiro de xadrez e torna as rainhas incapazes de atacar umas às outras.

Dê a você um número inteiron, retorna todos diferentese problema da rainhaé solução.

Cada solução contém um diferenten Problema da rainhaO plano de colocação das peças de xadrez, neste plano'Q'e'.'Eles representam a rainha e o assento vazio, respectivamente.

Exemplo 1:

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

Exemplo 2:

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

dica:

  • 1 <= n <= 9

题意

N Queen requer três funções de rotulagem, uma é a coluna, uma é a diagonal principal e a outra é a diagonal secundária.

Como definitivamente haverá uma rainha colocada em cada linha, ela será percorrida linha por linha. Quando a última linha for percorrida com sucesso e a rainha for colocada com sucesso, é o suficiente. Portanto, não há necessidade de definir a função de marcação de linha.

Neste momento podemos começar na primeira linha e percorrer as colunas. Determine se a coluna é falsa, se a diagonal principal é falsa e se a diagonal secundária é falsa. Se sim, vá para a próxima coluna. Caso contrário, defina a posição como Q e execute a mesma pesquisa para a próxima linha. Método de retrocesso, lembre-se de restaurar a posição e as funções de marcação após a pesquisa.

Esta diagonal e subdiagonal. Pode ser desenhado nas coordenadas, uma é y=x+b, a outra é y=-x+b.

Então b=yx, para fazer b&gt;0, então adicionamos n. O outro é 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 o método de retrocesso, primeiro encontre as condições de contorno e as condições finais. Geralmente, o conjunto i é igual ao número de linhas.

A condição de contorno geralmente é não cruzar o limite.

Geralmente, uma função de marcação precisa ser definida. Em seguida, acesse linha por linha ou posição por posição e a função da tag visitada será definida como verdadeira. Em seguida, continue para a próxima ou próxima linha (geralmente de forma recursiva). Em seguida, restaure a função de marcação acima e a placa após terminar (geralmente uma será definida como resposta). Se corresponder, push_back para o array ans.

Perfil pessoal

Ele se dedica à pesquisa de tecnologia há mais de 30 anos e é proficiente em diversas linguagens como java, linux, javascript, php, css, etc. estação de documentação do desenvolvedor para compartilhar alguns problemas no desenvolvimento de tecnologia para referência futura.

minhas informações de contato

Correspondência