设计一个stack, 有一个函数可以增加stack中底部向上k个数.

这个一看就要用cpp做, 直接vector, 原因是可以random access, 有现成的pop_back()和pop(). 然后我刚知道v.size()返回不是int, 是unsigned int, 还不能直接用min比

class CustomStack {
public:
    vector<int> v;
    int max;
    CustomStack(int maxSize) {
        max = maxSize; 
    }
    
    void push(int x) {
        if(v.size() >= max)
            return;
        v.push_back(x);
    }
    
    int pop() {
        if(empty(v))
            return -1;
        int res = v.back();
        v.pop_back();
        return res;
    }
    
    void increment(int k, int val) {
        int vv = v.size();
        int c = min(k, vv);
        for(int i = 0; i < c; i++){
            v[i] += val;
        }
    }
};

/**
 * Your CustomStack object will be instantiated and called as such:
 * CustomStack* obj = new CustomStack(maxSize);
 * obj->push(x);
 * int param_2 = obj->pop();
 * obj->increment(k,val);
 */

给一个数组, 每次选三个数字, 只能拿到第二大的, 问怎么选的最大.

这题就是贪婪, 多看几个例子就知道, 因为拿不到最大的,所以排序后, 大端选两个, 小端选一个.

class Solution {
public:
    int maxCoins(vector<int>& piles) {
        sort(piles.begin(), piles.end(), greater<int>());
        int res = 0;
        int j = piles.size() - 1;
        for(int i = 0;i <= j; i+=2){
            res += piles[i+1];
            j--;
        }
        return res;
    }
};

给一个数组, 里面是同样长度的string, 求这个string组成的grid是否对应的每列都是字典序的

class Solution {
public:
    int minDeletionSize(vector<string>& strs) {
        int n = strs.size();
        int m = strs[0].length();
        int res = 0;
        for(int i = 0; i < m; i++){
            for(int j = 1; j < n; j++) {
                if(strs[j - 1][i] > strs[j][i]){
                    res++;
                    break;
                }
            }
        }
        return res;
    }
};

给一个DAG(有向无圈图), 求从0到n-1的所有路径.

直接dfs

class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<int> tmp; 
        dfs(graph, tmp, 0);
        return res;
    }
    void dfs(vector<vector<int>>& graph, vector<int>& tmp, int cur){
        tmp.push_back(cur);
        if(cur == graph.size() - 1){
            res.push_back(tmp);
            return;
        }
        for(auto i : graph[cur]){
            dfs(graph, tmp, i);
            tmp.pop_back();
        } 
    }
};

给一个二叉树, 里面有random pointer, 求deep copy这个二叉树.

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     Node *left;
 *     Node *right;
 *     Node *random;
 *     Node() : val(0), left(nullptr), right(nullptr), random(nullptr) {}
 *     Node(int x) : val(x), left(nullptr), right(nullptr), random(nullptr) {}
 *     Node(int x, Node *left, Node *right, Node *random) : val(x), left(left), right(right), random(random) {}
 * };
 */

class Solution {
public:
    NodeCopy* copyRandomBinaryTree(Node* root) {
        unordered_map<Node*, NodeCopy*> map;
        return copy(root, map);
    }
    
    NodeCopy* copy(Node* root, unordered_map<Node*, NodeCopy*>& map) {
        if(root == nullptr)
            return nullptr;
        if(map.find(root) != map.end())
            return map[root];
        NodeCopy* nodecopy = new NodeCopy(root->val);
        map[root] = nodecopy;
        nodecopy->left = copy(root->left, map);
        nodecopy->right = copy(root->right, map);
        nodecopy->random = copy(root->random, map);
        return nodecopy;
    }
};

给一个postfix的表达式数, 让设计一个Node, 里面有evaluate方法, 可以算出答案.

这个题是偏设计, 所以一般不用全局的stack算, 上来给了个node的抽象类, 然后通过观察可以看到有数字+加减乘除几种node组成, 分辨写出这几个node. 然后输入的string是postfix, 所以只需要从后往前一个个扫描即可建树.

class Node {
public:
    Node(Node* l, Node* r) : left(l), right(r){} 
    virtual ~Node () {};
    virtual int evaluate() const = 0;
protected:
    Node* left;
    Node* right;
};

