数据结构与算法===回溯法

简介: 数据结构与算法===回溯法

原理

回溯法是采用试错的思想,它尝试分步骤的去解决一个问题。在分步骤解决问题的过程中,当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候,它将取消上一步甚至是上几步的计算,再通过其它的可能得分步解答再次尝试寻找问题的答案。

百度百科是这么解释的。

使用场景

现在聊聊使用场景的问题,之前的文章深度优先采用的就是回溯的思想。就是在当前层级一个一个试完,然后再去下一个层级遍历。可以去看看这篇文章。下边再看一个案例吧。

括号生成

代码

这个是Java的,如下:

class Solution {
    ArrayList<String> result = new ArrayList<>();
    public List<String> 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_ptr<vector<string>> cache[100] = {nullptr};
public:
    shared_ptr<vector<string>> generate(int n) {
        if (cache[n] != nullptr)
            return cache[n];
        if (n == 0) {
            cache[0] = shared_ptr<vector<string>>(new vector<string>{""});
        } else {
            auto result = shared_ptr<vector<string>>(new vector<string>);
            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];
    }
    vector<string> generateParenthesis(int n) {
        return *generate(n);
    }
};

小结

本篇聊了下回溯算法,使用场景,及代码。

本篇主要聊了回溯算法,使用场景,代码。深度优先是一个很好的例子,在当前层级一直试错,直到成功;当然,极端情况可能是不成功,那样的话算法复杂度就是指数级了。可以看下代码实现,生成括号是个不错的选择。OK,翻篇。

相关文章
|
6月前
|
算法 Python
Python高级算法——回溯法(Backtracking)
Python高级算法——回溯法(Backtracking)
296 2
|
算法 定位技术 C++
基本算法-回溯法(迷宫问题)
基本算法-回溯法(迷宫问题)
502 0
|
5月前
|
存储 机器学习/深度学习 算法
python 3种算法 回溯法、字典序生成、递归交换 实现全排列【力扣46题】
python 3种算法 回溯法、字典序生成、递归交换 实现全排列【力扣46题】
|
算法
【系统分析】数值算法——回溯法
【系统分析】数值算法——回溯法
104 0
|
6月前
|
Go
基础数据结构leetcode回溯法专题
基础数据结构leetcode回溯法专题
29 0
|
6月前
|
算法
【算法学习】—n皇后问题(回溯法)
【算法学习】—n皇后问题(回溯法)
|
存储 人工智能 算法
【算法分析与设计】回溯法(上)
【算法分析与设计】回溯法(上)
|
存储 算法 容器
精选算法题(1)——枚举符合要求的算术表达式(DFS、回溯法)
精选算法题(1)——枚举符合要求的算术表达式(DFS、回溯法)
|
存储 算法 索引
从小白开始刷算法 回溯法篇 leetcode.78
从小白开始刷算法 回溯法篇 leetcode.78
|
存储 机器学习/深度学习 算法
从小白开始刷算法 回溯法篇 leetcode.22
从小白开始刷算法 回溯法篇 leetcode.22