代码随想录二刷day30

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

---

一、力扣332. 重新安排行程

class Solution {private LinkedList<String> res;private LinkedList<String> path = new LinkedList<>();public List<String> findItinerary(List<List<String>> tickets) {Collections.sort(tickets, (a, b) -> a.get(1).compareTo(b.get(1)));path.add("JFK");boolean[] used = new boolean[tickets.size()];backTracking((ArrayList) tickets, used);return res;}public boolean backTracking(ArrayList<List<String>> tickets, boolean[] used) {if (path.size() == tickets.size() + 1) {res = new LinkedList(path);return true;}for (int i = 0; i < tickets.size(); i++) {if (!used[i] && tickets.get(i).get(0).equals(path.getLast())) {path.add(tickets.get(i).get(1));used[i] = true;if (backTracking(tickets, used)) {return true;}used[i] = false;path.removeLast();}}return false;}
}

二、力扣51. N 皇后

class Solution {List<List<String>> res = new ArrayList<>();public List<List<String>> solveNQueens(int n) {char[][] ch = new char[n][n];for(char[] c:ch){Arrays.fill(c, '.');}fun(0, n, ch);return res;}public void fun(int row, int n, char[][] ch){if(row == n){res.add(new ArrayList<>(temp(ch)));return;}for(int col = 0; col < n; col ++){if(flag(ch, row, col, n)){ch[row][col] = 'Q';fun(row +1, n, ch);ch[row][col] = '.';}}}public List<String> temp(char[][] ch){List<String> li = new ArrayList<>();for(char[] c: ch){li.add(String.copyValueOf(c));}return li;}public boolean flag(char[][] ch, int row, int col, int n){//判断行for(int i = 0; i < col; i ++){if(ch[row][i] == 'Q'){return false;}}//判断列for(int i = 0; i < row; i ++){if(ch[i][col] == 'Q'){return false;}}//判断°角for(int i = row-1, j = col-1; i >= 0 && j >= 0; i --, j --){if(ch[i][j] == 'Q'){return false;}}//判断135度角for(int i = row-1, j = col+1; i >= 0 && j <= n-1; i--, j ++){if(ch[i][j] == 'Q'){return false;}}return true;}
}

三、力扣37. 解数独

class Solution {public void solveSudoku(char[][] board) {fun(board);}public boolean fun(char[][] board){for(int i = 0; i < 9; i ++){for(int j = 0; j < 9; j ++){if(board[i][j] != '.'){continue;}for(char k = '1'; k <= '9'; k ++){if(flag(board, i, j, k)){board[i][j] = k;if(fun(board)){return true;}board[i][j] = '.';}}return false;}}return true;}public boolean flag(char[][] board, int row, int col, char k){//判断行for(int i = 0; i < 9; i ++){if(board[row][i] == k){return false;}}//判断列for(int i = 0; i < 9; i ++){if(board[i][col] == k){return false;}}//判断9宫格int a = (row/3)*3;int b = (col/3)*3;for(int i = a; i < a + 3; i ++){for(int j = b; j < b + 3; j ++){if(board[i][j] == k){return false;}}}return true;}
}```