代码随想录算法训练营第28天
今日任务
● 491.递增子序列 ● 46.全排列 ● 47.全排列 II
● 332.重新安排行程 ● 51. N皇后 ● 37. 解数独 ● 总结
链接：https://docs.qq.com/doc/DUHZYbWhwSHRCRmp3 (opens in a new tab)
链接：https://docs.qq.com/doc/DUEdTVVhxbnJiY3BR (opens in a new tab)
491.递增子序列
自己想法
保证递增的判断只需判断1轮（代码15行），即在进入递归for之前，比较start到end的数是否大于等于path里最后一个数，否则标记，以便跳过。
保证没有重复的判断需要判断多轮，即在递归for之内，把当前后面和nums[i]相等的数都标记，以便跳过。
这样block就可以同时保证递增和去重，在递归for开头判断block[i]是否为true，为true则跳过。
需要注意，block的作用域是单个递归（函数）过程，而非全局生效。也就是去重和递增的判断限制在同一树层，而不是整个树。
class Solution {
public List<List<Integer>> ans = new ArrayList<>();
public List<Integer> path = new ArrayList<>();
public List<List<Integer>> findSubsequences(int[] nums) {
backtrack(nums, 0, nums.length);
return ans;
}
public void backtrack(int[] nums, int start, int end) {
if(path.size() >= 2) ans.add(new ArrayList<>(path));
if(start == end) return;
else {
boolean[] block = new boolean[nums.length];
// 保证递增
for(int j = start; j < end; j++) if(path.size() > 0 && nums[j] < path.get(path.size() - 1)) block[j] = true;
for(int i = start; i < end; i++) {
// 利用block同时保证不重复且递增
while(i < end && block[i]) i++;
if(i < end) {
path.add(nums[i]);
backtrack(nums, i + 1, end);
path.remove(path.size() - 1);
// 去重
for(int j = i + 1; j < end; j++) if(nums[j] == nums[i]) block[j] = true;
}
}
}
}
}46.全排列
自己想法
class Solution {
List<List<Integer>> ans = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> permute(int[] nums) {
boolean[] used = new boolean[nums.length];
backtrack(nums, used);
return ans;
}
public void backtrack(int[] nums, boolean[] used) {
if(path.size() == nums.length) ans.add(new ArrayList<>(path));
else {
for(int i = 0; i < nums.length; i++) {
// 没用过的数才能用
while(i < nums.length && used[i]) i++;
if(i < nums.length) {
path.add(nums[i]);
used[i] = true;
backtrack(nums, used);
path.removeLast();
used[i] = false;
}
}
}
}
}47.全排列 II
自己想法
我这里又用了一个block数组来去重。
不过这个题也可以用排序的方法来去重，类似40.组合总和II (opens in a new tab)
class Solution {
List<List<Integer>> ans = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
boolean[] used = new boolean[nums.length];
backtrack(nums, used);
return ans;
}
public void backtrack(int[] nums, boolean[] used) {
if(path.size() == nums.length) ans.add(new ArrayList<>(path));
else {
boolean[] block = new boolean[nums.length];
for(int i = 0; i < nums.length; i++) {
// 没用过且不重复（while条件是反过来写的：用过或重复）
while(i < nums.length && (used[i] || block[i])) i++;
if(i < nums.length) {
path.add(nums[i]);
used[i] = true;
backtrack(nums, used);
path.removeLast();
used[i] = false;
// 去重
for(int j = 0; j < nums.length; j++) if(nums[i] == nums[j]) block[j] = true;
}
}
}
}
}332.重新安排行程
自己想法
开始自己写没剪枝，会超时。稍微改了改不超时了，但还是比较慢（78ms，打败5%）
class Solution {
public List<String> ans = new ArrayList<>();
public List<String> path = new ArrayList<>();
public List<String> findItinerary(List<List<String>> tickets) {
// trick1：用于剪枝，保证第一个找到的就是字典序最小
Collections.sort(tickets, (a, b) -> a.get(1).compareTo(b.get(1)));
boolean[] used = new boolean[tickets.size()];
path.add("JFK");
solve(tickets, used, "JFK");
return ans;
}
public void solve(List<List<String>> tickets, boolean[] used, String nowAt) {
if(path.size() == tickets.size() + 1) ans = new ArrayList<>(path);
else {
// trick2：用于剪枝，跳过重复票
boolean[] block = new boolean[tickets.size()];
for(int i = 0; i < tickets.size(); i++) {
// 没用过且票不重复且出发地是nowAt（while条件是用过或重复或不在nowAt）
while(i < tickets.size() && (used[i] || block[i] || !nowAt.equals(tickets.get(i).get(0)))) i++;
if(i < tickets.size()) {
path.add(tickets.get(i).get(1));
used[i] = true;
if(ans.size() == 0) solve(tickets, used, tickets.get(i).get(1));
path.remove(path.size() - 1);
used[i] = false;
for(int j = i + 1; j < tickets.size(); j++)
if(tickets.get(j).get(0).equals(tickets.get(i).get(0)) &&
tickets.get(j).get(1).equals(tickets.get(i).get(1))) block[j] = true;
}
}
}
}
}51. N皇后
自己想法
纯暴力，不剪枝，一个格子一个格子地试，178ms
class Solution {
public List<List<String>> ans = new ArrayList<>();
public boolean[][] one_ans;
public List<List<String>> solveNQueens(int n) {
one_ans = new boolean[n][n];
backtrack(0, n, 0);
return ans;
}
/* placed: 已经放置的棋子数
n: n
coordinate: 当前待测试的第一个位置，其范围为[0, n*n)
*/
public void backtrack(int placed, int n, int coordinate) {
if(placed == n) ans.add(queenArray2list(one_ans));
else {
for(int i = coordinate; i < n * n; i++) {
if(canPlace(n, i)) {
one_ans[i / n][i % n] = true;
backtrack(placed + 1, n, i + 1);
one_ans[i / n][i % n] = false;
}
}
}
}
public List<String> queenArray2list(boolean[][] array) {
List<String> resu = new ArrayList<>();
for(int i = 0; i < array.length; i++) {
StringBuilder strBuilder = new StringBuilder("");
for(int j = 0; j < array[i].length; j++) {
if(array[i][j]) {
strBuilder.append('Q');
// array[i][j] = 0;
}
else strBuilder.append('.');
}
resu.add(strBuilder.toString());
}
return resu;
}
public boolean canPlace(int n, int coordinate) {
int x = coordinate / n;
int y = coordinate % n;
// 同行
for(int i = 0; i < n; i++) if(i != y && one_ans[x][i]) return false;
// 同列
for(int i = 0; i < n; i++) if(i != x && one_ans[i][y]) return false;
// 斜线
// 遍历右上角到左下角的斜线
for (int i = 0; i < n; i++) {
int j = x + y - i;
if (j != y && j >= 0 && j < n && one_ans[i][j]) return false;
}
// 遍历左上角到右下角的斜线
for (int i = 0; i < n; i++) {
int j = y - x + i;
if (j != y && j >= 0 && j < n && one_ans[i][j]) return false;
}
return true;
}
}剪枝：一行只能放一个，那么backtrack直接跳到下一行。3ms
class Solution {
public List<List<String>> ans = new ArrayList<>();
public boolean[][] one_ans;
public List<List<String>> solveNQueens(int n) {
one_ans = new boolean[n][n];
backtrack(n, 0);
return ans;
}
/* n: n
row: 当前测试的行
*/
public void backtrack(int n, int row) {
if(row == n) ans.add(queenArray2list(one_ans));
else {
// 测试列
for(int i = 0; i < n; i++) {
if(canPlace(n, row, i)) {
one_ans[row][i] = true;
backtrack(n, row + 1);
one_ans[row][i] = false;
}
}
}
}
public List<String> queenArray2list(boolean[][] array) {
List<String> resu = new ArrayList<>();
for(int i = 0; i < array.length; i++) {
StringBuilder strBuilder = new StringBuilder("");
for(int j = 0; j < array[i].length; j++) {
if(array[i][j]) {
strBuilder.append('Q');
// array[i][j] = 0;
}
else strBuilder.append('.');
}
resu.add(strBuilder.toString());
}
return resu;
}
public boolean canPlace(int n, int x, int y) {
// 同列
for(int i = 0; i < n; i++) if(i != x && one_ans[i][y]) return false;
// 斜线
for (int i = 0; i < n; i++) {
int j = x + y - i;
if (j != y && j >= 0 && j < n && one_ans[i][j]) return false;
}
for (int i = 0; i < n; i++) {
int j = y - x + i;
if (j != y && j >= 0 && j < n && one_ans[i][j]) return false;
}
return true;
}
}37. 解数独
自己想法
class Solution {
public void solveSudoku(char[][] board) {
backtrack(board);
}
public boolean backtrack(char[][] board) {
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
// 跳过有数的地方
if(board[i][j] != '.') continue;
for(int k = 1; k <= 9; k++) {
if(sudokuCheck(i, j, k, board)) {
board[i][j] = (char) ('0' + k);
if(backtrack(board)) return true;
board[i][j] = '.';
}
}
// 试了9个数都不行说明当前尝试已经导致没有解了，无需继续尝试，应该返回上一层
return false;
}
}
return true;
}
public boolean sudokuCheck(int row, int col, int try_num, char[][] board) {
// 行
for(int i = 0; i < 9; i++) if(board[row][i] - '0' == try_num) return false;
// 列
for(int j = 0; j < 9; j++) if(board[j][col] - '0' == try_num) 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] - '0' == try_num) return false;
}
}
return true;
}
}