date: 2020/01/30

基本概念

深度优先搜索:Depth First Search, DFS

广度优先搜索:Breadth First Search, BFS

路径搜索的两个基本思路,一个以深度优先(一条路走到黑),另一个以广度优先(每个分岔口都走一下看看)

主要可以参考二叉树的遍历:

剪枝就是提前预判出哪些路一定是死路(不符合要求),减少需要搜索的路径


104二叉树的最大深度(简单)

https://leetcode-cn.com/problems/maximum-depth-of-binary-tree

int helper(TreeNode* root, int depth){
    if(root == NULL) return depth - 1;
    return max(helper(root->left, depth+1), helper(root->right, depth+1));
}

int maxDepth(TreeNode* root) {
    return helper(root, 1);
}


111二叉树的最小深度(简单)

https://leetcode-cn.com/problems/minimum-depth-of-binary-tree

与104接近,但不完全一样,不能直接把max换成min——考虑存在结点只有左/右分支的情况

int helper(TreeNode* root, int depth){
    if(root == NULL) return INT_MAX;
    if(root->left == NULL && root->right == NULL) return depth;
    return min(helper(root->left, depth+1), helper(root->right, depth+1));
}

int minDepth(TreeNode* root) {
    if(root == NULL) return 0;
    return helper(root, 1);
}


022括号生成(中等)

https://leetcode-cn.com/problems/generate-parentheses

void generateParenthesis(vector<string> &vec, string s, int n, int left, int right){
    if(s.size() == n * 2){  // 字符串构造完成
        vec.push_back(s);
    }else{
        if(left < n)    // 有可用左括号,尝试添加
            generateParenthesis(vec, s + '(', n, left + 1, right);
        if(right < left)    // 左括号有剩余,可添加右括号
            generateParenthesis(vec, s + ')', n, left, right + 1);
    }
}

vector<string> generateParenthesis(int n) {
    vector<string> result;
    generateParenthesis(result, "", n, 0, 0);
    return result;
}
void generateParenthesis(vector<string> &vec, string s, int n, int left, int right){
    if(left == n){  // 左括号用完啦,接下来只需要把右括号填满就是一个有效的字符串
        vec.push_back(s + string(2 * n - s.size(), ')'));
    }else{    // 左括号还有剩
        if(right < left)    // 右括号还有填入的空间
            generateParenthesis(vec, s + ')', n, left, right + 1);
        // 增加一个左括号
        generateParenthesis(vec, s + '(', n, left + 1, right);
    }
}

vector<string> generateParenthesis(int n) {
    vector<string> result;
    generateParenthesis(result, "", n, 0, 0);
    return result;
}


"144二叉树的前序遍历(中等)

此处为语雀文档,点击链接查看:https://www.yuque.com/yahei/hey-yahei/leetcode-tree#edwo6


"094二叉树的中序遍历(中等)

此处为语雀文档,点击链接查看:https://www.yuque.com/yahei/hey-yahei/leetcode-tree#4zP7j


"145二叉树的后序遍历(困难)

此处为语雀文档,点击链接查看:https://www.yuque.com/yahei/hey-yahei/leetcode-tree#gxWWS


"102二叉树的层次遍历(中等)

此处为语雀文档,点击链接查看:https://www.yuque.com/yahei/hey-yahei/leetcode-tree#c4AiF


051N皇后(困难)

https://leetcode-cn.com/problems/n-queens

回溯

// 根据status生成符合题目要求的vector<string>
vector<string> generate_solution(vector<int>& status, int n){
    vector<string> solution;
    for(vector<int>::iterator it = status.begin(); it != status.end(); it++){
        // solution.push_back(string(*it, '.') + "Q" + string(n - *it - 1, '.'));
        string s(n, '.');
        s[*it] = 'Q';
        solution.push_back(s);
    }
    return solution;
}

