首页 > 编程语言 >代码随想录算法训练营第25天 | 回溯问题完结

代码随想录算法训练营第25天 | 回溯问题完结

时间:2024-07-28 15:30:16浏览次数:15  
标签:25 nums int res ArrayList 随想录 回溯 new List

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

相关文章

  • 代码随想录算法训练营第50天 | 单调栈01
    代码随想录算法训练营第天|739.每日温度https://leetcode.cn/problems/daily-temperatures/description/代码随想录https://programmercarl.com/0739.每日温度.html#其他语言版本496.下一个更大元素Ihttps://leetcode.cn/problems/next-greater-element-i/description/......
  • 代码随想录算法训练营第49天 | 动态规划总结
    代码随想录算法训练营第天|647.回文子串https://leetcode.cn/problems/palindromic-substrings/description/代码随想录https://programmercarl.com/0647.回文子串.html#思路516.最长回文子序列https://leetcode.cn/problems/longest-palindromic-subsequence/代码随想录......
  • Midjourney提示词-动物系列-25
    ThroughhighdefinitionCG,Thenine-tailedfoxisananimalinChinesefairytales.Ithasninebeautifultails.Ithasafairytalebackground,portrait,bigeyes,smile,peachblossom,stream,charming,immortal,fluffy,shinymane,ptals,fairytales,il......
  • 代码随想录二刷——数组
     ......
  • P5825 排列计数 加强版
    加强版和原题不同之处在于\(p\)不再是一个排列,而是一个普通的值域为\([1,n]\)的数组考虑将\([p_i<p_{i+1}]\)转化为\(1-[p_i\gep_{i+1}]\),方便计算后面的\(g\),也就是恰好\(n-k-1\)不上升点的方案数记一段不上升点的连续段为非升段,\(f_i\)表示恰好\(i\)个不上升......
  • 【免费领源码】Java/Mysql数据库+SSM校园兼职网站 25557,计算机毕业设计项目推荐上万套
    摘 要当今人类社会已经进入信息全球化和全球信息化、网络化的高速发展阶段。丰富的网络信息已经成为人们工作、生活、学习中不可缺少的一部分。人们正在逐步适应和习惯于网上贸易、网上购物、网上支付、网上服务和网上娱乐等活动,人类的许多社会活动正在向网络化发展。兼职......
  • 【免费领源码】Java/Mysql数据库+springboot驾校预约管理系统 25540,计算机毕业设计项
    摘 要随着科学技术的飞速发展,各行各业都在努力与现代先进技术接轨,通过科技手段提高自身的优势;对于驾校预约管理系统当然也不能排除在外,随着网络技术的不断成熟,带动了驾校预约管理系统,它彻底改变了过去传统的管理方式,不仅使服务管理难度变低了,还提升了管理的灵活性。这种......
  • 《昇思25天学习打卡营第7天|函数式自动微分》
    函数式自动微分神经网络的训练主要使用反向传播算法,模型预测值(logits)与正确标签(label)送入损失函数(lossfunction)获得loss,然后进行反向传播计算,求得梯度(gradients),最终更新至模型参数(parameters)。自动微分能够计算可导函数在某点处的导数值,是反向传播算法的一般化。自动微分......
  • 《昇思25天学习打卡营第5天|数据变换 Transforms》
    数据变换Transforms通常情况下,直接加载的原始数据并不能直接送入神经网络进行训练,此时我们需要对其进行数据预处理。MindSpore提供不同种类的数据变换(Transforms),配合数据处理Pipeline来实现数据预处理。所有的Transforms均可通过map方法传入,实现对指定数据列的处理......
  • 代码随想录算法训练营day25:回溯04:491.递增子序列;46.全排列
    491.递增子序列力扣题目链接(opensnewwindow)给定一个整型数组,你的任务是找到所有该数组的递增子序列,递增子序列的长度至少是2。示例:输入:[4,6,7,7]输出:[[4,6],[4,7],[4,6,7],[4,6,7,7],[6,7],[6,7,7],[7,7],[4,7,7]]说明:给定数组的长度不......