返回顶部
首页 > 资讯 > 后端开发 > Python >Java回溯法解决全排列问题流程详解
  • 840
分享到

Java回溯法解决全排列问题流程详解

2024-04-02 19:04:59 840人浏览 安东尼

Python 官方文档:入门教程 => 点击学习

摘要

题目描述: 给定一不重复的数组,返回其具有的所有全排列(使用 List<List > 返回) 思路: 以数组 nums = [1, 2, 3] 为例,其具有的解空间可以用

题目描述:

给定一不重复的数组,返回其具有的所有全排列(使用 List<List > 返回)

思路:

以数组 nums = [1, 2, 3] 为例,其具有的解空间可以用这样一棵树表示,相比看到这里大家就可以知道,这是一道可以用 回溯法 解决的题。

难点:如何保证不选到已经使用过的数组元素 —— 使用 used[] 数组标记该元素是否被使用过

细节请看代码注释

    // 用于存储结果的数组
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    public List<List<Integer>> permute(int[] nums) {
        List<Integer> list = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        backTrack(nums, list, used);
        return ans;
    }
    // 回溯法参数: nums为待排列数组, list存储当前排列结果, used[]标记当前元素是否被使用过
    public void backTrack(int[] nums, List<Integer> list, boolean[] used){
        // 回溯法退出条件,list大小为nums[]长度,即所有元素都已加入排列
        if(list.size() == nums.length){
            // 加入结果数组,注意要 new 新的list (List为按指针所指地址存储,不然每次加的都是同一个)
            ans.add(new ArrayList(list));
            return;
        }
        // 循环以每个元素开始排列
        for(int i=0; i<nums.length; i++){
            // 元素未被使用过加入排列
            if(!used[i]){
                // 在排列中加入当前元素,并将used[i]修改为true
                list.add(nums[i]);
                used[i] = true;
                // 递归调用 backTrack
                backTrack(nums, list, used);
                // 回溯,去掉当前元素,并将used置为false
                list.remove(list.size() - 1);
                used[i] = false;
            }
        }
    }

变式一

题目描述:给定一具有重复数字的序列, 返回所有不重复的全排列

示例:

这道题是全排列的变式题, 只需要对全排列写法加入对重复情况去除的判断即可,于是本题的重心转移到了如何判断是否会产生重复序列。

我们可以思考什么情况会产生重复序列, 我们先对 nums[] 按从小到大排序, 限制每次填入的数字都是重复数字的从左到右的第一个数字

class Solution {
    Boolean[] visit;
    List<List<Integer>> ans;
    public List<List<Integer>> permuteUnique(int[] nums) {
        visit = new Boolean[nums.length];
        Arrays.fill(visit, false);
        List<Integer> list = new ArrayList<>();
        ans = new ArrayList<>();
        Arrays.sort(nums);
        backTrack(nums, list);
        return ans;
    }
    public void backTrack(int[] nums, List<Integer> list){
        if(nums.length == list.size()){
            ans.add(new ArrayList(list));
            return;
        }
        for(int i=0; i<nums.length; i++){
            // 当前元素用过 + 限制每轮填入的字符都是重复字符的从左到右的第一个字符
            if(visit[i] || (i > 0 && !visit[i-1] && nums[i] == nums[i-1])){
                continue;
             }
            list.add(nums[i]);
            visit[i] = true;
            backTrack(nums, list);
            visit[i] = false;
            list.remove(list.size() - 1);
        }
    }
}

变式:字符排序

class Solution {
    List<String> ans = new ArrayList<>();
    public String[] permutation(String s) {
        // 思路: 回溯法典型例题 —— 含重复问题
        char[] array = s.toCharArray();
        Arrays.sort(array);
        Boolean[] used = new Boolean[array.length];
        Arrays.fill(used, false);
        backTack(array, used, new StringBuilder());
        String[] res = new String[ans.size()];
        for(int i=0; i<ans.size(); i++){
            res[i] = ans.get(i);
        }
        return res;
    }
    public void backTack(char[] array, Boolean[] used, StringBuilder sb){
        if(array.length == sb.length()){
            ans.add(new String(sb));
        }
        for(int i=0; i<array.length; i++){
           if(used[i]){
               continue;
           }
           if(i>0 && array[i]==array[i-1] && !used[i-1]){
               continue;
           }
            sb.append(array[i]);
            used[i] = true;
            backTack(array, used, sb);
            sb.deleteCharAt(sb.length() - 1);
            used[i] = false;
        }
    }
}

到此这篇关于Java回溯法解决全排列问题流程详解的文章就介绍到这了,更多相关Java回溯法 内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

--结束END--

本文标题: Java回溯法解决全排列问题流程详解

本文链接: https://www.lsjlt.com/news/168833.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

