AI 助理
备案控制台
开发者社区 人工智能 文章 正文

LeetCode刷题系列(一)把回溯算法框架将给爷爷奶奶听（下）

2023-08-05 45
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： LeetCode刷题系列(一)把回溯算法框架将给爷爷奶奶听（下）

基于回溯框架求解之八皇后


  上述的题目都是在一维的角度求解回溯问题，比如像一个数组，一个字符串这样去展开递归树，但是有一些题目是二维的，需要我们进行二维的递归树展开。比如像Leetcode面试题 08.12. 八皇后问题， 说的是：设计一种算法，打印N皇后在N × N棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。示例:

输入：4
 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
 解释: 4 皇后问题存在如下两个不同的解法。
[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],
 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]

  每一行每一列都只能放一个，按照习惯，我们假设一行放一个，这样的话我们就需要对列进行遍历，然后每行依次递增，此时的递归树的全展开代码如下所示：

void backtrack(vector<string>& s, int index, int n){ // index表示行
    for(int column=0; column<n; ++column){
        s[index][column] ='Q';
        backtrack(s, index+1, n);
        s[index][column] = '.';
    }
}

  按照上述这个全展开，每一行的每个位置都会被放置一个'Q'的全部结果都会遍历得到，这棵树我们是展开了，接下来就是剪枝了。但是在剪枝之前，我们可以先写一首终止条件，也就是将计算得到的某个结果添加到最终的结果中去。终止条件就是当行遍历到最后一行的时候：

void backtrack(vector<string>& s, int index, int n){
  if(index == n){
        res.push_back(s);
        return;
    }
    for(int column=0; column<n; ++column){
        s[index][column] ='Q';
        backtrack(s, index+1, n);
        s[index][column] = '.';
    }
}

  接下来我们就只需要处理剪枝即可，依据题意，每一行每一列都只能有一个Q，因为我们遍历的时候就是按照行来遍历的，那么对于每一列，我们要保证它不能与其它列重合，那这不就可以用一个集合来记录哪一列被选中了，此时如果当前列在集合中的话，就剪枝去掉即可。这样列的剪枝就可以实现了：

unordered_set<int> set_column;
void backtrack(vector<string>& s, int index, int n){
  if(index == n){
        res.push_back(s);
        return;
    }
    for(int column=0; column<n; ++column){
      if(set_column.count(column)){ // 第一重剪枝
           continue;
        }
        set_column.insert(column);
        s[index][column] ='Q';
        backtrack(s, index+1, n);
        s[index][column] = '.';
        set_column.erase(column);
    }
}

  还有一个就是斜对角的，因为我们是从上往下依次每行放Q的，所以我们只需要检查左上角，还有右上角上是不是有Q，有的话，我们也需要去剪枝，我们写一个函数，输入当前的棋盘s和当前的row和column，还有判断棋盘边界必须的棋盘长度n：

bool Have_Q(vector<string>& s, int row, int column, int n){
    for(int i=row-1, j=column-1; i>=0 && j>=0; --i, --j){
        if(s[i][j] == 'Q') return true;
    }
    for(int i=row-1, j=column+1; i>=0 && j<n; --i, ++j){
        if(s[i][j] == 'Q') return true;
    }
    return false;
}

  之后我们就可以设置第二层剪枝了：

void backtrack(vector<string>& s, int index, int n){
    if(index == n){
        res.push_back(s);
        return;
    }
    for(int column=0; column<n; ++column){
        if(set_column.count(column)){ // 第一层剪枝
            continue;
        }
        if(Have_Q(s, index, column, n)){ // 第二层剪枝
            continue;
        }
        set_column.insert(column);
        s[index][column] ='Q';
        backtrack(s, index+1, n);
        s[index][column] = '.';
        set_column.erase(column);
    }
}

  到此，回溯算法的主逻辑就写完了，全部代码如下所示：

