В компьютерных задачах большое количество задач требует использования рекурсивных алгоритмов.В прошлом блоге мы представили проблему рекурсии в бинарных деревьях. Теперь давайте посмотрим на очень классическую идею поиска с возвратом в рекурсивных алгоритмах. Такие идеи алгоритмов обычно применяются к классу задач. Такая проблема называется проблемой дерева. Сама проблема такого рода не определяется в двоичном дереве. , но мы Когда вы подробно проанализируете эту проблему, вы обнаружите, что идея решения этой проблемы по существу имеет форму дерева.
проблема дерева
Теперь давайте посмотрим на очень классическую идею поиска с возвратом в рекурсивных алгоритмах. Такие идеи алгоритмов обычно применяются к классу задач. Такая проблема называется проблемой дерева. Сама проблема такого рода не определяется в двоичном дереве. , но мы Когда вы подробно проанализируете эту проблему, вы обнаружите, что идея решения этой проблемы по существу имеет форму дерева.
leetcode 17. Буквенные комбинации телефонных номеров
Идеи решения проблем
Например, когда мы вводим digits="23", 2 может представлять три буквы abc, когда 2 представляет a, 3 представляет def, и таким же образом мы можем нарисовать дерево.
Рекурсивный процесс:
цифры это строка цифр
s(цифры) — это строка букв, которую могут представлять цифры.
s(цифры[0…n-1]) = буква(цифры[0]) + s(цифры[1…n-1]) = буква(цифры[0]) + буква(цифры[1]) + s( цифры[2...n-1]) = ...
Код
class Solution {
private:
const string letterMap[10] = {
" ", //0
"", //1
"abc", //2
"def", //3
"ghi", //4
"jkl", //5
"mno", //6
"pqrs", //7
"tuv", //8
"wxyz" //9
};
vector<string> res;
//index表示从该数字开始在字串，存于s中
// s中保存了此时从digits[0...index-1]翻译得到的一个字母字符串
// 寻找和digits[index]匹配的字母, 获得digits[0...index]翻译得到的解
void findCombination(const string &digits, int index, const string &s){
if (index == digits.size()){
res.push_back(s);
return;
}
//获得数字
char c = digits[index];
//对应的字母串
string letters = letterMap[c - '0'];
for (int i = 0; i < letters.size(); i++){
findCombination(digits, index + 1, s + letters[i]);
}
return ;
}
public:
vector<string> letterCombinations(string digits) {
res.clear();
if (digits.size() == 0){
return res;
}
findCombination(digits, 0, "");
return res;
}
};
что такое откат
Важная особенность рекурсивных вызовов — возврат. Поиск с возвратом является основной реализацией решений грубой силы.
мыслительные вопросы
- leetcode 93
- leetcode 131
Перестановки
leetcode 46. Полная перестановка
Идеи решения проблем
Важным классом задач, с которыми может справиться алгоритм поиска с возвратом, является проблема перестановки.Если мы хотим упорядочить 1, 2, 3, мы можем сначала извлечь элемент.Например, если мы извлекаем 1 сейчас, то следующее нам нужно сделать, это использовать 2, 3 Два элемента построить договоренность. Нам нужно извлечь еще один элемент.Если мы извлечем 2, останется только элемент 3. По этому пути мы получим перестановку 123. Если мы выберем 3 с 23, то останется 2 и мы получим перестановку 132. Соответственно, мы рассматриваем выбор 2 или 3 в начале.
Это тоже проблема дерева.
Perms(nums[0…n-1]) = {возьмем число} + Perms(nums[{0…n-1} - это число])
Код
class Solution {
private:
vector<vector<int>> res;
vector<bool> visitor;
//产生一个解
//p[0, index-1]已经是一个组合了
//要生成index大小的组合
// p中保存了一个有index-1个元素的排列。
// 向这个排列的末尾添加第index个元素, 获得一个有index个元素的排列
void generatePermute(const vector<int>& nums, int index, vector<int>& p){
if (index == nums.size()){
res.push_back(p);
return;
}
for (int i = 0; i < nums.size(); i++){
if (!visitor[i]){
p.push_back(nums[i]);
visitor[i] = true;
generatePermute(nums, index + 1, p);
//回溯
p.pop_back();
visitor[i] = false;
}
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
res.clear();
if (nums.size() == 0){
return res;
}
visitor = vector<bool>(nums.size(), false);
vector<int> p;
generatePermute(nums, 0, p);
return res;
}
};
аналогичная проблема
- leetcode 47
Комбинированные проблемы
Возврат означает возврат назад.Рекурсивная функция автоматически гарантирует возврат назад, но другие переменные, которые мы устанавливаем, также должны вернуться в исходное положение, если это необходимо.
буквенный код 77. Комбинация
Идеи решения проблем
Мы берем ваши два числа из 1, 2, 3 и 4. Если мы возьмем 1 на первом шаге, затем возьмем число в 2, 3, 4, мы можем получить комбинацию 12, 13, 14. Если первый шаг занимает 2, то второй шаг занимает число от 3 до 4, и может быть получена комбинация 23 и 24. Если мы возьмем 3 на первом шаге, то на втором мы сможем взять только 4, в результате чего получится комбинация из 34.
Код
class Solution {
private:
vector<vector<int>> res;
//前start-1个组合已经完成
// 求解C(n,k), 当前已经找到的组合存储在c中, 需要从start开始搜索新的元素
void generateCombinations(int n, int k, int start, vector<int> &c){
if (c.size() == k){
res.push_back(c);
return;
}
for (int i = start; i <= n; i++){
c.push_back(i);
generateCombinations(n, k , i+1, c);
//回溯
c.pop_back();
}
return;
}
public:
vector<vector<int>> combine(int n, int k) {
res.clear();
if (n <= 0 || k <= 0){
return res;
}
vector<int> c;
generateCombinations(n, k, 1, c);
return res;
}
};
Оптимизация поиска с возвратом для решения комбинаторных задач
Это модель, которую мы построили для рекурсивного дерева этого вопроса.В этой модели есть место, куда нам явно не нужно идти, то есть на последнем месте нам не нужно пытаться взять 4 вообще, потому что мы берем 4. После этого нельзя брать никакое число. В нашем выше алгоритме мы все еще пытались взять 4. После взятия 4, когда мы взяли второе число, мы обнаружили, что ничего не можем взять, поэтому нам пришлось вернуться снова.Для этой части мы можем полностью сократить его выключенный. Другими словами, мы пытаемся взять только 1,2,3.
обратная обрезка
#include <iostream>
#include <vector>
using namespace std;
class Solution {
private:
vector<vector<int>> res;
// 求解C(n,k), 当前已经找到的组合存储在c中, 需要从start开始搜索新的元素
void generateCombinations(int n, int k, int start, vector<int> &c){
if( c.size() == k ){
res.push_back(c);
return;
}
// 还有k - c.size()个空位, 所以,[i...n]中至少要有k-c.size()个元素
// i最多为 n - (k-c.size()) + 1
for( int i = start ; i <= n - (k-c.size()) + 1 ; i ++ ){
c.push_back( i );
generateCombinations(n, k, i + 1 , c );
c.pop_back();
}
return;
}
public:
vector<vector<int>> combine(int n, int k) {
res.clear();
if( n <= 0 || k <= 0 || k > n )
return res;
vector<int> c;
generateCombinations(n, k, 1, c);
return res;
}
};
аналогичная проблема
- leetcode 39
- leetcode 40
- leetcode 216
- leetcode 78
- leetcode 90
- leetcode 401
Возврат на 2D-плоскость
leetcode79. Поиск слов
Идеи решения проблем
Для каждой позиции мы ищем в четырех направлениях в соответствии с верхним, правым, нижним и левым. Когда выбранное направление совпадает, выберите эту позицию, чтобы продолжить поиск верхнего, правого, нижнего и левого. Если четыре направления не совпадают, затем вернитесь в предыдущее положение Найдите следующее направление.
Код
class Solution {
//从board[startx][starty]开始， 寻找[index...word.size()]
private:
vector<vector<bool>> visited;
int m,n;//行与列
int d[4][2] = {{-1,0}, {0, 1}, {1, 0}, {0, -1}};
bool inArea(int x, int y){
return x >= 0 && x < m && y >= 0 && y < n;
}
bool searchWord(vector<vector<char>>& board, string word, int index, int startx, int starty){
//寻找到最后一个元素了
if (index == (word.size() -1)){
return board[startx][starty] == word[index];
}
if (board[startx][starty] == word[index]){
visited[startx][starty] = true;
// 从startx, starty出发,向四个方向寻
for (int i = 0; i < 4; i++){
int newx = startx + d[i][0];
int newy = starty + d[i][1];
if(inArea(newx, newy) && !visited[newx][newy]){
if (searchWord(board, word, index + 1, newx, newy)){
return true;
}
}
}
//回溯
visited[startx][starty] = false;
}
return false;
}
public:
bool exist(vector<vector<char>>& board, string word) {
m = board.size();
assert(m > 0);
n = board[0].size();
//初始化visitor
for (int i = 0; i < m ; i++){
visited.push_back(vector<bool>(n, false));
}
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
if (searchWord(board, word, 0, i, j)){
return true;
}
}
}
return false;
}
};
алгоритм заливки, класс классических задач
литкод 200. Количество островов
Идеи решения проблем
Сначала начнем с начала двумерного массива (0,0) Это место равно 1, и мы нашли новый остров, но нам нужно отметить землю, которая принадлежит тому же острову, что и эта земля. мы ищем Это не повторится на следующем острове. Тогда этот процесс является процессом заливки. По сути, это обход в глубину из начальной точки, который очень похож на поиск вышеприведенной задачи, и ищет каждый остров в четырех направлениях.
Код
class Solution {
private:
int d[4][2] = {{0,1}, {0, -1}, {1,0},{-1, 0}};
int m, n;
vector<vector<bool>> visited;
bool inArea(int x, int y){
return x >= 0 && x < m && y >= 0 && y < n;
}
void dfs(vector<vector<char>>& grid, int x, int y){
visited[x][y] = true;
for (int i = 0; i < 4; i++){
int newx = x + d[i][0];
int newy = y + d[i][1];
if (inArea(newx, newy) && !visited[newx][newy] && grid[newx][newy] == '1'){
dfs(grid, newx, newy);
}
}
return;
}
public:
int numIslands(vector<vector<char>>& grid) {
m = grid.size();
if (m == 0){
return 0;
}
n = grid[0].size();
if (n == 0){
return 0;
}
for (int i = 0; i < m; i++){
visited.push_back(vector<bool>(n, false));
}
int res = 0;
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
if (grid[i][j] == '1' && !visited[i][j]){
dfs(grid, i, j);
res++;
}
}
}
return res;
}
};
Здесь мы, кажется, не видим процесс поиска с возвратом, что означает, что нам не нужно находить позицию, в которой посещенный[x][y] является ложным, потому что наша цель — сопоставить оригинал (i,j) мы побежали. Острова, соединенные этой точкой, все отмечены, вместо того, чтобы найти в них конкретную последовательность или конкретное значение, поэтому мы отмечаем только true, и мы не будем отмечать его назад как false. Так что вопрос о том, называется ли этот вопрос возвратом, зависит от мнения. В процессе поиска он должен вернуться назад, что является характеристикой рекурсии. Но это не сбрасывало информацию. Однако его идея решения проблем — классическая заливка.
аналогичная проблема
- leetcode 130
- leetcode 417
Бэктрекинг — основа классического искусственного интеллекта
Возвращение к основам классического ИИ Мастера
буквенный код 51. Королева N
Идеи решения проблем
**Быстро определить юридическую ситуацию
- dia1: добавить одинаковые горизонтальные и вертикальные координаты
- dia2: абсцисса - ордината такая же
На примере четырех ферзей давайте посмотрим, как выполнить рекурсивный возврат. Прежде всего, в каждом ряду должна быть одна ферзь, иначе в одном ряду будет несколько ферзей. Тогда второй ряд может быть только в третьей позиции или четвертой позиции, учитывая третью позицию. Тогда третья строка будет иметь конфликт, где бы она ни находилась. Объясните, что ферзя нашего второго ряда нельзя поставить на третью позицию, мы отступаем и ставим ферзя на четвертую позицию.
Попробуйте разместить ферзя в ряд за раз, чтобы увидеть, сможем ли мы разместить ферзя.Если мы не можем, вернитесь к предыдущему ряду и снова поместите ферзя в предыдущий ряд, пока мы не поместим ферзей на все четыре ряды.
Код
class Solution {
private:
vector<bool> col, dia1, dia2;
vector<vector<string>> res;
//尝试在一个n皇后问题中，摆放第index行的皇后位置
void putQueen(int n, int index, vector<int> &row){
if (index == n){
res.push_back(generateBoard(n, row));
return;
}
// 尝试将第index行的皇后摆放在第i列
for (int i = 0; i < n; i++){
if (!col[i] && !dia1[index + i] && !dia2[index -i + n -1]){
row.push_back(i);
col[i] = true;
dia1[index + i] = true;
dia2[index -i + n -1] = true;
//递归,尝试下一行
putQueen(n, index + 1, row);
//回溯，复原
col[i] = false;
dia1[index + i] = false;
dia2[index -i + n -1] = false;
row.pop_back();
}
}
return;
}
vector<string> generateBoard(int n, vector<int> &row){
assert(n == row.size());
vector<string> board(n, string(n, '.'));
for(int i = 0; i < n; i++){
board[i][row[i]] = 'Q';
}
return board;
}
public:
vector<vector<string>> solveNQueens(int n) {
res.clear();
col.clear();
dia1.clear();
dia2.clear();
col = vector<bool>(n, false);
dia1 = vector<bool>(2*n -1, false);
dia2 = vector<bool>(2*n -1, false);
vector<int> row;
putQueen(n, 0, row);
return res;
}
};
аналогичная проблема
- leetcode 52
- leetcode 37
------------------------- Великолепная разделительная линия --------------------
Друзья, которые прочитали это, могут нажать «Нравится» / «Подписаться», ваша поддержка — самая большая поддержка для меня.
личный блогСтек томатной технологиииДомашняя страница Наггетс
Если вы хотите узнать больше, обратите внимание на мой публичный аккаунт в WeChat: Tomato Technology Stack.