代码随想录--6.回溯学习记录

一些回溯的心得

也是让我蹭上困难level的题了，比较自豪的是截至目前已经尽力把所有问题往二叉树的结构方向靠拢，致力于只用一招破题。说白了就是travel中的for循环为当前节点所在层的遍历，而for内的travel则是当前节点往下走的延伸。需要注意的点就是针对不同场景，要考虑返回值是void还是bool（当然我个人还是喜欢void，bool实在难以得心应手），要找的方案是只有一个还是若干，这都会影响具体代码实现细节，比如if中需不需要return，for每次从哪开始，需不需要记录当前index并传参到下一次travel中。

最终需要的结果大都是二维vector，区别在于内里的vector是什么类型一般是int或者string，相比标准解法中的直接在string上操作，我更喜欢用vector<int>来进行处理，最后发现符合需求时再转换成vector<string>并纳入最终res中，事实上感觉这种不需要变化太多的处理流程我想称之为范式，只需要针对不同场景在细节处仔细斟酌即可，大方向都是一个套路，下面以N皇后为例

N皇后

整个代码是比较丝滑地写出来的，一气呵成，（当然也可能因为是上午做的，脑袋比较清醒，昨晚的安排行程那题就给我做破防了（后来怒刷韩剧去了，模范出租车还是太爽了看得），同为困难却也亦有差距啊）从看题到思索再到写出，唯一花时间的地方就是判断排兵布阵的合法性，最后跑通并对比标准答案后也证实了我这套范式的可行性，起码简约且舒适。

class Solution { public: bool isR(vector<int>& dis,int n,int target){ if(dis.empty())return true; if(find(dis.begin(),dis.end(),target)!=dis.end()) return false; for(int i=dis.size()-1;i>=0;i--){ if(abs(dis[i]-target)==dis.size()-i) return false; } return true; } vector<vector<string>> res; vector<int> dis; void travel(int n){ if(dis.size()==n){ string s(n,'.'); vector<string> sol(n,s); for(int i=0;i<n;i++){ sol[i][dis[i]]='Q'; } res.emplace_back(sol); } for(int i=0;i<n;i++){ if(isR(dis,n,i)){ dis.push_back(i); travel(n); dis.pop_back(); } } } vector<vector<string>> solveNQueens(int n) { travel(n); return res; } };

看完就发现来来回回无非就这么几套，满足条件如果复杂就写个isR()函数判断，简单就直接在for或者if中判断，然后记得travel前后操作保持对称，所以有的涉及到重复问题（标准答案给的是用used的vector记录）我都是懒得整直接最后输出res之后排序然后unique去重之类的。但这些重复的问题在未来肯定会经常碰到，都还缺乏对我而言舒适且真正稳固耐用的范式，所以之后n刷的时候需要重点考虑。