leetcode46-全排列

原题

给定一个没有重复数字的序列,返回其所有可能的全排列。

示例:

输入: [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/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年3月2日
下一篇 2020年3月3日

相关推荐

  • 'leetcode50-Pow(x,n)'

    原题 实现 pow(x, n) ,即计算 x 的 n 次幂函数。 示例1: 输入: 2.00000, 10 输出: 1024.00000 示例2: 输入: 2.10000, 3 输…

    算法 2020年1月5日
    0210
  • leetcode45-跳跃游戏II

    原题 原题 给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 示例: 输…

    算法 2020年2月15日
    0150
  • leetcode28-实现strStr()

    原题 实现 strStr() 函数。 给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从…

    算法 2019年11月20日
    0130
  • leetcode328-奇偶链表

    原题 给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。 请尝试使用原地算法完成。你的算法的空…

    算法 2019年12月16日
    0130
  • leetcode125-验证回文串

    原题 给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。 说明: 本题中,我们将空字符串定义为有效的回文串。 示例 1: 输入: "A man, a …

    算法 2020年5月21日
    0150
  • leetcode1115-交替打印FooBar

    原题 我们提供一个类: class FooBar { public void foo() {     for (int i = 0; i < n; i++) {       …

    算法 2020年2月2日
    0180
  • leetcode498-对角线遍历

    这是一个Z字形编排问题,JEPG的编码过程中也会用到。 原题 给定一个含有 M x N 个元素的矩阵(M 行,N 列),请以对角线遍历的顺序返回这个矩阵中的所有元素,对角线遍历如下…

    2019年11月14日
    0110
  • leetcode402-移掉K位数字

    原题 给定一个以字符串表示的非负整数 num,移除这个数中的 k 位数字,使得剩下的数字最小。 注意: num 的长度小于 10002 且 ≥ k。 num 不会包含任何前导零。 …

    算法 2020年1月29日
    0100
  • leetcode41-缺失的第一个正数

    原题 给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。 示例 1: 输入: [1,2,0] 输出: 3 示例 2: 输入: [3,4,-1,1] 输出: 2 示例 3…

    算法 2020年5月11日
    0130
  • 蓝桥杯试题-哈夫曼树

    原题 Description Huffman树在编码中有着广泛的应用。在这里,我们只关心Huffman树的构造过程。 给出一列数{pi}={p0, p1, …, pn-1},用这列…

    算法 2020年3月1日
    0250

发表回复

登录后才能评论