阜阳专业网站建设,最好用wordpress主题,互联网广告,网站建设 绵阳332.重新安排行程
题目链接#xff1a;332.重新安排行程
给你一份航线列表 tickets #xff0c;其中 tickets[i] [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
所有这些机票都属于一个从 JFK#xff08;肯尼迪国际机场#xff09;出发的…332.重新安排行程
题目链接332.重新安排行程
给你一份航线列表 tickets 其中 tickets[i] [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
所有这些机票都属于一个从 JFK肯尼迪国际机场出发的先生所以该行程必须从 JFK 开始。如果存在多种有效的行程请你按字典排序返回最小的行程组合。
例如行程 [JFK, LGA] 与 [JFK, LGB] 相比就更小排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。 文章讲解/视频讲解https://programmercarl.com/0332.%E9%87%8D%E6%96%B0%E5%AE%89%E6%8E%92%E8%A1%8C%E7%A8%8B.html 思路
采用回溯的方法解决最暴力的方法就是直接回溯通过判断路径是否是否等于tickets.size() 1来决定是否结束。
为了获得字典序最小的结果我将tickets排了序并在找到结果时提前剪枝但是在第80/81样例处超时了。
可以用unordered_mapstring, mapstring, int targetsunordered_map出发机场, map到达机场, 航班次数 targets这个数据结构来构造这样就不会超时了。
C实现
// 原写法
class Solution {
public:vectorstring results;vectorint used;bool finded;vectorstring findItinerary(vectorvectorstring tickets) {auto cmp [](vectorstring a, vectorstring b){return a[0] b[0] ? a[1] b[1] : a[0] b[0];};sort(tickets.begin(), tickets.end(), cmp);string curr JFK;used.resize(tickets.size(), false);finded false;vectorstring path;path.push_back(curr);backtracking(path, curr, tickets);path.pop_back();return results;}void backtracking(vectorstring path, string curr, const vectorvectorstring tickets){if(finded) return;if(path.size() tickets.size() 1){results path;finded true;return;}for(int i 0;itickets.size();i){if(tickets[i][0] curr){if(!used[i]){path.push_back(tickets[i][1]);used[i] true;backtracking(path, tickets[i][1], tickets);path.pop_back();used[i] false;}}}}
// 用哈希表加速遍历
class Solution {
public:unordered_mapstring, mapstring,int targets;vectorstring findItinerary(vectorvectorstring tickets) {for(const vectorstring ticket : tickets){targets[ticket[0]][ticket[1]];}string curr JFK;vectorstring results;results.push_back(curr);backtracking2(results, tickets.size());return results;}bool backtracking2(vectorstring results, int ticket_size){if(results.size() ticket_size 1){return true;}string curr results[results.size() - 1];for(auto des : targets[curr]){if(des.second 0){results.push_back(des.first);des.second--;if(backtracking2(results, ticket_size)) return true;des.second;results.pop_back();}}return false;}
};
51. N皇后
题目链接51. N皇后
按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。
给你一个整数 n 返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案该方案中 Q 和 . 分别代表了皇后和空位。 文章讲解/视频讲解https://programmercarl.com/0051.N%E7%9A%87%E5%90%8E.html 思路
采用回溯方法解决在使用回溯之前提前做一下处理
建立存储每一行是否有Q的hash表每一列是否有Q的hash表每一个正斜线是否有Q的hash表每一个反斜线是否有Q的hash表。
由于我回溯函数里的纵向遍历是根据每一行递归处理的因此这里存储每一行是否有Q的hash表并不需要。
C实现
class Solution {
public:vectorvectorstring results;vectorbool rowHash, columnHash, slashHash, backslashHash;vectorvectorstring solveNQueens(int n) {//rowHash.resize(n, false);columnHash.resize(n, false);slashHash.resize(2*n-1, false);backslashHash.resize(2*n-1, false);vectorstring current;for(int i 0;in;i){string tmp(n, .);current.push_back(tmp);}backtracking(current, 0, n);return results;}void backtracking(vectorstring current, int curri, int n){if(curri n){results.push_back(current);return;}for(int j 0;jn;j){int slashIdx curri j;int backslashIdx curri (n - j - 1);if(!columnHash[j] !slashHash[slashIdx] !backslashHash[backslashIdx]){columnHash[j] true;slashHash[slashIdx] true;backslashHash[backslashIdx] true;current[curri][j] Q; backtracking(current, curri 1, n);current[curri][j] .;columnHash[j] false;slashHash[slashIdx] false;backslashHash[backslashIdx] false;}}}
};37. 解数独
题目链接37. 解数独
编写一个程序通过填充空格来解决数独问题。
数独的解法需 遵循如下规则
数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。请参考示例图
数独部分空格内已填入了数字空白格用 . 表示。 文章讲解/视频讲解https://programmercarl.com/0037.%E8%A7%A3%E6%95%B0%E7%8B%AC.html 思路
首先找到每一个空白格’.之后遍历这些空白格来进行回溯解决。
在回溯之前需要一些处理需要9 9 9个哈希表分别表示每一行的哈希表每一列的哈希表每一个小方格的哈希表。
之后进行回溯操作便可。
C实现
class Solution {
public:vectorunordered_setchar rowHash; // 行vectorunordered_setchar columnHash; // 列vectorunordered_setchar blockHash; // 3x3方格vectorvectorint blanks;void solveSudoku(vectorvectorchar board) {rowHash.resize(board.size());columnHash.resize(board.size());blockHash.resize(board.size());for(int i 0;iboard.size();i){for(int j 0;jboard[i].size();j){int k 3 * (i / 3) (j / 3);if(board[i][j] ! .){rowHash[i].insert(board[i][j]);columnHash[j].insert(board[i][j]);blockHash[k].insert(board[i][j]);}else{blanks.push_back({i, j, k});}}}backtracking(0, board);}bool backtracking(int curri, vectorvectorchar board){if(curri blanks.size()){return true;}vectorint index blanks[curri];for(int i 1;i9;i){char num 0 i;if(rowHash[index[0]].find(num) rowHash[index[0]].end() columnHash[index[1]].find(num) columnHash[index[1]].end() blockHash[index[2]].find(num) blockHash[index[2]].end()){rowHash[index[0]].insert(num);columnHash[index[1]].insert(num);blockHash[index[2]].insert(num);board[index[0]][index[1]] num;if(backtracking(curri 1, board)) return true;board[index[0]][index[1]] .;rowHash[index[0]].erase(num);columnHash[index[1]].erase(num);blockHash[index[2]].erase(num);}}return false;}
};回溯总结
https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E6%80%BB%E7%BB%93.html
