万网网站建设方案书,深圳建筑工程招聘信息,网站内部搜索怎么做,快速做彩平图得网站文章目录 原理使用场景括号生成代码 小结 原理
回溯法是采用试错的思想#xff0c;它尝试分步骤的去解决一个问题。在分步骤解决问题的过程中#xff0c;当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候#xff0c;它将取消上一步甚至是上几步的计算#x… 文章目录 原理使用场景括号生成代码 小结 原理
回溯法是采用试错的思想它尝试分步骤的去解决一个问题。在分步骤解决问题的过程中当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候它将取消上一步甚至是上几步的计算再通过其它的可能得分步解答再次尝试寻找问题的答案。
百度百科是这么解释的。
使用场景
现在聊聊使用场景的问题之前的文章深度优先采用的就是回溯的思想。就是在当前层级一个一个试完然后再去下一个层级遍历。可以去看看这篇文章。下边再看一个案例吧。
括号生成 代码
这个是Java的,如下
class Solution {ArrayListString result new ArrayList();public ListString generateParenthesis(int n) {_generate(0, 0, n, );return result;}private void _generate(int left, int right, int n, String s) {if (left right left n) {result.add(s);return;}if(left n) {_generate(left 1, right, n, s ();}if (left right) {_generate(left, right 1, n, s ));}}
}下边看看c的如下
class Solution {shared_ptrvectorstring cache[100] {nullptr};
public:shared_ptrvectorstring generate(int n) {if (cache[n] ! nullptr)return cache[n];if (n 0) {cache[0] shared_ptrvectorstring(new vectorstring{});} else {auto result shared_ptrvectorstring(new vectorstring);for (int i 0; i ! n; i) {auto lefts generate(i);auto rights generate(n - i - 1);for (const string left : *lefts)for (const string right : *rights)result - push_back(( left ) right);}cache[n] result;}return cache[n];}vectorstring generateParenthesis(int n) {return *generate(n);}
};小结
本篇聊了下回溯算法使用场景及代码。
本篇主要聊了回溯算法使用场景代码。深度优先是一个很好的例子在当前层级一直试错直到成功当然极端情况可能是不成功那样的话算法复杂度就是指数级了。可以看下代码实现生成括号是个不错的选择。OK翻篇。
