【0262_Week03】回溯法小结及一些零碎知识点

Z-Clark commented 4 years ago

回溯算法小结

回溯算法，大部分情况下，都是用来解决广义的搜索问题，即从一组可能的解中，选择出一个满足要求的解。

（注意：该算法非常适合使用递归，而剪枝是提高回溯效率的常用技巧！）

实际上，解决一个回溯问题，就是一个遍历决策树的过程，关键有三点：

路径：已经做出的选择
选择列表：当前可以做的选择
结束条件：即到达决策树底层，无法再做选择

回溯算法的框架

def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.push_back(路径);
        return;
    for 选择 in 选择列表:
        做选择;                //递归前，做选择
        backtrack(路径, 选择列表);
        撤销选择;              //递归后，撤销选择
    (可选)将该选择再加入选择列表  //eg.全排列问题

正因为回溯算法，必须穷举整棵决策树，因此，时间复杂度一般较高，且 >= O(n)。

全排列（重复和不可重复）的两个问题，可以多研究几遍，有好处！

附上一篇大佬写的题解：labuladong的回溯算法详解

一些零碎知识点（C++）：

1.优先队列

priority_queue<int, vector, greater > p; 小顶堆

priority_queue p;默认大顶堆

2.滑动窗口最大值问题

为了解决C++的priority_queue不能删除特定元素的问题，可以采用pair类型关联该特定条件，妙！

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> result;
    if (k == 0) return result;
    priority_queue<pair<int, int>> w;
    for (int i = 0, n = (int)nums.size(); i < n; i++) {
        while (!w.empty() && w.top().second <= i-k)
            w.pop();
        w.push(make_pair(nums[i],i));
        if (i >= k-1)
            result.push_back(w.top().first);
    }
    return result;
}

3.前后序遍历

前序遍历的代码在进入某一个节点之前的那个时间点执行，后序遍历代码在离开某个节点之后的那个时间点执行。

4.图的相关链接