全排列题目链接https://leetcode.cn/problems/permutations/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答无分析自己没什么思路。看了官方题解后的解答//只看思路自己编码版 //方法回溯 //时间复杂度O(n*n!) //空间复杂度O(n) ListListInteger ans; public ListListInteger permute(int[] nums) { ans new ArrayList(); int n nums.length; ListInteger output new ArrayList(n); backtrack(nums, output, 0, n); return ans; } //output存储每次排列的结果 //index记录nums数组中还未被使用的第一个元素的下标[0,index-1]为已经被使用过的元素[index,n-1]为还未被使用过的元素 public void backtrack(int[] nums, ListInteger output, int index, int n){ int oLen output.size(); if(n oLen){ ans.add(new ArrayList(output)); return; } for(int iindex; in; i){ output.add(nums[i]); swap(nums, index, i);//将使用过的数据移动至index指向的位置 backtrack(nums, output, index 1, n); //回溯 swap(nums, index, i); output.remove(oLen); } } public void swap(int[] nums, int x, int y){ int temp nums[x]; nums[x] nums[y]; nums[y] temp; } //看了官方解答版 //方法回溯 //时间复杂度O(n*n!) //空间复杂度O(n) public ListListInteger permute(int[] nums) { ListListInteger ans new ArrayList(); ListInteger output new ArrayList(); for(int num : nums){ output.add(num); } int n nums.length; backtrack(output, n, 0, ans); return ans; } //first为output集合中未被使用过的第一个元素的下标 //在output集合中[0,first-1]为已经排列好的元素[first,n-1]为还未被排列的元素 public void backtrack(ListInteger output, int n, int first, ListListInteger ans){ //所有数都填完了 if(first n){ //收集答案 ans.add(new ArrayList(output)); return; } for(int ifirst; in; i){ //动态维护数组 Collections.swap(output, i, first); //继续递归填下一个数 backtrack(output, n, first 1, ans); //撤销操作 Collections.swap(output, i, first); } }分析 1、解题思路通过递归为每个位置填入一个还未被使用过的元素官方题解先将nums数组的数据复制一份到output集合中用变量first维护output集合中还未被排列过的元素即在output集合中[0,first-1]为已经被排列好的元素[first,n-1]为还未被排列的元素。之后只需动态维护output集合并在n个元素全都排列好后收集答案即可。 2、在本次解答中官方题解通过每次排列后将元素位置进行变换并用一个变量first维护第一个未被排列过的元素的位置使得集合中[0,first-1]为已经被排列好的元素[first,n-1]为还未被排列的元素这样生成的全排列并不是按字典序存储在答案数组中的如果题目要求按字典序输出那么则需使用标记数组或者其他方法来维护元素状态。总结本题采用回溯方法解题其中需要注意每次搜集答案时需重新创建一个集合并将得到的排列复制到新建的集合中。本题通过变量first和动态维护数组来区分未被使用过的元素和已经被使用过的元素所以得到的答案不是按字典序存储的如果题目要求按字典序输出那么则需使用标记数组或者其他方法来维护元素状态。
055全排列
全排列题目链接https://leetcode.cn/problems/permutations/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答无分析自己没什么思路。看了官方题解后的解答//只看思路自己编码版 //方法回溯 //时间复杂度O(n*n!) //空间复杂度O(n) ListListInteger ans; public ListListInteger permute(int[] nums) { ans new ArrayList(); int n nums.length; ListInteger output new ArrayList(n); backtrack(nums, output, 0, n); return ans; } //output存储每次排列的结果 //index记录nums数组中还未被使用的第一个元素的下标[0,index-1]为已经被使用过的元素[index,n-1]为还未被使用过的元素 public void backtrack(int[] nums, ListInteger output, int index, int n){ int oLen output.size(); if(n oLen){ ans.add(new ArrayList(output)); return; } for(int iindex; in; i){ output.add(nums[i]); swap(nums, index, i);//将使用过的数据移动至index指向的位置 backtrack(nums, output, index 1, n); //回溯 swap(nums, index, i); output.remove(oLen); } } public void swap(int[] nums, int x, int y){ int temp nums[x]; nums[x] nums[y]; nums[y] temp; } //看了官方解答版 //方法回溯 //时间复杂度O(n*n!) //空间复杂度O(n) public ListListInteger permute(int[] nums) { ListListInteger ans new ArrayList(); ListInteger output new ArrayList(); for(int num : nums){ output.add(num); } int n nums.length; backtrack(output, n, 0, ans); return ans; } //first为output集合中未被使用过的第一个元素的下标 //在output集合中[0,first-1]为已经排列好的元素[first,n-1]为还未被排列的元素 public void backtrack(ListInteger output, int n, int first, ListListInteger ans){ //所有数都填完了 if(first n){ //收集答案 ans.add(new ArrayList(output)); return; } for(int ifirst; in; i){ //动态维护数组 Collections.swap(output, i, first); //继续递归填下一个数 backtrack(output, n, first 1, ans); //撤销操作 Collections.swap(output, i, first); } }分析 1、解题思路通过递归为每个位置填入一个还未被使用过的元素官方题解先将nums数组的数据复制一份到output集合中用变量first维护output集合中还未被排列过的元素即在output集合中[0,first-1]为已经被排列好的元素[first,n-1]为还未被排列的元素。之后只需动态维护output集合并在n个元素全都排列好后收集答案即可。 2、在本次解答中官方题解通过每次排列后将元素位置进行变换并用一个变量first维护第一个未被排列过的元素的位置使得集合中[0,first-1]为已经被排列好的元素[first,n-1]为还未被排列的元素这样生成的全排列并不是按字典序存储在答案数组中的如果题目要求按字典序输出那么则需使用标记数组或者其他方法来维护元素状态。总结本题采用回溯方法解题其中需要注意每次搜集答案时需重新创建一个集合并将得到的排列复制到新建的集合中。本题通过变量first和动态维护数组来区分未被使用过的元素和已经被使用过的元素所以得到的答案不是按字典序存储的如果题目要求按字典序输出那么则需使用标记数组或者其他方法来维护元素状态。
