代码随想录算法训练营20期|第三十天|332.重新安排行程 ● 51. N皇后 ● 37. 解数独 ● 总结

332.重新安排行程 

class Solution {
   List res = new ArrayList<>();
 
    public List findItinerary(List> tickets) {
        //from,             dest,    number
        Map> map = new HashMap<>();
        for(List ticket : tickets){
            String from = ticket.get(0);
            String to   = ticket.get(1);
            
            map.putIfAbsent(from, new TreeMap<>());
            TreeMap treeMap = map.get(from);
            treeMap.put(to, treeMap.getOrDefault(to, 0) + 1);
        }
        
        res.add("JFK");
        backtrack(tickets, map, 0);
 
        return res;
    }
 
    private boolean backtrack(List> tickets, Map> map,int progress){
        if(progress == tickets.size()){
            return true;
        }
 
        TreeMap tos = map.get(res.get(res.size() - 1));
        if(tos == null || tos.isEmpty() || tos.size() == 0)
            return false;
        
        for(String str : tos.keySet()){
            if(tos.get(str) == 0)
                continue;
 
            res.add(str);
            tos.put(str, tos.get(str) - 1);
 
            if(backtrack(tickets, map, progress + 1))
                return true;
 
            res.remove(res.size() - 1);
            tos.put(str, tos.get(str) + 1);
        }
 
        return false;
    }
 
 
 
}

•  51. N皇后 

•  37. 解数独 

•  总结