Обмен технологиями

Метод Ликоу с возвратом

2024-07-12

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

Что такое возврат назад?

Если при поиске определенного узла мы обнаруживаем, что текущий узел (и его подузлы) не является требуемой целью, мы возвращаемся к исходному узлу, чтобы продолжить поиск и восстановить измененное состояние текущего узла.
Запомните два маленьких совета:Первый — передать статус по ссылке (&), а второй — изменить все изменения статуса после завершения рекурсии.
Обычно существует две ситуации для возврата изменений: одна — изменить последний бит вывода, например перестановка и комбинация, другая — изменить цель доступа;
Помните, например, поиск строки в матрице.

46.Полная договоренность

тема

Дан массив без повторяющихся чисел.nums, вернуть еговсе возможные перестановки .ты можешьв любом порядкеОбратный ответ.

Пример 1:

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

Пример 2:

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

Пример 3:

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

намекать:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • numsвсе целые числа вотличаются друг от друга​​​​​​​
отвечать
Чтобы вывести все отсортированные комбинации массива, мы можем использовать метод обратного отслеживания.
Сначала определите позицию, а затем меняйте ее с каждой последующей позицией. После смены перейдите в следующую локацию. Затем после выполнения данного ряда действий необходимо заменить замененные. Это метод возврата.
  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. Комбинация

77. Комбинация

тема

Даны два целых числаnиk, диапазон возврата[1, n]все возможно вkкомбинация цифр.

ты можешь нажатьЛюбой заказОбратный ответ.

Пример 1:

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

Пример 2:

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

намекать:

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

题解

Установите счетчик и вычислите количество каждого из них. Когда count == k, поместите его в массив. Это отличается от предыдущих, которые представляли собой перестановки и комбинации. Это немного похоже на выбор массива.

Начиная с 1-n, создайте дополнительный массив для хранения результатов каждого раза. Count изменяется динамически. После присвоения i счетчик увеличивается на единицу, и число выбирается из (i+1, n) в dfs. Посчитайте - после обратного отслеживания.

  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. Поиск юнитов

79. Поиск слов

тема

учитываяm x n2D сетка символовboardи строковое словоword .еслиwordсуществует в сетке, возвращаетtrue; В противном случае возвратfalse 。

Слова должны быть составлены из букв, стоящих в соседних ячейках в алфавитном порядке, причем «соседними» ячейками считаются те, которые расположены рядом по горизонтали или по вертикали. Буквы в одной ячейке не могут использоваться повторно.

Пример 1:

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

Пример 2:

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

Пример 3:

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

намекать:

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • boardиwordСостоит только из прописных и строчных английских букв.

отвечать

Аналогичная рутина.

Метод dfs+backtracking сначала определяет посещение, чтобы отметить, было ли местоположение отмечено во время каждого поиска, чтобы предотвратить многократное посещение одного и того же местоположения.

Для местоположения необходимо принять решение о границах, чтобы определить, пересекает ли оно границу. Затем определите, была ли она посещена, успешно ли она найдена и отличается ли буква в этой позиции от целевой буквы.

dfs, поищи вокруг.

  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. Королева

51. Королева Н

тема

По правилам шахмат ферзь может атаковать фигуру, находящуюся в той же строке, столбце или на той же диагонали.

проблема с королевойИзучается то, какnкоролева помещена вn×nна шахматной доске и лишить ферзей возможности атаковать друг друга.

Дайте вам целое числоn, возвращает все разныен проблема с королевойрешение.

Каждое решение содержит разныепроблема с королевойПлан расстановки шахматных фигур, на этом плане'Q'и'.'Они представляют королеву и пустое место соответственно.

Пример 1:

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

Пример 2:

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

намекать:

  • 1 <= n <= 9

题意

N Queen требует трех функций маркировки: одна — столбец, одна — главная диагональ, а другая — второстепенная диагональ.

Поскольку в каждом ряду обязательно будет помещен ферзь, он проходится ряд за рядом. Когда последний ряд успешно пройден и ферзь успешно установлен, этого достаточно. Поэтому нет необходимости устанавливать функцию маркировки строк.

На данный момент мы можем начать с первой строки и перемещаться по столбцам. Определите, является ли столбец ложным, ложной ли главная диагональ и ложной ли второстепенная диагональ. Если да, перейдите к следующему столбцу. Если нет, установите позицию Q, а затем выполните тот же поиск для следующей строки. Метод обратного отслеживания: не забудьте восстановить положение и функции маркировки после поиска.

Это диагональ и субдиагональ. Его можно нарисовать по координатам: одна y=x+b, другая y=-x+b.

Итак, b=yx, чтобы сделать b&gt;0, поэтому мы добавляем n. Другой — у+х.

  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. };

Подведем итог

Для метода обратного отслеживания сначала найдите граничные и конечные условия. Обычно набор i равен количеству строк.

Граничное условие обычно заключается в том, чтобы не пересекать границу.

Как правило, необходимо установить функцию маркировки. Затем осуществляется доступ построчно или по позиции, и для функции посещенного тега устанавливается значение true. Затем перейдите к следующей или следующей строке (обычно рекурсивно). Затем после завершения восстановите вышеуказанную функцию маркировки и доску (обычно одна из них устанавливается в качестве ответа). Если оно соответствует, push_back в массив ans.

Личный профиль

Он посвятил себя исследованию технологий более 30 лет и владеет различными языками, такими как Java, Linux, Javascript, php, css и т. д. Он внес большой вклад в область открытого исходного кода. Станция документации для разработчиков, где можно поделиться некоторыми проблемами в разработке технологий для дальнейшего использования. Все ознакомьтесь.

моя контактная информация

Почта