第二十六天 | 332.重新安排行程 51. N皇后 37. 解数独总结

332.重新安排行程

给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始.

思路：1.出发机场和目的地机场可以用defaultdict(list)装，key是出发机场，value是目的地机场列表。2. 由于行程可能变成一个圈，为了避免在圈内来回飞，我们将已经飞过的行程从字典中移除。3. 由于只要返回一个最小结果，可以在每一层循环前，对目的地排序，这样可以先遍历较小的结果。同时，只要得到一个正确的答案，就直接返回，无需再遍历下去。因此需要在枝条末端得到结果的时候，返回True。上层枝条得到这个True后，也往上返回True，直到跳出函数。

51. N皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题的解决方案。每一种解法包含一个不同的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

思路：1. 从上往下一行一行填，一行只能填一个皇后。因此问题就转为在每一行，选择一个合适的列填入皇后。2. 定义一个isvalid函数，判断当前的选择是否合法。3. 问题就转为了一个标准的回溯算法。

37. 解数独

思路：和N皇后问题类似，对于board上的每一个格子，在0-9之间选择填入一个合法的数字。如果最后填满所有格子，则解题成功。1.定义一个isvalid函数。2. 对board逐行逐列遍历，空格子填入合法数字，然后进入下一层回溯去填下一个格子。3. 由于数独问题只要一个答案即可，因此在得道一个答案的时候，可以返回True，然后上一层回溯算法把这个True往上传，直到结束函数。4. 全部格子都填入合法数字，则为答案。