代码随想录算法训练营day30 | 题目332、题目51、题目37
题目一描述
给你一份航线列表 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
from 和 to 由大写英文字母组成
from != to
解题思路
用合适的数据结构存储机票信息，并做升序排列。
递归来深度优先搜索，找到第一个解法就是答案
代码实现
方法一：
class Solution {
List<String> res = new ArrayList<>();
boolean findFlag;
public List<String> findItinerary(List<List<String>> tickets) {
List<String> path = new ArrayList<>();
// <出发机场, <到达机场, 航班次数>> 存储机票信息，这样也方便根据机场名字去找
Map<String, Map<String, Integer>> map = new HashMap<>();
// 将机票信息存入图
for (List<String> ticket : tickets) {
String startPort = ticket.get(0);
String endPort = ticket.get(1);
Map<String, Integer> temp;
if (map.containsKey(startPort)) {
temp = map.get(startPort);
temp.put(endPort, temp.getOrDefault(endPort, 0) + 1);
map.put(startPort, temp);
} else {
temp = new TreeMap<>(); // 会根据键值升序排列
temp.put(endPort, 1);
map.put(startPort, temp);
}
}
path.add("JFK");
backtracking(path, map, tickets);
return res;
}
private void backtracking(List<String> path, Map<String, Map<String, Integer>> map, List<List<String>> tickets) {
if (findFlag) {
return;
}
if (path.size() == tickets.size() + 1) {
res = new ArrayList<>(path);
findFlag = true;
return;
}
String lastPort = path.get(path.size() - 1);
if (map.containsKey(lastPort)) { // 只在目的地机票范围内找
Map<String, Integer> tempMap = map.get(lastPort);
for (Map.Entry<String, Integer> entry : tempMap.entrySet()) {
String nextPort = entry.getKey();
int ticketNum = entry.getValue();
if (ticketNum > 0) {
path.add(nextPort);
tempMap.put(nextPort, ticketNum - 1);
backtracking(path, map, tickets);
path.remove(path.size() - 1);
tempMap.put(nextPort, ticketNum);
}
}
}
}
}
技巧总结
Map map = new TreeMap<>(); 会自动把存入的数据按照键值升序排列。
声明是父类或接口，实现类是具体类。
map的遍历操作。
题目二描述
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
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
解题思路
按照每行来做递归，每次放置判断有效性，到第n行获得结果。
注意判断有效性可以优化。
代码实现
方法一：
class Solution {
List<List<String>> res = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
char[][] array = new char[n][n];
for (char[] a : array) {
Arrays.fill(a, '.');
}
backtracking(array, n, 0);
return res;
}
private void backtracking(char[][] array, int n, int layerNum) {
if (layerNum == n) {
List<String> tempRes = new ArrayList<>();
for (char[] a : array) {
tempRes.add(new String(a));
}
res.add(tempRes);
}
for (int i = 0; i < n; i++) {
if (check(array, layerNum, i, n)) {
array[layerNum][i] = 'Q';
backtracking(array, n, layerNum + 1);
array[layerNum][i] = '.';
}
}
}
private boolean check(char[][] array, int row, int col, int n) {
// 列合法
for (int i = 0; i < n; i++) {
if (i != row && array[i][col] == 'Q') {
return false;
}
}
// 左下到右上合法
int sum = col + row;
for (int i = 0; i < n; i++) {
if (i != row && sum - i >= 0 && sum - i < n && array[i][sum - i] == 'Q') {
return false;
}
}
// 左上到右下合法
int sub = col - row;
for (int i = 0; i < n; i++) {
if (i != row && sub + i >= 0 && sub + i < n && array[i][sub + i] == 'Q') {
return false;
}
}
return true;
}
}
方法二：
class Solution {
List<List<String>> res = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
char[][] array = new char[n][n];
for (char[] a : array) {
Arrays.fill(a, '.');
}
backtracking(array, n, 0);
return res;
}
private void backtracking(char[][] array, int n, int layerNum) {
if (layerNum == n) {
List<String> tempRes = new ArrayList<>();
for (char[] a : array) {
tempRes.add(new String(a));
}
res.add(tempRes);
}
for (int col = 0; col < n; col++) {
if (check(array, layerNum, col, n)) {
array[layerNum][col] = 'Q';
backtracking(array, n, layerNum + 1);
array[layerNum][col] = '.';
}
}
}
private boolean check(char[][] array, int row, int col, int n) {
// 列合法
for (int i = 0; i < row; i++) { // 检查到本行的上一行即可
if (array[i][col] == 'Q') {
return false;
}
}
// 右上合法即可，左下一定没有放Q
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (array[i][j] == 'Q') {
return false;
}
}
// 左上合法即可，右下一定没有Q
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (array[i][j] == 'Q') {
return false;
}
}
return true;
}
}
技巧总结
用char[][]比String[][]好
new String()可以接受一个字符数组，直接转换成为一个字符串。
题目三描述
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
数字 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] 是一位数字或者 '.'
题目数据 保证 输入数独仅有一个解
解题思路
回溯深搜即可。
检查小九宫格时先除3再乘3，这里其实做了取整操作。
也可以不用findNext，直接三层for循环，遇到是点的就跳过。
代码实现
方法一：
class Solution {
public void solveSudoku(char[][] board) {
backtracking(board, 0, 0);
}
private boolean backtracking(char[][] board, int lastI, int lastJ) {
int[] cur = findNext(board, lastI, lastJ);
if (cur[0] == -1 && cur[1] == -1) {
return true;
}
for (int num = 1; num <= 9; num++) {
char numChar = (char) (num + '0');
if (check(board, cur, numChar)) {
board[cur[0]][cur[1]] = numChar;
if (backtracking(board, cur[0], cur[1]))
return true;
board[cur[0]][cur[1]] = '.';
}
}
return false;
}
private int[] findNext(char[][] board, int lastI, int lastJ) {
for (int i = lastI; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.')
return new int[] { i, j };
}
}
return new int[] { -1, -1 };
}
private boolean check(char[][] board, int[] cur, char numChar) {
// 检查行
for (int j = 0; j < 9; j++) {
if (board[cur[0]][j] == numChar) {
return false;
}
}
// 检查列
for (int i = 0; i < 9; i++) {
if (board[i][cur[1]] == numChar) {
return false;
}
}
// 检查九宫格
for (int i = cur[0] / 3 * 3; i < cur[0] / 3 * 3 + 3; i++) {
for (int j = cur[1] / 3 * 3; j < cur[1] / 3 * 3 + 3; j++) {
if (board[i][j] == numChar) {
return false;
}
}
}
return true;
}
}
方法二：
class Solution {
public void solveSudoku(char[][] board) {
backtracking(board);
}
private boolean backtracking(char[][] board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.')
continue;
for (int num = 1; num <= 9; num++) {
char numChar = (char) (num + '0');
if (check(board, new int[] { i, j }, numChar)) {
board[i][j] = numChar;
if (backtracking(board))
return true;
board[i][j] = '.';
}
}
return false;
}
}
return true;
}
private boolean check(char[][] board, int[] cur, char numChar) {
// 检查行
for (int j = 0; j < 9; j++) {
if (board[cur[0]][j] == numChar) {
return false;
}
}
// 检查列
for (int i = 0; i < 9; i++) {
if (board[i][cur[1]] == numChar) {
return false;
}
}
// 检查九宫格
for (int i = cur[0] / 3 * 3; i < cur[0] / 3 * 3 + 3; i++) {
for (int j = cur[1] / 3 * 3; j < cur[1] / 3 * 3 + 3; j++) {
if (board[i][j] == numChar) {
return false;
}
}
}
return true;
}
}
技巧总结
数字转字符型：char numChar = (char) (num + '0');
