332.重新安排行程

文章：19. 重新安排行程

题目：332. 重新安排行程

【思路】

题目存在的几个问题：

1.一个行程中会出现回头，会形成一个圈，处理不好的话。

2.有多种解法，要返回字母序靠前排在前面的

3.使用回溯，终止条件是什么

4.如何遍历一个机场所对应的所有机场

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    private LinkedList<String>res ;
    private LinkedList<String> path = new LinkedList<>();
    public List<String> findItinerary(List<List<String>> tickets) {
        Collections.sort(tickets,(a,b)->a.get(1).compareTo(b.get(1)));
        path.add("JFK");
        boolean[] used = new boolean[tickets.size()];
        backtracking((ArrayList)tickets,used);
        return res;
    }
    public boolean backtracking(ArrayList<List<String>>tickets,boolean[]used){
        //出发地和目的地 多一个！
        if(path.size() == tickets.size()+1){
            res = new LinkedList(path);
            return true;
        }
        
        for(int i=0;i<tickets.size();i++){
            //如果当前机票没有被使用！false && ticket的第i个机票组的出发地等于行程里最后的目的地相等则有下一个路径
            if(!used[i] && tickets.get(i).get(0).equals(path.getLast())){
                path.add(tickets.get(i).get(1));
                used[i] = true;
                if(backtracking(tickets,used)){
                    return true;
                }
                used[i] = false;
                path.removeLast();
            }
        }
        return false;
    }
}
  • GO实现（看不懂）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
type pair struct{
    target string
    visited bool
}
type pairs []*pair
func(p pairs)Len()int{
    return len(p)
}
func(p pairs)Swap(i,j int){
    p[i],p[j] = p[j],p[i]
}
func(p pairs)Less(i,j int)bool{
    return p[i].target < p[j].target
}


func findItinerary(tickets [][]string) []string {
    res := []string{}
    targets := make(map[string]pairs)
    for _,ticket := range tickets{
        if targets[ticket[0]] == nil{
            targets[ticket[0]] = make(pairs,0)
        }
        targets[ticket[0]] =append(targets[ticket[0]],&pair{target:ticket[1],visited:false})
    }
    for k,_ := range targets{
        sort.Sort(targets[k])
    }
    res = append(res,"JFK")
    var backtracking func()bool 
    backtracking = func()bool{
        if len(tickets)+1 == len(res){
            return true
        }
        for _,pair := range targets[res[len(res)-1]]{
            if pair.visited == false{
                res = append(res,pair.target)
                pair.visited = true
                if backtracking(){
                    return true
                }
                res = res[:len(res)-1]
                pair.visited = false
            }
        }
        return false
    }
    backtracking()
    return res 
}

51.N皇后

文章：

题目：

  • Java实现
1

  • Go实现
1

37.解数独

文章：

题目：

  • Java实现
1

  • Go实现
1

【回溯章节总结】

回溯理论基础

回溯是递归的副产品，只要有递归就会有回溯。所有回溯法基础和二叉树遍历，深度优先搜索混在一起，因为这两种方式都是用了递归。

回溯法就是暴力搜索，不是什么高效的算法，最多再剪枝一下。

能解决的问题：

  • 组合问题：N个数里面按一定规则找出k个数的集合
  • 排列问题：N个数按一定规则全排列，有几种排列方式
  • 切割问题：一个字符串按一定规则有几种切割方式
  • 子集问题：一个N个数的集合里有多少符合条件的子集
  • 棋盘问题：N皇后，解数独等等

回溯法模板：

1
2
3
4
5
6
7
8
9
10
11
void backtracking(参数){
	if(终止条件){
		存放结果；
		return；
	}
	for(选择：本层集合元素（树中节点孩子的数量就是集合的大小）){
		处理节点；
		backtracking(路径，选择列表);//递归
		回溯，撤销处理结果
	}
}

组合问题

用递归控制for循环嵌套的数量。

for循环：横向遍历，递归：纵向遍历，回溯不断调整结果集