class Solution {
public:
    vector<vector<string>> res;
    unordered_set<int> set_column;
    vector<vector<string>> solveNQueens(int n) {
        vector<string> s(n, string(n, '.'));
        backtrack(s, 0, n);
        return res;
    }
    void backtrack(vector<string>& s, int index, int n){ // index表示行
        if(index == n){
            res.push_back(s);
            return;
        }
        for(int column=0; column<n; ++column){
            if(set_column.count(column)){ // 第一层剪枝
                continue;
            }
            if(Have_Q(s, index, column, n)){ // 第二层剪枝
                continue;
            }
            set_column.insert(column);
            s[index][column] ='Q';
            backtrack(s, index+1, n);
            s[index][column] = '.';
            set_column.erase(column);
        }
    }
    bool Have_Q(vector<string>& s, int row, int column, int n){
        for(int i=row-1, j=column-1; i>=0 && j>=0; --i, --j){
            if(s[i][j] == 'Q') return true;
        }
        for(int i=row-1, j=column+1; i>=0 && j<n; --i, ++j){
            if(s[i][j] == 'Q') return true;
        }
        return false;
    }
};

基于回溯框架求解之单词搜索


  花，花里胡哨的回溯框架的题目它，它又来了。LeetCode 79. 单词搜索：给定一个m x n二维字符网格board和一个字符串单词word。如果word存在于网格中，返回true；否则，返回false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。示例1：

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

  还是那句话，只要全展开递归树能够全展开，这类题目其实就已经做了一大半了。说白了其实就是在网格里面搜一条路径，那么对于每个网格的位置上面，能够选择的方向只有四个，因此我们可以对这四个方向进行for循环遍历，然后把这颗递归树展开：

vector<pair<int, int>> direction{{0,1}, {0,-1}, {1, 0}, {-1, 0}};
void backtrack(vector<vector<char>>& board, vector<vector<int>>& vis, string& word, int row, int column, int index){
    for(pair<int, int>dir : direction){
        row = row + dir.first;
        column = column + dir.second;
        backtrack(board, vis, word, row, column, index+1);
        row = row - dir.first;
        column = column - dir.second;
    }
}

  上述代码中，我们把方向放在一个vector数组里面，里面存的是一个pair<int, int>数组。之后还有一个终止条件，还有剪枝需要去处理，我们先来处理一下终止条件，就是当index访问到了最后一个word的长度嘛，那就是对word中的每个字符都检查了一遍。

void backtrack(vector<vector<char>>& board, vector<vector<int>>& vis, string& word, int row, int column, int index){
    if(index == word.size()){ // 终止条件满足，返回结果
        res = true; 
        return;
    }
    for(pair<int, int>dir : direction){
        row = row + dir.first;
        column = column + dir.second;
        backtrack(board, vis, word, row, column, index+1);
        row = row - dir.first;
        column = column - dir.second;
    }
}

  剩下的一件事情就是剪枝了，首先就是访问的边界条件，如果越界，我们是需要剪枝的，如果访问到了之前已经访问过的元素，我们也是需要去剪枝的，字符不相等的时候我们也是需要去剪枝的。所以我们需要一个二维数组去记录哪些元素已经被访问过了。然后还需要去写一个剪枝的函数：

void backtrack(vector<vector<char>>& board, vector<vector<int>>& vis, string& word, int row, int column, int index){
    if(index == word.size()){ // 终止条件满足，返回结果
        res = true; 
        return;
    }
    for(pair<int, int>dir : direction){
        if(Purning(board, vis, word, row, column, index)) continue; // 剪枝
        vis[row][column] = 1;
        row = row + dir.first;
        column = column + dir.second;
        backtrack(board, vis, word, row, column, index+1);
        row = row - dir.first;
        column = column - dir.second;
        vis[row][column] = 0;
    }
}
bool Purning(vector<vector<char>>& board, vector<vector<int>>& vis, string& word, int row, int column, int index){
    if(row < 0 || row >= board.size() || column < 0 || column >= board[0].size()) return true; // 边界情况剪枝。
    if(board[row][column] == word[index] && !vis[row][column]) return false; // 值不相等情况，和已访问过该节点情况，剪枝。
    else return true;
}

  到此整颗递归搜索树就构建完毕了。但是这道题目还有一个骚操作，就是这个递归树展开的根节点是会变动的，也就是说矩阵中的元素与word单词第一个字符相等的时候我们才需要去递归展开这颗递归树，因此我们可以得到完整代码如下所示：

