排列问题

排列问题概述

排列问题，主要看「有无重复元素」

• 无重复元素，used数组只用来判断该数选了没有

• 有重复元素，used数组还可以帮助去重

  46. 全排列

  需要一个used数组判断是否用过了
  或者使用list.contains、string.indexOf()判断path里有无当前字符

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

  47. 全排列 II

• used[i] == true判断这个数用过了没，在组合问题中用的是startIndex

• i > 0 && nums[i-1] == nums[i] && used[i-1] == false

  • used[i-1] == false，数层中去重

  • used[i-1] == true，也是可以的，但这是在树枝中去重，排列问题数层树枝都可以，但是组合问题只能在数层中去重

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

332. 重新安排

• 如何记录映射关系，构造什么样的数据结构

Map<出发机场, TreeMap<到达机场, 航班次数>> targets，首先使用TreeMap是为了添加元素默认升序，答案只需要一个升序最小的即可。为什么不使用TreeSet，是因为，TreeSet只能保存从该机场能出发到哪个机场，并不能表明机票是否使用过了，如果使用过了的机票不对航班次数置0，那么可能产生死循环，如图所示，会在JFK和NRT之间来回飞。我们将TreeMap的value作为一个标志位，如果机票用过了就置为0，否则为1。所以我们需要把机票信息处理成出发机场及到达机场的map。

• 回溯函数是有返回值的，因为只要找到一条符合要求的路径就返回即可

• for循环表示横向遍历，遍历从当前机场出发，到所有的目的地机场

  class Solution {
    Map<String, Map<String, Integer>> targets = new HashMap<>();
    Deque<String> res = new LinkedList<>();
    public List<String> findItinerary(List<List<String>> tickets) {
        for (List<String> ticket : tickets) {
            Map<String, Integer> temp;
            if (targets.containsKey(ticket.get(0))) {
                temp = targets.get(ticket.get(0));
                temp.put(ticket.get(1), temp.getOrDefault(ticket.get(1), 0) + 1);
            }else {
                temp = new TreeMap<>(); //升序map
                temp.put(ticket.get(1), 1);
            }
            targets.put(ticket.get(0), temp);
        }
        res.add("JFK");
        backtrack(tickets.size());
        return new ArrayList<>(res);
    }
    public boolean backtrack(int ticketsNum){
        if (res.size() == ticketsNum + 1) {
            return true;
        }
        String last = res.getLast();
        if (targets.containsKey(last)) {
            for (Map.Entry<String, Integer> target : targets.get(last).entrySet()) {
                int count = target.getValue();
                if (count > 0) {
                    res.add(target.getKey());
                    target.setValue(count - 1);
                    if (backtrack(ticketsNum)) {
                        return true;
                    }
                    target.setValue(count);
                    res.removeLast();
                }
            }
        }
        return false;
    }
  }