宁波 住房和建设局网站,浙江建设职业技术学院oa网站,新泰网页定制,大门户wordpress主题大家好#xff0c;我是晴天学长#xff0c;排列型的回溯#xff0c;需要的小伙伴可以关注支持一下哦#xff01;后续会继续更新的。#x1f4aa;#x1f4aa;#x1f4aa; 1) .全排列 给定一个不含重复数字的数组 nums #xff0c;返回其 所有可能的全排列 。你可以 按…大家好我是晴天学长排列型的回溯需要的小伙伴可以关注支持一下哦后续会继续更新的。 1) .全排列 给定一个不含重复数字的数组 nums 返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1
输入nums [1,2,3] 输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 示例 2
输入nums [0,1] 输出[[0,1],[1,0]] 示例 3
输入nums [1] 输出[[1]]
提示
1 nums.length 6 -10 nums[i] 10 nums 中的所有整数 互不相同 2) .算法思路
全排列 1.建立boolean数组去标记 2.用合适的数组去存答案 3.注意回溯的时候参数是否变回了以前的样子。 3) .算法步骤
1.创建一个整数数组nums作为全排列的输入。 2.创建一个二维列表ans用于存储所有的全排列结果。 3.创建一个列表path用于存储当前的排列路径。 4.调用permute方法将nums作为参数传入。 5.在permute方法中创建一个布尔数组st用于标记数组nums中的元素是否已经被访问过。 6.初始化路径列表path为空。 7.调用dfs方法传入初始长度0、布尔数组st和路径列表path。 8.在dfs方法中判断如果当前路径的长度等于数组nums的长度即已经找到了一个全排列 a. 将当前路径path的副本添加到结果列表ans中。 b. 返回。 遍历数组nums的每个元素 a. 如果当前元素未被访问 1将当前元素添加到路径列表path中。 2将当前元素标记为已访问。 3递归调用dfs方法传入长度加1、更新后的布尔数组st和路径列表path。 4将当前元素标记为未访问以便后续的回溯。 5从路径列表path中移除最后一个元素恢复路径状态。 c.返回最终的结果列表ans。 4.代码示例
class Solution {private int[] nums;//方便插入ListListInteger ans new LinkedList();ListInteger path;public ListListInteger permute(int[] nums) {this.nums nums;//替换成全局变量。这个类中。boolean[] st new boolean[nums.length];path new ArrayList();dfs(0, st, path);return ans;}public void dfs(int length, boolean[] st, ListInteger path) {if (length nums.length) {ans.add(new ArrayList(path));return;}for (int i 0; i nums.length; i) {if (!st[i]) {path.add(nums[i]);st[i] true;dfs(length 1, st, path);st[i]false;path.remove(path.size()-1);}}}}5.总结
正确的排列回溯。 试题链接
