全排列2

1、代码:

https://leetcode-cn.com/problems/permutations-ii/submissions/

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        ArrayList<List<Integer>> resultList = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return resultList;
        }
        dfs(0, nums, resultList);
        return resultList;
    }

    public void dfs(int depth, int[] nums, List<List<Integer>> resultList) {
        // 递归基
        if (depth == nums.length-1) {
            ArrayList<Integer> oneResult = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                oneResult.add(nums[i]);
            }
            resultList.add(oneResult);
            return;
        }

        // 遍历到每一层能做的选择:
        // 第0层:0号位可以和0,1,2交换;
        // 第1层:1号位可以和1,2交换;
        // 第2层:2号位可以和2交换。
        for (int i = depth; i < nums.length; i++) {
            if(isRepeat(nums,depth,i)){
                continue;
            }
            swap(nums, depth, i);
            dfs(depth + 1, nums, resultList);
            swap(nums, depth, i);
        }
    }

    private boolean isRepeat(int[] nums,int depth,int i){
        for (int j = depth; j < i; j++) {
            if(nums[j]==nums[i]){
                return true;
            }
        }
        return false;

    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

。。

上一篇:清华数据结构PA6——旅行商(TSP)


下一篇:获取格式化查询字符串