[LeetCode] Permutations I / II

shery 發布于2019-08-14 15:14 / 1770人閱讀

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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