// 根据当前局势生成可执行的选项集合
unordered_set<int> available_options(vector<int>& status, int n){
    unordered_set<int> options;
    for(int i = 0; i < n; i++)
        options.insert(i);

    for(int i = 0; i < status.size(); i++){
        options.erase(status[i]);  // 同列
        options.erase(status[i] + (status.size() - i));  // 左斜方
        options.erase(status[i] - (status.size() - i));  // 右斜方
    }

    return options;
}

// 回溯
void helper(vector<vector<string>>& result, vector<int>& status, int n){
    if(status.size() == n){ // 完成目标
        result.push_back(generate_solution(status, n));
    }else{  // 探索下一行
        unordered_set<int> options = available_options(status, n);
        for(unordered_set<int>::iterator it = options.begin(); it != options.end(); it++){
            status.push_back(*it);   // 应用操作
            helper(result, status, n);  // 递归试探
            status.pop_back();  // 回溯
        }
    }
}

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> result;
    vector<int> status;
    helper(result, status, n);
    return result;
}
void helper(vector<vector<string>>& result, vector<string>& status, vector<int>& bitmap, int n){
    if(status.size() == n){   // 完成目标
        result.push_back(status);
    }else{  // 探索下一行
        for(int i = 0; i < n; i++){  // 逐列判断
            if((bitmap[status.size()] & (1 << i)) == 0){   // 有效位置
                bool valid_bitmap = true;   // 【剪枝】新的bitmap是有效的
                // 拷贝bitmap预判本次操作对后续行的影响以生成新的bitmap
                vector<int> next_bitmap = bitmap;
                for(int j = status.size() + 1; j < n; j++){ // 逐行处理
                    // 标记正下方的相应位置
                    next_bitmap[j] |= 1 << i;
                    // 标记左斜方的相应位置
                    int block_bit_left = i - (j - status.size());
                    if(block_bit_left >= 0)
                        next_bitmap[j] |= 1 << block_bit_left;
                    // 标记右斜方的相应位置
                    int block_bit_right = i + (j - status.size());
                    if(block_bit_right < n)
                        next_bitmap[j] |= 1 << block_bit_right;
                    // 【剪枝】如果某一行被完全标记,可以提前宣告这是一条死路
                    if(next_bitmap[j] == (1 << n) - 1){
                        valid_bitmap = false;
                        break;
                    }
                }
                // 如果新的bitmap有效,则添加进status并继续递归搜索
                if(valid_bitmap){
                    string s(n, '.');
                    s[i] = 'Q';
                    status.push_back(s);
                    helper(result, status, next_bitmap, n);
                    status.pop_back();
                }
            }
        }
    }
}

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> result;
    vector<string> status;
    vector<int> bitmap(n, 0);   // bit0表示可放置,bit1被标记表示不可放置
    helper(result, status, bitmap, n);
    return result;
}


052N皇后II(困难)

https://leetcode-cn.com/problems/n-queens-ii

051N皇后 类似,但不需要返回具体的结果,只需要返回结果的数量


036有效数独(中等)

https://leetcode-cn.com/problems/valid-sudoku

这道题跟搜索没啥关系,按题目判断条件是否符合即可

bool isValidSudoku(vector<vector<char>>& board) {
    // 用位串来记录数字1-9的使用情况
    vector<int> row_bitmap(9), col_bitmap(9), sub_bitmap(9);
    for(int row_idx = 0; row_idx < 9; row_idx++){
        for(int col_idx = 0; col_idx < 9; col_idx++){
            char c = board[row_idx][col_idx];
            if(c != '.'){
                int num_bit = 1 << (c - '1');
                int sub_idx = row_idx / 3 * 3 + col_idx / 3;
                if((row_bitmap[row_idx] & num_bit) != 0 || \
                   (col_bitmap[col_idx] & num_bit) != 0 || \
                   (sub_bitmap[sub_idx] & num_bit) != 0)
                        return false;
                row_bitmap[row_idx] |= num_bit;
                col_bitmap[col_idx] |= num_bit;
                sub_bitmap[sub_idx] |= num_bit;
            }
        }
    }
    return true;
}


