代码随想录第三十天打卡|332.重新安排行程， 51. N皇后， 37. 解数独

代码随想录

class Solution {
public:unordered_map<string,map<string,int>>mp;bool backtracking(int ticketNum,vector<string>&res){if (res.size()==ticketNum+1)return true;for (pair<const string,int>&target:mp[res[res.size()-1]]){if (target.second>0){target.second--;res.push_back(target.first);if (backtracking(ticketNum, res))return true;res.pop_back();target.second++;}}return false;}vector<string> findItinerary(vector<vector<string>>& tickets) {vector<string>res;for (const vector<string>target:tickets){mp[target[0]][target[1]]++;}res.push_back("JFK");backtracking(tickets.size(),res);return res;}
};

总结

二刷的时候这题还是没有思路，不过比一刷的时候答案都看不懂要强了。

51. N皇后（可跳过）

代码随想录

视频讲解：这就是传说中的N皇后？ 回溯算法安排！| LeetCode：51.N皇后_哔哩哔哩_bilibili

class Solution {
public:vector<vector<string>>res;bool check(int x,int y,vector<string>mp,int n){//再检查纵向的for (int i=0;i<x;i++){if (mp[i][y]=='Q')return false;}//最后检查斜向的for (int i=x-1,j=y+1;i>=0 && j<n;i--,j++){if (mp[i][j]=='Q')return false;}for (int i=x-1,j=y-1;i>=0 && j>=0;i--,j--){if (mp[i][j]=='Q')return false;}return true;}void backtracking(int n,int deep,vector<string>mp){if (deep==n){res.push_back(mp);return;}for (int y=0;y<n;y++){if (check(deep,y,mp,n)){mp[deep][y]='Q';backtracking(n,deep+1,mp);mp[deep][y]='.';}}}vector<vector<string>> solveNQueens(int n) {vector<string>mp(n,string(n,'.'));backtracking(n,0,mp);return res;}
};

总结

感觉思路比上一题要简单，实现难一些。

37. 解数独（可跳过）

代码随想录

视频讲解：回溯算法二维递归？解数独不过如此！| LeetCode：37. 解数独_哔哩哔哩_bilibili

这题先跳了，明天再看吧，感觉今天花的时间已经有点多了。