优化回溯算法只有剪枝一种方法。剪枝精髓：for循环在寻找起点的时候要有一个范围，如果这个起点到集合终止之间的元素已经不够题目要求的k个元素，也就没有搜索的必要了。

在for循环上做剪枝操作是回溯法剪枝的常见套路。

startIndex的使用：

1.如果是一个集合来求组合的话，就需要startIndex，例如：回溯算法：求组合问题，回溯算法：求组合总和。

2.如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex，例如：回溯算法：电话号码的字母组合

组合总和

组合总和（一）

有元素总和的限制，因此我们提出剪枝：已选元素总和如果已经大于n（题中要求的和）了，那么往后遍历就没有意义了，直接剪掉。

在本题中，依然还可以有一个剪枝，就是回溯算法：组合问题再剪剪枝 (opens new window)中提到的，对for循环选择的起始范围的剪枝。

所以剪枝的代码可以在for循环加上 i <= 9 - (k - path.size()) + 1 的限制！

组合总和（二）

需要使用startIdex来规定循环遍历的起始位置。

组合总和（三）

题目给的元素里面，集合元素会有重复，但要求解集不能包含重复的组合。

因此我们需要解决去重的问题。

“树枝去重” “树层去重”

组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上面是有两个维度的，一个维度是同一树枝上“使用过”，一个维度是在统一树层上“使用过”。

在candidates[i] == candidates[i - 1]相同的情况下：

  • used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
  • used[i - 1] == false，说明同一树层candidates[i - 1]使用过

子集问题

子集问题（一）

在树形结构中子集问题就是要收集所有节点的结果，而组合问题是收集叶子节点的结果。

子集问题（二）

在上题的基础上加上了去重，不选取前面已经出现过的相同值，使用**排序+bool数组used和nums[i] == nums[i-1]**进行判断。

递增子序列

不能提前排序，因为这题需要我们获得递增的子序列，不能够修改数组。==>因此选择使用set对已经使用过的值进行进一步的存储。

本题明显一个元素不能够重复使用，所以需要startIndex调整下一层递归的起始位置。

!path.isEmpty() && nums[i] <path.get(path.size()-1) || set.contains(nums[i])

排列问题

排列问题（一）

排序是有序的，也即是说{1,2}和{2,1}是两个集合，之前使用过的数还要再次使用，因此：

  • 每层都是从0开始搜索而不是startIndex
  • 需要used数组记录path都放了哪些元素

排列问题（二）

和上一题不同的是需要去重，也就是“树层去重”和“树枝去重”

使用(used[i - 1] == false)，即树层去重，效率更高！

去重问题

使用used数组去重 和 使用set去重 两种写法的性能差异：

使用set去重的版本相对于used数组的版本效率都要低很多，大家在leetcode上提交，能明显发现。

原因在回溯算法：递增子序列 (opens new window)中也分析过，主要是因为程序运行的时候对unordered_set 频繁的insert，unordered_set需要做哈希映射（也就是把key通过hash function映射为唯一的哈希值）相对费时间，而且insert的时候其底层的符号表也要做相应的扩充，也是费时的。

而使用used数组在时间复杂度上几乎没有额外负担！

使用set去重，不仅时间复杂度高了，空间复杂度也高了，在本周小结！（回溯算法系列三） (opens new window)中分析过，组合，子集，排列问题的空间复杂度都是O(n)，但如果使用set去重，空间复杂度就变成了O(n^2)，因为每一层递归都有一个set集合，系统栈空间是n，每一个空间都有set集合。

那有同学可能疑惑 用used数组也是占用O(n)的空间啊？

used数组可是全局变量，每层与每层之间公用一个used数组，所以空间复杂度是O(n + n)，最终空间复杂度还是O(n)。

重新安排行程（图论额外拓展）

感觉和排列去重很像，但需要回溯函数有额外的bool返回值来判断该路径是否能够被选择，如果这条路径==给出的航班数组数+1的话说明该条为有效航班路线。同时，本题要求我们如果有多条路线，按字典序更前的输出，也就意味着我们需要先将航班排序再进行下列操作。