一些算法好题
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;
}

递归回溯

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

bool check(vector<int> &arr1, vector<int> &arr2, vector<int> &arr3, vector<int> &arr4, int n, int x, int y) {
    return arr1[x] == 0 && arr2[y] == 0 && arr3[y-x+n] == 0 && arr4[x+y] == 0;
}

void add(vector<int> &arr1, vector<int> &arr2, vector<int> &arr3, vector<int> &arr4, vector<string> &v, int n, int x, int y) {
    arr1[x] = 1;            // 
    arr2[y] = 1;            // 
    arr3[y-x+n] = 1;        // 
    arr4[x+y] = 1;          // 
    v[x][y] = 'xxx';
}

void remove(vector<int> &arr1, vector<int> &arr2, vector<int> &arr3, vector<int> &arr4, vector<string> &v, int n, int x, int y) {
    arr1[x] = 0;            // 
    arr2[y] = 0;            // 
    arr3[y-x+n] = 0;        // 
    arr4[x+y] = 0;          // 
    v[x][y] = 'xxx';
}

数据结构

895 https://leetcode.com/problems/maximum-frequency-stack/description/ (这道题应该 100 分可以打 90 分了)

https://leetcode.com/problems/maximum-frequency-stack/discuss/166136/Easy-Java-Solution-using-PriorityQueue

class FreqStack {
    Map<Integer,Integer> map;
    PriorityQueue<int[]> pq;
    int index;
    public FreqStack() {
        map = new HashMap<>();
        pq = new PriorityQueue<>((a,b) -> {
                if (a[1] == b[1]) {
                    return b[2] - a[2];
                } else {
                    return b[1] - a[1];
                }
        });
        index = 0;
    }

    public void push(int x) {
        int freq = map.getOrDefault(x,0) + 1;
        map.put(x,freq);
        pq.offer(new int[]{x, freq, index++});
    }

    public int pop() {
        int temp =  pq.poll()[0];
        if (map.get(temp) == 1) {
            map.remove(temp);
        } else {
            map.put(temp, map.get(temp)-1);
        }
        return temp;
    }
}

https://leetcode.com/problems/maximum-frequency-stack/discuss/163410/C++JavaPython-O(1)

unordered_map<int, int> freq;
unordered_map<int, stack<int>> m;
int maxfreq = 0;

void push(int x) {
    maxfreq = max(maxfreq, ++freq[x]);
    m[freq[x]].push(x);
}

int pop() {
    int x = m[maxfreq].top();
    m[maxfreq].pop();
    if (!m[maxfreq].size()) maxfreq--;
    freq[x]--
    return x;
}