美文网首页
46 & 47. Permutations

46 & 47. Permutations

作者: exialym | 来源:发表于2016-11-02 16:53 被阅读9次

    46 Permutations

    Given a collection of distinct numbers, return all possible permutations.
    For example,[1,2,3] have the following permutations:
    [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
    使用深度优先搜索加递归

    function permute(nums) {
        var res = [];
        var used = [];
        var tmp = [];
        helper(nums, tmp);
        return res;
        function helper(nums, tmp){
            //已经满了就放到结果数组里并退出这层helper
            if(tmp.length == nums.length){
                res.push(tmp.concat());
            } else {
                for(var idx = 0; idx < nums.length; idx++){
                    // 遇到已经加过的元素就跳过
                    if(used[idx]){
                        continue;
                    }
                    used[idx] = true;
                    tmp.push(nums[idx]);
                    //加入该元素后进入下一层helper
                    //下一层helper还是从头开始遍历,将第一个找到的没用过的元素压入tmp
                    helper(nums, tmp);
                    tmp.pop();
                    used[idx] = false;
                }
            }
        }
    }
    

    47. Permutations II

    Given a collection of numbers that might contain duplicates, return all possible unique permutations.
    For example,
    [1,1,2] have the following unique permutations:
    这次数组中可能有重复的元素,但是最后的组合不能是重复的。
    加一个判断条件,如果后面的元素等于前面的元素,且前面的元素在本次结果中已经使用了,那么这个后面的元素才可以用。

    var permuteUnique = function(nums) {
        var res = [];
        var used = [];
        var num = nums.length;
        nums.sort();
        var help = function(temp) {
            //console.log(temp);
            if (temp.length===nums.length) {
                res.push(temp.concat());
            } else {
                for (var i = 0;i < num;i++) {
                    if (used[i]===true)
                        continue;
                    if (nums[i]===nums[i-1]&&used[i-1]!==true) 
                        continue;
                    used[i] = true;
                    temp.push(nums[i]);
                    help(temp);
                    temp.pop();
                    used[i] = false;
                }
            }
        };
        help([]);
        return res;
    };
    

    相关文章

      网友评论

          本文标题:46 & 47. Permutations

          本文链接:https://www.haomeiwen.com/subject/wnnvuttx.html