[LeetCode] Permutations I / II

shery 发布于2019-08-14 15:14 / 1649人阅读

Permutations I Problem

Given a list of numbers, return all possible permutations.

Example

For nums = [1,2,3], the permutations are:

[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

Challenge

Do it without recursion.

Solution

Recursion

class Solution {
    public ArrayList> permute(ArrayList num) {
        ArrayList> res = new ArrayList>();
        if (num == null || num.size() == 0) {
            return res;
        }
        ArrayList list = new ArrayList ();
        helper (nuts, list, res);
        return res;
    }
    
    public void helper(ArrayList num, ArrayList list, ArrayList> res) {
        if (list.size() == num.size()) {
            res.add(new ArrayList (list));
            return;
        }
        for (int i = 0; i < num.size(); i++) {
            if (list.contains(num.get(i))) {
                continue;
            }
            list.add(num.get(i));
            helper(num, list, res);
            list.remove(list.size() - 1);
        }
    }
}

Permutations II Problem

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

Solution

sort

call backtracking function in main function

in backtracking function, when temp list size equals nums array size, save a copy of temp list to result

iteration nums array, if current num is used, or it"s same as previous num and previous num is unused (released), continue

update temp array and used boolean array at the same time in back tracking.

class Solution {
    public List> permuteUnique(int[] nums) {
        List> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        Arrays.sort(nums);
        helper(nums, new ArrayList(), new boolean[nums.length], res);
        return res;
    }
    private void helper(int[] nums, List temp, boolean[] used, List> res) {
        if (temp.size() == nums.length) res.add(new ArrayList<>(temp));
        else {
            for (int i = 0; i < nums.length; i++) {
                if (used[i] || (i > 0 && !used[i-1] && nums[i] == nums[i-1])) {
                    continue;
                } else {
                    used[i] = true;
                    temp.add(nums[i]);
                    helper(nums, temp, used, res);
                    temp.remove(temp.size()-1);
                    used[i] = false;
                }
            }
        }
    }
}

私有云 GPU服务器 II ii6 ii7 Permutations

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65480.html

leetcode47 Permutations II

摘要：当前的值如果已经被使用过，则继续判断下一个数值。则当第一个被添加进结果集时，可以继续使用第二个作为元素添加进结果集从而生成。假设将表示为那么结果集中会确保永远在数值的前面，从而避免了和的重复情况出现。题目要求 Given a collection of numbers that might contain duplicates, return all possible unique ...

taoszu 2019-08-14 18:33 评论0 收藏0
leetcode 47 Permutations II

摘要：题目详情题目要求输入一个可能会有重复数字的数组，要求我们输出可能组成的全排列无重复排列。可以用来实现，但这种实现方式复杂度高。另外一种实现思路是，新声明一个数组来存储中元素的使用状况。以这个数组为例。题目详情 Given a collection of numbers that might contain duplicates, return all possible unique ...

Cobub 2019-08-16 11:13 评论0 收藏0
[Leetcode] Permutations 全排列

摘要：每一轮搜索选择一个数加入列表中，同时我们还要维护一个全局的布尔数组，来标记哪些元素已经被加入列表了，这样在下一轮搜索中要跳过这些元素。 Permutations I Given a collection of numbers, return all possible permutations. For example, [1,2,3] have the following permu...

scq000 2019-08-14 12:31 评论0 收藏0
[Leetcode]PermutationsI II Next Permutation Permut

摘要：解题思路这道题是要将排列按字典序排列，然后求出下一个排列，一种办法是我们先求出所有的排序情况，但是题目规定不能占有额外空间。每次求出一个数字后，要及时的把它从中删除掉。采用来构造结果序列。 PermutationsGiven a collection of distinct numbers, return all possible permutations. For example, ...

ChristmasBoy 2019-08-16 10:26 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0