037解数独(困难)

https://leetcode-cn.com/problems/sudoku-solver

跟N皇后差不多

// 获取下一个需要填写的空格
pair<int, int> getNextBlank(vector<vector<char>>& board, pair<int, int>& cur_blank){
    int cur_row = cur_blank.first, cur_col = cur_blank.second;
    for(int i = cur_row; i < 9; i++){
        for(int j = (i == cur_row) ? (cur_col +1) : 0 ; j < 9; j++){
            if(board[i][j] == '.')
                return make_pair(i, j);
        }
    }
    // 任务已完成
    return make_pair(-1, -1);
}

bool helper(vector<vector<char>>& board, pair<int, int> cur_blank,
            vector<int>& row_bitmap, vector<int>& col_bitmap, vector<int>& sub_bitmap){
    int cur_row = cur_blank.first, cur_col = cur_blank.second;
    int cur_sub = cur_row / 3 * 3 + cur_col / 3;
    // 任务已完成
    if(cur_row == -1 && cur_col == -1)
        return true;
    // 尝试填入数值1-9
    for(int i = 0; i < 9; i++){
        int num_bit = 1 << i;
        // 检查bitmap,如果数值有效
        if((row_bitmap[cur_row] & num_bit) == 0 && \
           (col_bitmap[cur_col] & num_bit) == 0 && \
           (sub_bitmap[cur_sub] & num_bit) == 0){
            // 备份当前bitmap(不需要保存整个bitmap)
            int backup_rowbit = row_bitmap[cur_row];
            int backup_colbit = col_bitmap[cur_col];
            int backup_subbit = sub_bitmap[cur_sub];
            // 填入数值
            row_bitmap[cur_row] |= num_bit;
            col_bitmap[cur_col] |= num_bit;
            sub_bitmap[cur_sub] |= num_bit;
            board[cur_row][cur_col] = i + '1';
            // 递归探索
            if(helper(board, 
                      getNextBlank(board, cur_blank), 
                      row_bitmap, col_bitmap, sub_bitmap)){
                return true;
            }
            // 恢复bitmap
            board[cur_row][cur_col] = '.';
            row_bitmap[cur_row] = backup_rowbit;
            col_bitmap[cur_col] = backup_colbit;
            sub_bitmap[cur_sub] = backup_subbit;
        }
    }
    return false;
}

void solveSudoku(vector<vector<char>>& board) {
    vector<int> row_bitmap(9), col_bitmap(9), sub_bitmap(9);
    // 记录第一个需要填写的空格
    int next_row, next_col;   
    bool first_blank = true;
    // 初始化bitmap
    for(int row_idx = 0; row_idx < 9; row_idx++){
        for(int col_idx = 0; col_idx < 9; col_idx++){
            char c = board[row_idx][col_idx];
            if(c != '.'){   // 非空格
                int num_bit = 1 << (c - '1');
                int sub_idx = row_idx / 3 * 3 + col_idx / 3;
                row_bitmap[row_idx] |= num_bit;
                col_bitmap[col_idx] |= num_bit;
                sub_bitmap[sub_idx] |= num_bit;
            }else if(first_blank){  // 第一个空格
                next_row = row_idx;
                next_col = col_idx;
                first_blank = false;
            }
        }
    }
    // 递归探索
    helper(board, make_pair(next_row, next_col), row_bitmap, col_bitmap, sub_bitmap);
}


"079单词搜索(中等)

此处为语雀文档,点击链接查看:https://www.yuque.com/yahei/hey-yahei/trie#U4Ro8


"212单词搜索II(困难)

此处为语雀文档,点击链接查看:https://www.yuque.com/yahei/hey-yahei/trie#HCuOD


"200岛屿数量(中等)