代码随想录算法训练营第三十天|332.重新安排行程、51. N皇后、37. 解数独

发布时间:2024年01月12日

题目:332.重新安排行程

文章链接:代码随想录

题目链接:力扣题目链接

图释:

class Solution {
public:
    // unordered_map<出发机场, map<抵达机场, 航班次数>> targrts;
    unordered_map<string, map<string,int>> targrts;
 
    bool backtracking(int ticketNum, vector<string>& result){
        // 所有机票都要用一次 
        if(result.size() == ticketNum+1){ //航线次数+1
            return true;
        }
        // targrts[result[result.size()-1]] 从结果集里的最后一个目的地,作为出发地,找到以航班中的航线
        for(pair<const string, int>& targrt: targrts[result[result.size()-1]]){
            if(targrt.second > 0){ // 检测本航线是否飞过
               result.push_back(targrt.first);
               targrt.second--;
               if(backtracking(ticketNum, result)) return true; // 如果下层递归有返true则继续向上返回true
               // 没有返回找到航班则回溯
               result.pop_back();
               targrt.second++;
            }
        }
        // 遍历完,以该地点作为出发地的航线都不行,则返回
        return false; 
    }

    vector<string> findItinerary(vector<vector<string>>& tickets) {
        targrts.clear();
        vector<string> result;
        // vec = ["MUC","LHR"] 遍历赋值给vec
        for(const vector<string> vec : tickets){
            // <MUC <LHR, 1>>
            targrts[vec[0]][vec[1]]++;
        }
        result.push_back("JFK"); // 放入首发机场
        backtracking(tickets.size(), result); // 航线次数
        return result;
    }
};

题目:51. N皇后

文章链接:代码随想录

视频链接:LeetCode:51.N皇后

题目链接:力扣题目链接

图释:

class Solution {
public:
    vector<vector<string>> result;
    bool isValid(int row, int col, vector<string> chessboard, int n){
       // 检测列
       for(int i=0; i<n; i++){
           if(chessboard[i][col] == 'Q') return false;
       }
       // 检测45度角(上一行的左上角) 因为还没遍历到下一行,所以不用判断
       for(int i=row-1, j=col-1; i>=0 && j>=0; i--,j--){
           // 当row==clo==0时,不会进入
           if(chessboard[i][j] == 'Q') return false; // 一直循环向↖找
       }
        for(int i=row-1, j=col+1; i>=0 && j<=n; i--,j++){
           if(chessboard[i][j] == 'Q') return false; // 一直循环向↗找
       }
       return true;
    }    
    // 传入棋盘
    void backtracking(vector<string> chessboard, int n, int row){
        if(row == n){
            // 在进入递归之前就判断该位置能否放入皇后了,所以当递归到最后一行,说明是合法的
            result.push_back(chessboard);
            return;
        }
        // 树层逻辑  遍历某行的每一列
        for(int col=0; col<n; col++){
            if(isValid(row, col, chessboard, n)){ // 判断该位置是否合法
               chessboard[row][col] = 'Q'; // 放置皇后
               backtracking(chessboard, n, row+1);
               chessboard[row][col] = '.'; // 回溯,撤销皇后
            }
        }
        // 可加可不加,不加的话就是当层遍历完,没有的话,自动退出
        return ;
    }
  
    vector<vector<string>> solveNQueens(int n) {
        result.clear();
        // 根据传入的n构建棋盘格
        std::vector<std::string> chessboard(n, std::string(n, '.'));
        backtracking(chessboard, n, 0);
        return result;
    }
};

题目:37. 解数独

文章链接:代码随想录

视频链接:LeetCode:

题目链接:力扣题目链接

图释:

class Solution {
public:
    bool isValid(int row, int col, char k, vector<vector<char>>& board){
        for(int i=0; i<9; i++){// 判断行有无重复
           if(board[row][i]==k)return false;
        }
        for(int j=0; j<9; j++){// 判断列有无重复
           if(board[j][col]==k)return false;
        }
        // 判断格子中有无重复
        int startRow = (row/3)*3; 
        int startCol = (col/3)*3;
        for(int i=startRow; i<startRow+3; i++){ // 注意这里是小于,不用等号
            for(int j=startCol; j<startCol+3; j++){
                if(board[i][j]==k) return false;
            }
        }
        // 如果遍历完都没有不合法,则合法
        return true;
    }

    // 如果是需要遍历所有的路径,把结果放到result中就用void 不需要返回值,由终止条件终止
    // 如果只需要找到一条合法的路径,则用bool,当找到一条时,一层一层向上返回true,不需要再遍历
    bool backtracking(vector<vector<char>>& board){
        // 二维递归
        for(int i=0; i<board.size(); i++){  // 行
            for(int j=0; j<board[0].size(); j++){ // 列

                // 如果当前位置不为空,则向下继续
                if(board[i][j] !='.'){
                    continue;
                }
                // 循环放入1-9个数
                for(char k='1'; k<='9'; k++){

                    // 判断这个位置和否合法
                    if(isValid(i,j,k,board)){
                        board[i][j] = k; // k 是 char类型
                        if(backtracking(board)) {
                           return true; // 如果下层递归返回true,说明找到解法,继续向上进行返回
                        }
                        // 没有找到,则换另外一个数再进行尝试
                        board[i][j] = '.';
                    } 
                }
                // 如果9个数都尝试完了都不符合,则返回false
                return false;
                }
        }
        // 如果遍历完网格中所有的格子都没有false的话,则说明找到解法了
        return true;
    }

    void solveSudoku(vector<vector<char>>& board) {
        backtracking(board);
    }
};

文章来源:https://blog.csdn.net/m0_71413464/article/details/135527942
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。