class VNode : public Node {
    public:
    VNode(int value) : Node(nullptr, nullptr), val(value){}
    int evaluate() const{
        return val;
    }
    protected:
    int val;
};

class Plus : public Node {
    public:
    Plus(Node* l, Node* r) : Node(l, r){}
    protected:
    int evaluate() const{
        return left->evaluate() + right->evaluate();
    }
};

class Minus : public Node {
    public:
    Minus(Node* l, Node* r) : Node(l, r){}
    protected:
    int evaluate() const{
        return right->evaluate() - left->evaluate();
    }
};
class Multiply : public Node {
    public:
    Multiply(Node* l, Node* r) : Node(l, r){}
    protected:
    int evaluate() const{
        return left->evaluate() * right->evaluate();
    }
};
class Divide : public Node {
    public:
    Divide(Node* l, Node* r) : Node(l, r){}
    protected:
    int evaluate() const{
        return right->evaluate() / left->evaluate();
    }
};
class TreeBuilder {
public:
    Node* buildTree(vector<string>& postfix) {
        if(postfix.size() == 0)
            return nullptr;
        string s  = postfix.back();
        postfix.pop_back();
        if(!isdigit(s[0])){
            auto left = buildTree(postfix);
            auto right = buildTree(postfix);
            if(s == "+"){
                return new Plus(left, right);
            }else if(s == "-"){
                return new Minus(left, right);
            }else if (s == "*")
            {
                return new Multiply(left, right);
            }else
            {
                return new Divide(left, right);
            }
        }else{
            return new VNode(stoi(s));
        }
    }
};

给一个2d数组, 求不改变里面数字对应行列最大值的情况下, 数组数字最大增加多少.

这题读懂题很关键, 先找行列对应的最大值, 然后再用两个值中小的那个减去现有的值, res += min(row[i], col[j]) – grid[i][j], where row[i], col[j] is the max number of i, j.

class Solution {
public:
    int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        vector<int> col(m);
        vector<int> row(n);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                row[i] = max(row[i], grid[i][j]);
                col[j] = max(col[j], grid[i][j]);
            }
        }
        int res = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                res += min(row[i], col[j]) - grid[i][j];
            }
        }
        return res;
    }
};

给一个只有奇数的从1开始的递增数组, 给一个operation, 可以让后边的数字变大1前边的数字变小1. 求多少个operation后, 可以让数组的数字全部相等.

这个题就是观察一下, 比如数字第一个数字肯定是1, 那么最后一个数字是2*(n – 1) + 1 = 2*n – 1; 然后一次变换只能加减1, 那么就求差然后除2即可.

class Solution {
public:
    int minOperations(int n) {
        int res = 0;
        int i = 1;
        int j = 2*(n - 1) + 1;
        while(i < j){
            res += (j - i) / 2;
            i+=2;
            j-=2;
        }
        return res;
    }
};

给一个数组, 找到有多少组的i,j,k使得ary[i] < ary[j] < ary[k].

这题就o(n^2)的查找就能过.

class Solution {
public:
    int numTeams(vector<int>& r) {
        int res = 0;
        int n = r.size();
        for(int i = 0; i < n; i++){
            int countLeftInc = 0;
            int countRightInc = 0;
            int countLeftDec = 0;
            int countRightDec = 0;
            for(int j = 0; j < i; j++){
                if(r[j] < r[i]){
                    countLeftInc++;
                }
                else{
                    countLeftDec++;
                }
            }
            for(int j = i + 1; j < n; j++){
                if(r[j] > r[i]){
                    countRightInc++;
                }
                else{
                    countRightDec++;
                }
            }
            res += (countLeftInc * countRightInc);
            res += (countLeftDec * countRightDec);
        }
        return res;
    }
};

给一个string, 里面是括号, 求最少添加几个括号, 让string valid.

用stack跟踪string的左括号. 最后stack的大小就是答案

class Solution {
public:
    int minAddToMakeValid(string S) {
        stack<char> st; 
        for(auto c : S) {
            if(c == '('){
                st.push(c);
            }else{
                if(st.empty()){
                    st.push(c);
                }else{
                    if(st.top() == '('){
                        st.pop();
                    }
                    else{
                        st.push(c);
                    }
                }
            }
        }
        return st.size();
    }
};