原题
给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3] 输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1] ]
解法
思想
做这道题的时候我才发现我做这类回溯算法的题还是蛮少的，对集合的深克隆api不是很熟悉。主要是深克隆的蛮麻烦 -。-||
思想就是回溯啦，可以用一个数组记录使用过了的元素。
代码
class Solution {
List<List<Integer>> ans = new ArrayList<>();
int[] globalNums;
public List<List<Integer>> permute(int[] nums) {
int[] used = new int[nums.length];
globalNums = nums;
List<Integer> list = new ArrayList<>();
trackback(list,used,0);
return ans;
}
public void trackback(List<Integer> list,int[] used,int usedCount){
if(usedCount==globalNums.length){
ans.add(list);
}
for(int i = 0;i<globalNums.length;i++){
if(used[i]==0){
List<Integer> copy = new ArrayList<>(list);
copy.add(globalNums[i]);
int[] usedCopy = Arrays.copyOf(used,used.length);
usedCopy[i] = 1;
trackback(copy,usedCopy,usedCount+1);
}
}
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode46-%e5%85%a8%e6%8e%92%e5%88%97/
相关推荐
-
leetcode394-字符串解码
原题 给定一个经过编码的字符串，返回它解码后的字符串。 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意...
-
力扣杯春季个人赛-剧情触发时间
这次的个人赛真是让我认清了自己的实力。。两道困难题都没做出?，虽然大家的通过率也不咋地。。 最后排名 我记录一道做出来的题吧，这道题是一道中等题，通过率如下，虽然题目不难，但由于时...
-
leetcode376-摆动序列
原题 如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。 例如， [1,7,4,9,...
-
leetcode67-二进制求和
原题 给定两个二进制字符串，返回他们的和（用二进制表示）。 输入为非空字符串且只包含数字 1 和 0。 示例 1: 输入: a = “11”, b = “1” 输出: “100” ...
-
蓝桥杯试题-哈夫曼树
原题 Description Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。 给出一列数{pi}={p0, p1, …, pn-1}，用这列...
-
leetcode33-搜索旋转排序数组
原题 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值，...
-
程序员面试金典17.01-不用加号的加法
原题（来源Leetcode） 设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。 示例: 输入: a = 1, b = 1 输出: 2 提示： a, b 均可能是负数或...
-
leetcode57-插入区间
原题 给出一个无重叠的 ，按照区间起始端点排序的区间列表。 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。 示例 1: 输入: ...
-
leetcode13-罗马数字转整数
原题 罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。 字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 例如， 罗马数字 2...
-
leetcode62-不同路径
原题 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Fi...