class Solution {
public:
    bool res = false;
    vector<pair<int, int>> direction{{0,1}, {0,-1}, {1, 0}, {-1, 0}};
    bool exist(vector<vector<char>>& board, string word) {
        vector<vector<int>> vis(board.size(), vector<int>(board[0].size()));
        for(int i=0; i<board.size(); ++i){
            for(int j=0; j<board[0].size(); ++j){
                if(board[i][j] == word[0]){
                    backtrack(board, vis, word, i, j, 0);
                    if(res) return res;
                }
            }
        }
        return res;
    }
    void backtrack(vector<vector<char>>& board, vector<vector<int>>& vis, string& word, int row, int column, int index){
        if(index == word.size()){ // 终止条件满足，返回结果
            res = true; 
            return;
        }
        for(pair<int, int>dir : direction){
            if(Purning(board, vis, word, row, column, index)) continue; // 剪枝
            vis[row][column] = 1;
            row = row + dir.first;
            column = column + dir.second;
            backtrack(board, vis, word, row, column, index+1);
            row = row - dir.first;
            column = column - dir.second;
            vis[row][column] = 0;
        }
    }
    bool Purning(vector<vector<char>>& board, vector<vector<int>>& vis, string& word, int row, int column, int index){
        if(row < 0 || row >= board.size() || column < 0 || column >= board[0].size()) return true; // 边界情况剪枝。
        if(board[row][column] == word[index] && !vis[row][column]) return false; // 值不相等情况，和已访问过该节点情况，剪枝。
        else return true;
    }
};

基于回溯框架求解之解数独

  等等，还没完，回溯算法还有更骚的题，但是万变不离其宗，我们来看一下LeetCode 37. 解数独，编写一个程序，通过填充空格来解决数独问题。数独的解法需 遵循如下规则：数字1-9在每一行只能出现一次。数字1-9在每一列只能出现一次。数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）数独部分空格内已填入了数字，空白格用 ‘.’ 表示。示例：

输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

  解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

  这道题目与之前的几道不一样的地方在于它还有一些骚操作，如果想要全展开，不仅要对这个二维矩阵进行遍历，并且在每个小格子上面还需要对数字1-9进行遍历，并且与之前的回溯算法不一样的地方在于，如果这里找到了一个可行解的话，我们就需要返回了，不然会被回溯回去，就相当于什么都没做了。因此我们将回溯函数backtrack()的返回值类型不再设置为void类型，而是将其设置为bool类型，此时全展开的代码可以写成如下形式：

bool backtrack(vector<vector<char>>& board, int index){
  if(index == 9*9) return true;
    int row = index / 9;
    int column = index % 9;
    for(int i=1; i<=9; ++i){ // 每个方格上遍历放九个数字
        board[row][column] = i+'0';
        if(backtrack(board, index+1))  return true;
        board[row][column] = '.';
    }
    return false;
}

  上述代码中已经加入了终止条件，我们只需要再加入剪枝即可，这里的剪枝分为两种情况，如果被选中的小方格中有元素的话，我们就跳过，返回下一个元素的求解结果：

if(board[row][column] != '.'){ // 给定行和列上已经有数字后，进行剪枝
    return backtrack(board, index+1);
}

  如果是给定的1-9中某个数字不合适的话，我们就continue换掉这个数字，可以写一个剪枝函数来实现这个事情：

bool Pruning(vector<vector<char>>& board, int row, int column, char str_i){
    for(int i=0; i<9; ++i){ 
        if(board[row][i] == str_i) return true; // 对列遍历，剪枝
        if(board[i][column] == str_i) return true; // 对行遍历，剪枝
    }
    int row_new = (row/3)*3, column_new = (column/3)*3; // 对小的九宫格进行遍历
    for(int i=row_new; i<row_new+3; ++i){
        for(int j=column_new; j<column_new+3; ++j){
            if(board[i][j] == str_i) return true;
        }
    }
    return false;
}

  所有的代码如下所示：

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        backtrack(board, 0);
    }
    bool backtrack(vector<vector<char>>& board, int index){
        if(index == 9*9) return true;
        int row = index / 9;
        int column = index % 9;
        for(int i=1; i<=9; ++i){ // 每个方格上遍历放九个数字
            if(board[row][column] != '.'){ // 给定行和列上已经有数字后，进行剪枝，这一剪枝条件放到for循环外面也是可以的
                return backtrack(board, index+1);
            }
            if(Pruning(board, row, column, i+'0')){
                continue;
            }
            board[row][column] = i+'0';
            if(backtrack(board, index+1))  return true;
            board[row][column] = '.';
        }
        return false;
    }
    bool Pruning(vector<vector<char>>& board, int row, int column, char str_i){
        //if(board[row][column] != '.') return true;
        for(int i=0; i<9; ++i){ 
            if(board[row][i] == str_i) return true; // 对列遍历，剪枝
            if(board[i][column] == str_i) return true; // 对行遍历，剪枝
        }
        int row_new = (row/3)*3, column_new = (column/3)*3; // 对小的九宫格进行遍历
        for(int i=row_new; i<row_new+3; ++i){
            for(int j=column_new; j<column_new+3; ++j){
                if(board[i][j] == str_i) return true;
            }
        }
        return false;
    }
};

