一些算法好题
09 September 2018

收集一些做过的好题:不能直观的想出解决方案,或者想出了解决方案但是代码写起来很 “模棱两可(写不出)” 的题目

155 https://leetcode.com/problems/min-stack/description/

已知一个栈的入栈顺序,求出所有可能的出栈顺序

void dfs(vector<vector<int>> &res, vector<int> v, stack<int> st, int len, int num, int stackSize) {
    if (num == len+1) {
        while (!st.empty()) {
            auto top = st.top();
            v.push_back(top);
            st.pop();
        }

        res.push_back(v);
        return;
    }

    // 1. 栈为空
    if (stackSize == 0) {
        st.push(num);
        dfs(res, v, st, len, num+1, stackSize+1);
        return;
    }

    // 2. 栈不为空
    auto s1 = st;
    auto s2 = st;

    // 2.1 继续入栈
    s1.push(num);
    dfs(res, v, s1, len, num+1, stackSize+1);

    // 2.2 弹出来
    auto top = s2.top();
    v.push_back(top);
    s2.pop();
    dfs(res, v, s2, len, num, stackSize-1);
}

int main(void) {
    int len = 5;
    int num = 1;
    int stackSize = 0;                  // 栈大小

    stack<int> st;
    vector<vector<int>> res;
    vector<int> v;
    dfs(res, v, st, len, num, stackSize);

    return 0;
}

递归回溯

51
52
八皇后,数独 [思路是:某个位置被设置了以后,可以根据 4 个维度来标记,代码如下]