微网站开发案例,磁力在线搜索引擎,西安市未央区建设局官方网站,网站游戏下载回溯是递归的副产品#xff0c;只要有递归就会有回溯#xff0c;所以回溯法也经常和二叉树遍历#xff0c;深度优先搜索混在一起#xff0c;因为这两种方式都是用了递归。
回溯法就是暴力搜索#xff0c;并不是什么高效的算法#xff0c;最多再剪枝一下。
回溯算法能解…回溯是递归的副产品只要有递归就会有回溯所以回溯法也经常和二叉树遍历深度优先搜索混在一起因为这两种方式都是用了递归。
回溯法就是暴力搜索并不是什么高效的算法最多再剪枝一下。
回溯算法能解决如下问题
组合问题N个数里面按一定规则找出k个数的集合排列问题N个数按一定规则全排列有几种排列方式切割问题一个字符串按一定规则有几种切割方式子集问题一个N个数的集合里有多少符合条件的子集 棋盘问题N皇后解数独等等
332. 重新安排行程
给你一份航线列表 tickets 其中 tickets[i] [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
所有这些机票都属于一个从 JFK肯尼迪国际机场出发的先生所以该行程必须从 JFK 开始。如果存在多种有效的行程请你按字典排序返回最小的行程组合。
例如行程 [JFK, LGA] 与 [JFK, LGB] 相比就更小排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
示例 1 输入tickets [[MUC,LHR],[JFK,MUC],[SFO,SJC],[LHR,SFO]]
输出[JFK,MUC,LHR,SFO,SJC]示例 2 输入tickets [[JFK,SFO],[JFK,ATL],[SFO,ATL],[ATL,JFK],[ATL,SFO]]
输出[JFK,ATL,JFK,SFO,ATL,SFO]
解释另一种有效的行程是 [JFK,SFO,ATL,JFK,ATL,SFO] 但是它字典排序更大更靠后。提示
1 tickets.length 300tickets[i].length 2fromi.length 3toi.length 3fromi 和 toi 由大写英文字母组成fromi ! toi
教程https://programmercarl.com/0332.%E9%87%8D%E6%96%B0%E5%AE%89%E6%8E%92%E8%A1%8C%E7%A8%8B.html
方法一回溯
思路
class Solution {private LinkedListString res;private LinkedListString path new LinkedList();public ListString findItinerary(ListListString 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(ArrayListListString tickets, boolean[] used) {if (path.size() tickets.size() 1) {res new LinkedList(path);return true;}for (int i 0; i tickets.size(); 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;}
}