参考


文章标签：
机器学习/深度学习
算法
关键词：
LeetCode算法
回溯算法
LeetCode刷题
回溯算法框架
算法框架
小小何先生
目录
相关文章
肾透侧视攻城狮
|
17天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串（12）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丟脸好嘛？】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明；【含常见的报错问题及其对应的解决方法】你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
19 2
2024重生之回溯数据结构与算法系列学习之串（12）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丟脸好嘛？】
小王老师呀
|
9天前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合，并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构，遍历字符串时将左括号压入栈中，遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
小王老师呀
26 4
肾透侧视攻城狮
|
17天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习（8）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
19 3
肾透侧视攻城狮
|
17天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的；不然别给我家鸽鸽丢脸好嘛？】
顺序表的定义和基本操作之插入；删除；按值查找；按位查找等具体详解步骤以及举例说明
肾透侧视攻城狮
24 3
肾透侧视攻城狮
|
17天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解（9）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
19 2
肾透侧视攻城狮
|
17天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构之单双链表按位、值查找；[前后]插入；删除指定节点；求表长、静态链表等代码及具体思路详解步骤；举例说明、注意点及常见报错问题所对应的解决方法
肾透侧视攻城狮
20 2
肾透侧视攻城狮
|
17天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总（10）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
17 1
肾透侧视攻城狮
|
17天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的；不然别给我家鸽鸽丢脸好嘛？】
顺序表的定义和基本操作之插入；删除；按值查找；按位查找习题精讲等具体详解步骤以及举例说明
肾透侧视攻城狮
17 1
肾透侧视攻城狮
|
17天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习【无论是王道考研人还真爱粉都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构的基本概念；算法的基本概念、特性以及时间复杂度、空间复杂度等举例说明；【含常见的报错问题及其对应的解决方法】
肾透侧视攻城狮
17 1
肾透侧视攻城狮
|
17天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二（5）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
13 0

热门文章

最新文章

  • 1
    线性排序算法（1）
  • 2
    【推荐算法】商品推荐_3041
  • 3
    [干货]基础机器学习算法
  • 4
    泛型KMP算法
  • 5
    《操作系统》—— 处理机调度算法
  • 6
    算法学习之顺序结构
  • 7
    【算法】算法之美—Fire Net
  • 8
    OneMob（一体传媒）：大数据算法 让营销更精准
  • 9
    A* + 弗洛伊德 算法 打造 360 向寻路 - [ActionScript3.0]
  • 10
    【数据结构与算法】一篇文章彻底搞懂二分查找（思路图解+代码优化）两种实现方式，递归与非递归
  • 1
    155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
    45
  • 2
    1124. 表现良好的最长时间段 (python) 前缀和 分类讨论 最大长度 力扣 面试题
    52
  • 3
    经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目（面试题）
    50
  • 4
    刷算法Leetcode---9（二叉树篇Ⅲ）
    36
  • 5
    2670.找出不同元素数目差数组-力扣(LeetCode)
    32
  • 6
    821.字符的最短距离-力扣(LeetCode)
    32
  • 7
    力扣经典150题第六十题：反转链表 II
    26
  • 8
    力扣经典150题第五十九题： 随机链表的复制
    41
  • 9
    力扣经典150题第五十八题：合并两个有序链表
    40
  • 10
    力扣经典150题第五十六题：环形链表
    33

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 推荐系统入门之使用ALS算法实现打分预测
  • 欧拉图的构造性证明与算法实现
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 使用Swing算法实现商品推荐
    • 下一篇
    阿里云OSS设置跨域访问