目录
题目概述(中等难度)
思路与代码
思路展现
代码示例
题目概述(中等难度)
题目链接:
点我进入链接
思路与代码
思路展现
这道题目就是经典的回溯+DFS(深度优先搜索遍历),在这里我就不再给出我关于回溯的讲解了,leetcode的大佬已经帮我们总结到位了,只需要跟着他的题解走即可,在这里宣传以下weiwei大佬是一位非常厉害的大佬,除了他自己写的题解意外,也开设了自己的github网站帮助大家学习算法,在这里我都会将其网站贴到下面:
全排列weiwei大佬题解链接
weiwei大佬github链接
同时关于全排列这道题目大家如果觉得直接看题解上手比较有难度的话,推荐大家可以直接看下面的一个B站up主来带大家入门:
点我进入B站
顺带介绍以下回溯三部曲:
同时关于什么是DFS和BFS我也给出大家一个链接:
点我来看BFS和DFS
代码示例
class Solution { public List<List<Integer>> permute(int[] nums) { //len代表数组的长度 int len = nums.length; //path是一个双端队列,设置成这个的原因是Java官方Stack类的建议 Deque<Integer> path = new LinkedList<>(); //设置我们的res List<List<Integer>> res = new ArrayList<>(); //设置我们所给定的nums数组中每个元素的初始状态为false boolean[] used = new boolean[len]; if(len == 0) { return res; } dfs(path,used,nums,res,0,len); return res; } /* dfs方法参数介绍: path表示双端队列,用于存储我们所选择的路径上的数字 boolean数组用于表示数字的选择与被选择,被选择为true,没有为false res用于存储最后的返回结果 我们递归结束的条件与我们nums数组的长度len以及二叉树深度depth有很大的关系 */ public void dfs(Deque<Integer> path , boolean[] used , int[] nums , List<List<Integer>> res , int depth , int len) { if(depth == len) { //注意这里的写法其实是一个简便写法,就是直接实例化一个list集合然后将双端队列参数直接传入进去 res.add(new ArrayList<>(path)); //声明我们的递归终止条件 return; } //!used[i]就表示此时假设这个数字还没有被选中,它的反就一定为true,然后才能进入到下面的语句 for(int i = 0 ; i < len ; i++) { if(!used[i]) { //选中后将数字加入到path中 path.addLast(nums[i]); //选中后将状态置为true used[i] = true; //上面我们选择元素完毕后就开始我们的递归 dfs(path,used,nums,res,depth + 1,len); //进行完递归操作后接下来就需要我们进行撤回操作 //1:撤回操作的第一步是将状态置为false used[i] = false; //2:撤回操作的第二步是将数字从path中移除 path.removeLast(); } } } }
注意:
写成res.add(new ArrayList<>(path))的原因是当我们写成res.add(path)的时候,因为path每次都会更改,所以如果只写一个path的话相当于只有一个符合条件的全排列会被放到res当中去,而当我们写new ArrayList<>(path)的时候,相当于每次都会在堆上开辟一个空间去存储我们符合条件的全排列,所以最终结果是res会存储我们所有符合条件的全排列.