力扣爆刷第125天之回溯五连刷(全排列、N皇后、数独)
文章目录
- 力扣爆刷第125天之回溯五连刷(全排列、N皇后、数独)
- 一、46. 全排列
- 二、7. 全排列 II
- 三、332. 重新安排行程
- 四、51. N 皇后
- 五、37. 解数独
一、46. 全排列
题目链接:https://leetcode.cn/problems/permutations/description/
思路:求全排列,元素无重,所以递归不需要起始索引,但是需要纵向去重,纵向去重使用flag数组,纵向标记去重,横向不影响。
class Solution {
List<List<Integer>> resList = new ArrayList<>();
List<Integer> list = new ArrayList<>();
boolean[] flag;
public List<List<Integer>> permute(int[] nums) {
flag = new boolean[nums.length];
backTracking(nums);
return resList;
}
void backTracking(int[] nums) {
if(list.size() == nums.length) {
resList.add(new ArrayList(list));
return;
}
for(int i = 0; i < nums.length; i++) {
if(flag[i]) continue;
flag[i] = true;
list.add(nums[i]);
backTracking(nums);
flag[i] = false;
list.remove(list.size()-1);
}
}
}
二、7. 全排列 II
题目链接:https://leetcode.cn/problems/permutations-ii/description/
思路:本题求全排列,集合元素有重复,所以不仅要纵向去重,也需要横向去重,纵向去重需要使用used数组,纵向标记,递归返回时清楚,不影响横向,横向去重需要排序,让相同元素挨在一起,而且横向是递归返回之后的for横向遍历,所以前一个位置得是false,才行。
class Solution {
List<List<Integer>> resList = new ArrayList<>();
List<Integer> list = new ArrayList<>();
boolean[] flag;
public List<List<Integer>> permuteUnique(int[] nums) {
flag = new boolean[nums.length];
Arrays.sort(nums);
backTracking(nums);
return resList;
}
void backTracking(int[] nums) {
if(list.size() == nums.length) {
resList.add(new ArrayList(list));
return ;
}
for(int i = 0; i < nums.length; i++) {
if(flag[i] || (i > 0 && nums[i] == nums[i-1]) && !flag[i-1]) continue;
flag[i] = true;
list.add(nums[i]);
backTracking(nums);
flag[i] = false;
list.remove(list.size()-1);
}
}
}
三、332. 重新安排行程
题目链接:https://leetcode.cn/problems/reconstruct-itinerary/description/
思路:类似于有向图记录特定路线,而且有多个选择时要求按照字母排序,此时可以利用优先级队列,构建map集合,然后后序收集元素即可。
class Solution {
List<String> list = new ArrayList<>();
Map<String, PriorityQueue<String>> map = new HashMap<>();
public List<String> findItinerary(List<List<String>> tickets) {
for(List<String> nums : tickets) {
String from = nums.get(0);
String to = nums.get(1);
if(!map.containsKey(from)) {
map.put(from, new PriorityQueue());
}
map.get(from).add(to);
}
dfs("JFK");
Collections.reverse(list);
return list;
}
void dfs(String from) {
while(map.containsKey(from) && map.get(from).size() > 0) {
dfs(map.get(from).poll());
}
list.add(from);
}
}
四、51. N 皇后
题目链接:https://leetcode.cn/problems/n-queens/description/
思路:N皇后就是简单的排列回溯,只需要正常递归,然后再每一个点进行是否符合条件的判断即可,由于是递归,所以判断时只需要判断45度和135度和竖直向上的方向。
class Solution {
List<List<String>> resList = new ArrayList<>();
char[][] source;
public List<List<String>> solveNQueens(int n) {
source = new char[n][n];
for(char[] cc : source) {
Arrays.fill(cc, '.');
}
backTracking(n, 0);
return resList;
}
void backTracking(int n, int row) {
if(row == n) {
List<String> list = new ArrayList<>();
for(char[] cList : source) {
list.add(new String(cList));
}
resList.add(list);
return;
}
for(int col = 0; col < n; col++) {
if(isTrue(row, col, n)) {
source[row][col] = 'Q';
backTracking(n, row+1);
source[row][col] = '.';
}
}
}
boolean isTrue(int x, int y, int n) {
for(int i = x; i >= 0; i--) {
if(source[i][y] == 'Q') return false;
}
for(int i = x, j = y; i >= 0 && j >= 0; i--, j--) {
if(source[i][j] == 'Q') return false;
}
for(int i = x, j = y; i >= 0 && j < n; i--, j++) {
if(source[i][j] == 'Q') return false;
}
return true;
}
}
五、37. 解数独
题目链接:https://leetcode.cn/problems/sudoku-solver/description/
思路:本题也是排序的回溯题,排序不需要指定for循环的起始位置,唯一与回溯模板不同之处在于值的选择,需要逐个判断是否未出现过,未出现过才可以赋值并且递归。
class Solution {
public void solveSudoku(char[][] board) {
backTracking(board);
}
boolean backTracking(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(!isTrue(board, i, j, k)) continue;
board[i][j] = k;
if(backTracking(board)) return true;
board[i][j] = '.';
}
return false;
}
}
return true;
}
boolean isTrue(char[][] board, int x, int y, char k) {
for(int i = 0; i < 9; i++) {
if(board[x][i] == k || board[i][y] == k) return false;
}
int row = x / 3, col = y / 3;
row *= 3;
col *= 3;
for(int i = row; i < row + 3; i++) {
for(int j = col; j < col + 3; j++) {
if(board[i][j] == k) return false;
}
}
return true;
}
}