2024年7月27日
题46. 全排列
继续回溯。
class Solution {
List<List<Integer>> res;
List<Integer> path;
int[] used;
int[] nums;
public List<List<Integer>> permute(int[] nums) {
//用一个used存
//0表示还没有用,1表示用了
res = new ArrayList<>();
path = new LinkedList<>();
this.nums = nums;
used = new int[nums.length];
backTracking(0);
return res;
}
//index表示用了几个了
public void backTracking(int index){
if(index==nums.length){
res.add(new ArrayList<>(path));
}else{
for(int i=0;i<nums.length;i++){
if(used[i]==1){
continue;
}else{
used[i]=1;
path.add(nums[i]);
backTracking(index+1);
used[i]=0;
path.removeLast();
}
}
}
}
}
题47. 全排列 II
继续使用简单包含方法判断去重,不过根据结果来看效率非常低效,后续需要学习一下标准做法。
凡是涉及重复元素的都要首先排序
class Solution {
List<List<Integer>> res;
List<Integer> path;
int[] used;
int[] nums;
public List<List<Integer>> permuteUnique(int[] nums) {
//用一个used存
//0表示还没有用,1表示用了
Arrays.sort(nums);
res = new ArrayList<>();
path = new LinkedList<>();
this.nums = nums;
used = new int[nums.length];
backTracking(0);
return res;
}
//index表示用了几个了
public void backTracking(int index){
if(index==nums.length){
if(!res.contains(new ArrayList<>(path))){
res.add(new ArrayList<>(path));
}
}else{
for(int i=0;i<nums.length;i++){
if(used[i]==1){
continue;
}else{
used[i]=1;
path.add(nums[i]);
backTracking(index+1);
used[i]=0;
path.removeLast();
}
}
}
}
}
题51. N 皇后
重点是想明白怎么判断每条直线是否被占用。
class Solution {
int[][] arr;
List<List<String>> res = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
arr = new int[n][n];
//第一个旗子只能在第一行
for(int j=0;j<n;j++){
arr[0][j] = 1;
digui(1,n);
arr[0][j] = 0;
}
return res;
}
public void digui(int index, int n){
if(index==n){
res.add(getList(n));
return;
}
for(int j=0;j<n;j++){
arr[index][j] = 1;
if(!check(n)){
arr[index][j] = 0;
}else{
digui(index+1,n);
arr[index][j] = 0;
}
}
}
public boolean check(int n){
//行一样
//列一样
//行列和一样
//行列差一样
int[][] bei = new int[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(arr[i][j]==1){
if(bei[i][j]==1){
return false;
}
//开始把线上的赋1
for(int p=0;p<n;p++){
bei[p][j] = 1;
}
for(int q=0;q<n;q++){
bei[i][q] = 1;
}
//把斜线赋1
int p=i,q=j;
while(p>=0&&q>=0){
bei[p][q]=1;
p-=1;
q-=1;
}
p=i;q=j;
while(p>=0&&q<n){
bei[p][q]=1;
p-=1;
q+=1;
}
p=i;q=j;
while(p<n&&q>=0){
bei[p][q]=1;
p+=1;
q-=1;
}
p=i;q=j;
while(p<n&&q<n){
bei[p][q]=1;
p+=1;
q+=1;
}
}
}
}
return true;
}
public List<String> getList(int n){
List<String> res1 = new ArrayList<>();
for(int i=0;i<n;i++){
String s = "";
for(int j=0;j<n;j++){
if(arr[i][j]==1){
s+="Q";
}else{
s+=".";
}
}
res1.add(s);
}
return res1;
}
}
标签:25,nums,int,res,ArrayList,随想录,回溯,new,List
From: https://www.cnblogs.com/hailicy/p/18328275