排列问题

46.全排列，47*全排列II(数组中含有重复元素)，332重新安排行程，51N皇后
46.全排列

private List<List<Integer>>res=new ArrayList<>();
    private List<Integer>singleRes=new LinkedList<>();
    private boolean[]used;
    public List<List<Integer>> permute(int[] nums) {
        used=new boolean[nums.length];
        backTrack(0,nums);
        return res;
    }
    private void backTrack(int index,int[]nums){
        if(singleRes.size()==nums.length){
            res.add(new ArrayList<>(singleRes));
            return;
        }
        for(int i=index;i<nums.length;i++){
            if(used[i]){
                continue;
            }
            singleRes.add(nums[i]);
            used[i]=true;
            backTrack(index,nums);
            singleRes.remove(singleRes.size()-1);
            used[i]=false;
        }
 }

47.全排列2

private List<List<Integer>>res=new ArrayList<>();
    private List<Integer>singleRes=new LinkedList<>();
    private boolean[]used;
    public List<List<Integer>> permuteUnique(int[] nums) {
        used=new boolean[nums.length];
        Arrays.sort(nums);
        backTrack(0,nums);
        return res;
    }
    private void backTrack(int index,int[]nums){
        if(singleRes.size()==nums.length){
            res.add(new ArrayList<>(singleRes));
            return;
        }
        for(int i=index;i<nums.length;i++){
            if(i>index&&nums[i]==nums[i-1]&&used[i-1]==false){
                continue;
            }
            if(used[i]==false){
                singleRes.add(nums[i]);
                used[i]=true;
                backTrack(index,nums);
                singleRes.remove(singleRes.size()-1);
                used[i]=false;
            }
        }
    }

332.重新安排行程

private List<String>res=new ArrayList<>();
    private Map<String, PriorityQueue<String>> map=new HashMap<>();
    public List<String> findItinerary(List<List<String>> tickets) {
        for (List<String> ticket : tickets) {
            String start=ticket.get(0);
            String end=ticket.get(1);
            if(!map.containsKey(start)){
                map.put(start,new PriorityQueue<>());
            }
            map.get(start).add(end);
        }
        backTrack("JFK",map);
        Collections.reverse(res);
        return res;
    }
    private void backTrack(String depart,Map<String,PriorityQueue<String>>map){
        while (map.containsKey(depart)&&map.get(depart).size()>=1) {
            String poll = map.get(depart).poll();
            backTrack(poll, map);
        }
        res.add(depart);
    }

51.N皇后

private List<List<String>>res=new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        char[][]chars=new char[n][n];
        for(int i=0;i<chars.length;i++){
            for(int j=0;j<chars[0].length;j++){
                chars[i][j]='.';
            }
        }
        backTrack(0,n,chars);
        return res;
    }
    private void backTrack(int row,int n,char[][]chars){
        if(row==n){
            res.add(charArrayToList(chars));
            return;
        }
        for(int col=0;col<n;col++){
            if(check(row,col,chars)){
                chars[row][col]='Q';
                backTrack(row+1,n,chars);
                chars[row][col]='.';
            }
        }
    }
    private boolean check(int row,int col,char[][]chars){
        //检查同一列
        for(int i=row;i>=0;i--){
            if(chars[i][col]=='Q'){
                return false;
            }
        }
        //检查45度角
        for(int i=row,j=col;i>=0&&j>=0;i--,j--){
            if(chars[i][j]=='Q'){
                return false;
            }
        }
        //检查135°角
        for(int i=row,j=col;i>=0&&j<chars[0].length;i--,j++){
            if(chars[i][j]=='Q'){
                return false;
            }
        }
        return true;
    }
    private List<String> charArrayToList(char[][]chars){
        List<String>list=new ArrayList<String>();
        for (char[] aChar : chars) {
            list.add(String.copyValueOf(aChar));
        }
        return list;
    }