第三十天打卡

重新安排行程

332. 重新安排行程
     困难
     745
     相关企业
     给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

例如，行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小，排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

示例 1：

输入：tickets = [[“MUC”,“LHR”],[“JFK”,“MUC”],[“SFO”,“SJC”],[“LHR”,“SFO”]]
输出：[“JFK”,“MUC”,“LHR”,“SFO”,“SJC”]
示例 2：

输入：tickets = [[“JFK”,“SFO”],[“JFK”,“ATL”],[“SFO”,“ATL”],[“ATL”,“JFK”],[“ATL”,“SFO”]]
输出：[“JFK”,“ATL”,“JFK”,“SFO”,“ATL”,“SFO”]
解释：另一种有效的行程是 [“JFK”,“SFO”,“ATL”,“JFK”,“ATL”,“SFO”] ，但是它字典排序更大更靠后。

提示：

1 <= tickets.length <= 300
tickets[i].length == 2
fromi.length == 3
toi.length == 3
fromi 和 toi 由大写英文字母组成
fromi != toi

class Solution {
public:unordered_map> targets;vector res;vector findItinerary(vector>& tickets) {for(vector item:tickets){targets[item[0]][item[1]]++;}res.push_back("JFK");backtrack(tickets.size());return res;}bool backtrack(int ticketNum){if(res.size()==ticketNum+1){return true;}for(pair& target:targets[res[res.size()-1]]){if(target.second > 0){res.push_back(target.first);target.second--;if(backtrack(ticketNum)) return true;target.second++;res.pop_back();}}return false;}
};

N 皇后

51. N 皇后
    困难
    1.7K
    相关企业
    按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例 1：

输入：n = 4
输出：[[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：

输入：n = 1
输出：[[“Q”]]

提示：

1 <= n <= 9

class Solution {public:vector> res;/* 输入棋盘边长 n，返回所有合法的放置 */vector> solveNQueens(int n) {// '.' 表示空，'Q' 表示皇后，初始化空棋盘。vector board(n, string(n, '.'));backtrack(board, 0);return res;}// 路径：board 中小于 row 的那些行都已经成功放置了皇后// 选择列表：第 row 行的所有列都是放置皇后的选择// 结束条件：row 超过 board 的最后一行void backtrack(vector& board, int row) {// 触发结束条件if (row == board.size()) {res.push_back(board);return;}int n = board[row].size();for (int col = 0; col < n; col++) {// 排除不合法选择if (!isValid(board, row, col)) {continue;}// 做选择board[row][col] = 'Q';// 进入下一行决策backtrack(board, row + 1);// 撤销选择board[row][col] = '.';}}/* 是否可以在 board[row][col] 放置皇后？*/bool isValid(vector& board, int row, int col) {int n = board.size();// 检查列是否有皇后互相冲突for (int i = 0; i <= row; i++) {if (board[i][col] == 'Q')return false;}// 检查右上方是否有皇后互相冲突for (int i = row - 1, j = col + 1;i >= 0 && j < n; i--, j++) {if (board[i][j] == 'Q')return false;}// 检查左上方是否有皇后互相冲突for (int i = row - 1, j = col - 1;i >= 0 && j >= 0; i--, j--) {if (board[i][j] == 'Q')return false;}return true;}
};

解数独

37. 解数独
    困难
    1.6K
    相关企业
    编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

示例 1：

输入：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”]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

提示：

board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 ‘.’
题目数据 保证 输入数独仅有一个解

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码已经通过力扣的全部测试用例，可直接粘贴提交。class Solution {
public:void solveSudoku(vector>& board) {backtrack(board, 0, 0);}bool backtrack(vector>& board, int i, int j) {int m = 9, n = 9;if (j == n) {// 穷举到最后一列的话就换到下一行重新开始。return backtrack(board, i + 1, 0);}if (i == m) {// 找到一个可行解，触发 base casereturn true;}if (board[i][j] != '.') {// 如果有预设数字，不用我们穷举return backtrack(board, i, j + 1);}for (char ch = '1'; ch <= '9'; ch++) {// 如果遇到不合法的数字，就跳过if (!isValid(board, i, j, ch))continue;board[i][j] = ch;// 如果找到一个可行解，立即结束if (backtrack(board, i, j + 1)) {return true;}board[i][j] = '.';}// 穷举完 1~9，依然没有找到可行解，此路不通return false;}bool isValid(vector>& board, int r, int c, char n) {for (int i = 0; i < 9; i++) {// 判断行是否存在重复if (board[r][i] == n) return false;// 判断列是否存在重复if (board[i][c] == n) return false;// 判断 3 x 3 方框是否存在重复if (board[(r/3)*3 + i/3][(c/3)*3 + i%3] == n)return false;}return true;}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！