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日

相关推荐

  • leetcode67-二进制求和

    原题 给定两个二进制字符串,返回他们的和(用二进制表示)。 输入为非空字符串且只包含数字 1 和 0。 示例 1: 输入: a = “11”, b = “1” 输出: “100” …

    算法 2019年11月15日
    090
  • leetcode199-二叉树的右视图

    原题 给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。 示例: 输入: [1,2,3,null,5,null,4] 输出:&nb…

    算法 2020年4月22日
    0110
  • leetcode234-回文链表

    原题 请判断一个链表是否为回文链表。 示例1: 输入: 1->2 输出: false 示例2: 输入: 1->2->2->1 输出: true 进阶: 你能否用 O(n) 时间复杂…

    2019年12月16日
    0100
  • leetcode92-反转链表

    原题 https://leetcode.cn/problems/reverse-linked-list-ii/description 题解 头插法 /** * Definition…

    算法 2小时前
    010
  • leetcode733-图像渲染

    原题 有一幅以二维整数数组表示的图画,每一个整数表示该图画的像素值大小,数值在 0 到 65535 之间。 给你一个坐标 (sr, sc) 表示图像渲染开始的像素值(行 ,列)和一…

    2019年12月13日
    0100
  • leetcode290-单词规律

    原题 https://leetcode.cn/problems/word-pattern/description/ 解法 类似leetcode205-同构字符串 func word…

    算法 2天前
    030
  • leetcode131-分割回文串

    原题 给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。 返回 s 所有可能的分割方案。 示例: 输入: "aab" 输出: [ ["aa","b"], …

    算法 2020年5月22日
    0100
  • leetcode914-卡牌分组

    原题 给定一副牌,每张牌上都写着一个整数。 此时,你需要选定一个数字 X,使我们可以将整副牌按下述规则分成 1 组或更多组: 每组都有 X 张牌。 组内所有的牌上都写着相同的整数。…

    算法 2020年3月27日
    090
  • leetcode561-数组拆分I

    原题 给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ,使得从1 到 n 的 min(ai, b…

    算法 2019年11月18日
    080
  • 剑指offer50-第一个只出现一次的字符

    原题(来源Leetcode) 在字符串 s 中找出第一个只出现一次的字符。如果没有,返回一个单空格。 s 只包含小写字母。 示例: s = "abaccdeff" 返回 "b" s…

    算法 2020年6月10日
    0170

发表回复

登录后才能评论