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