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

Leetcode332.重新安排行程

文章链接：代码随想录
题目链接：332.重新安排行程

class Solution {
public:
    unordered_map<string, map<string, int>> targets;
    bool backtracking(int ticketNum, vector<string>& result){
        if (result.size() == ticketNum + 1){
            return true;
        }

        for (pair<const string, int>& target : targets[result[result.size() - 1]]){
            if (target.second > 0){
                result.push_back(target.first);
                target.second--;
                if (backtracking(ticketNum, result)) return true;
                target.second++;
                result.pop_back();
            }
        }
        return false;
    }

    vector<string> findItinerary(vector<vector<string>>& tickets) {
        vector<string> result;
        for (const vector<string>& vec : tickets){
            targets[vec[0]][vec[1]]++;
        }
        result.push_back("JFK");
        backtracking(tickets.size(), result);
        return result;
    }
};

Leetcode51. N皇后

文章链接：代码随想录
思路链接：51. N皇后

class Solution {
public:
    vector<vector<string>> res;
    void backtracking(int n, int row, vector<string>& chessboard){
        if (row == n){
            res.push_back(chessboard);
            return ;
        }

        for (int col = 0; col < n; col++){
            if (isValid(col, row, chessboard, n)){
                chessboard[row][col] = 'Q';
                backtracking(n, row + 1, chessboard);
                chessboard[row][col] = '.';
            }
        }
    }

    bool isValid(int col, int row, vector<string>& chessboard, int n){
        for (int i = 0; i < row; i++) { 
            if (chessboard[i][col] == 'Q') {
                return false;
            }
        }
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){
            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;
    }
    
    vector<vector<string>> solveNQueens(int n) {
        vector<string> chessboard(n, string(n, '.'));
        backtracking(n, 0, chessboard);
        return res;
    }
};

Leetcode37. 解数独

文章链接：代码随想录
思路链接：37. 解数独

class Solution {
public:
    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] == '.'){
                    for (char k = '1'; k <= '9'; k++){
                        if (isValid(i, j, k, board)){
                            board[i][j] = k;
                            if (backtracking(board)) return true;
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }   
        }
        return true;
    }

    bool isValid(int row, int col, char val, vector<vector<char>>& board){
        for (int i = 0; i < board.size(); i++){
            if (board[i][col] == val) return false;
        }
        for (int j = 0; j < board[0].size(); j++){
            if (board[row][j] == val) 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] == val) return false;
            }
        }
        return true;
    }

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

2023.12.28
今天作项目解题PPT太忙没空做，先站个位

2023.12.29
今天忙着为明天拍摄实验做调试准备，按着昨天看解析文章的理解，今天又大致看了一遍敲出来了三道题，今天的题没刷。
这几天太忙没时间刷题学和计算机基础，今天也没健身，明天实验估计又没时间，跨年前估计不会学出太多了；不过还好前一个无关的项目今天结题了，明天是做课题相关实验，也不算浪费时间，一切还是向着好的方向发展，丢掉焦虑，停止内耗，踏实做自己能做的事就好。
希望明天实验顺利，跨年那天上午练个肩，下午回家，顺便发个跨年健身的朋友圈（文案想了十几天还没想好哈哈哈，不过图片选好了就一张），然后把今明两天的题补上。明后天有时间就再看点操作系统，加油！！！