猜你喜欢
  • Java回溯法解决全排列问题流程详解
    题目描述: 给定一不重复的数组,返回其具有的所有全排列(使用 List<List > 返回) 思路: 以数组 nums = [1, 2, 3] 为例,其具有的解空间可以用...
    99+
    2024-04-02
  • C++回溯算法中的全排列问题怎么解决
    本文小编为大家详细介绍“C++回溯算法中的全排列问题怎么解决”,内容详细,步骤清晰,细节处理妥当,希望这篇“C++回溯算法中的全排列问题怎么解决”文章能帮助大家解决疑惑,下面跟着小编的思路慢慢深入,一起来学习新知识吧。一、全排列全排列的特点...
    99+
    2023-07-05
  • C++回溯算法中的全排列问题分析探讨
    目录一、全排列二、全排列II 一、全排列 全排列的特点就是:解放了index(每次遍历都从0开始),但是解放index的同时,又捆绑了used数组,记录已经出现过的元素 class ...
    99+
    2023-03-15
    C++回溯算法全排列 C++回溯算法 C++全排列问题
  • Java基于递归解决全排列问题算法示例
    本文实例讲述了Java基于递归解决全排列问题算法。分享给大家供大家参考,具体如下:排列问题设R={r1,r2,...,rn}是要进行排列的n个元素,Ri=R-{ri}。集合x中元素的全排列记为Perm(X)。(ri)Perm(X)表示在全排...
    99+
    2023-05-30
    java 递归 全排列
  • C++使用回溯法解决黄金矿工问题
    目录题目描述示例解题思路顺心的人大抵一样,坎坷的人各有各的坎坷。也只能坚持自我修行,等待自己的机遇。 题目描述 你要开发一座金矿,地质勘测学家已经探明了这座金矿中的资源分布,并用大小...
    99+
    2024-04-02
  • C++回溯算法中子集问题如何解决
    这篇文章主要介绍了C++回溯算法中子集问题如何解决的相关知识,内容详细易懂,操作简单快捷,具有一定借鉴价值,相信大家阅读完这篇C++回溯算法中子集问题如何解决文章都会有所收获,下面我们一起来看看吧。一、子集子集问题与其它问题最大的不同就是:...
    99+
    2023-07-05
  • C++回溯与分支限界算法分别解决背包问题详解
    目录算法思想回溯代码分支限界代码算法思想 分支限界法与回溯法的求解目标不同。 回溯法的求解目标是找出解空间中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,...
    99+
    2024-04-02
  • SimpleDateFormat线程安全问题排查详解
    目录一. 问题现象二. 原因排查三. 原因分析四. 解决方案一. 问题现象 运营部门反馈使用小程序配置的拉新现金红包活动二维码,在扫码后跳转至404页面。 二. 原因排查 首先,检查...
    99+
    2022-11-13
    SimpleDateFormat线程安全排查 SimpleDateFormat线程安全
  • 怎么使用Java递归回溯解决八皇后的问题
    这篇文章主要介绍“怎么使用Java递归回溯解决八皇后的问题”,在日常操作中,相信很多人在怎么使用Java递归回溯解决八皇后的问题问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”怎么使用Java递归回溯解决八皇后...
    99+
    2023-06-25
  • Java使用递归回溯完美解决八皇后的问题
    八皇后问题 八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即:...
    99+
    2024-04-02
  • C++回溯算法中组合的相关问题怎么解决
    这篇文章主要讲解了“C++回溯算法中组合的相关问题怎么解决”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“C++回溯算法中组合的相关问题怎么解决”吧!回溯算法模板void backtracki...
    99+
    2023-07-05
  • PHP怎么用回溯算法求解子集问题
    本篇内容介绍了“PHP怎么用回溯算法求解子集问题”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!回溯算法实际上一个类似枚举的搜索尝试过程,主要...
    99+
    2023-06-20
  • Java实现全排列的三种算法详解
    目录算法一算法二算法三算法一 基于递归与回溯实现。在排列1,2,3的时候,先由3向上回溯到2发现没有其他可能的情况,再回溯到1,排列为1,3,2再向上回溯到存在其他情况时,即根节点然...
    99+
    2024-04-02
  • Java使用线程同步解决线程安全问题详解
    第一种方法:同步代码块: 作用:把出现线程安全的核心代码上锁 原理:每次只能一个线程进入,执行完毕后自行解锁,其他线程才能进来执行 锁对象要求:理论上,锁对象只要对于当前同时执行的线...
    99+
    2024-04-02
  • C语言回溯法解八皇后问题(八皇后算法)
    八皇后问题(N皇后问题)的回溯法求解 一、问题描述 在一个国际象棋棋盘上放置八个皇后,使得任何两个皇后之间不相互攻击,求出所有的布棋方法,并推广到N皇后情况。 二、参考资料 啥文字都...
    99+
    2024-04-02
  • C语言如何使用回溯法解八皇后问题
    这篇文章给大家分享的是有关C语言如何使用回溯法解八皇后问题的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。八皇后问题(N皇后问题)的回溯法求解一、问题描述在一个国际象棋棋盘上放置八个皇后,使得任何两个皇后之间不相互...
    99+
    2023-06-22
  • Java解决青蛙跳台阶问题流程
    1.问题描述 一只青蛙一次可以跳上1阶台阶,也可以跳上2阶台阶,求该青蛙跳上一个n阶台阶总共有多少种跳法? 2.画图分析  3.问题讲解  一只青蛙,要么1次跳2个台阶,要么1次跳...
    99+
    2024-04-02
  • Java多线程之线程安全问题详解
    目录1. 什么是线程安全和线程不安全?2. 自增运算为什么不是线程安全的?3. 临界区资源和竞态条件总结:面试题: 什么是线程安全和线程不安全?自增运算是不是线程安全的?如何保证多线...
    99+
    2024-04-02
  • 关于java中线程安全问题详解
    目录一、什么时候数据在多线程并发的环境下会存在安全问题?二、怎么解决线程安全问题?三、银行 取钱/存钱 案例为什么会出现线程安全问题四、总结 一、什么时候数据在多线程并发的环境下会存...
    99+
    2024-04-02
  • Java利用跳跃表解决双重队列问题详解
    目录一 问题描述二 输入三 输出四 输入和输出样例五 分析和设计六 代码七 测试一 问题描述 银行的每个客户都有一个正整数标识 K,到银行请求服务时将收到一个正整数的优先级...
    99+
    2022-12-28
    Java跳跃表解决双重队列 Java跳跃表 Java 双重队列
软考高级职称资格查询
编程网,编程工程师的家园,是目前国内优秀的开源技术社区之一,形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容,为IT开发者提供了一个发现、使用、并交流开源技术的平台。
  • 官方手机版

  • 微信公众号

  • 商务合作