1. Star collision
   Given an integer array astroids, the planets in the same row are represented. For each element in the array, its absolute value represents the size of the planet, and positive and negative represents the moving direction of the planet (positive represents moving to the right, negative represents moving to the left). Each planet moves at the same speed.
   Find all the planets left after the collision. Collision rule: two planets collide with each other, and the smaller planet will explode. If two planets are the same size, both planets will explode. Two planets moving in the same direction will never collide.

Very suitable for stack solution

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        vector<int> ans; // Pretend to be a stack and just push_back operation, pop_back() operation
        int n = asteroids.size();
        for(int i = 0; i < n; ++i){
            if(ans.empty() || asteroids[i] > 0) ans.push_back(asteroids[i]);
            else{
                while(ans.size() && ans.back() > 0 && ans.back() < -asteroids[i])
                    ans.pop_back(); // If a collision occurs and the absolute value of the positive number is small, delete the positive number
                if(ans.empty() || ans.back() < 0) ans.push_back(asteroids[i]);
                else if(ans.back() == -asteroids[i]) ans.pop_back(); // Delete both
            }
        }
        return ans;
    }
};

1. lisp syntax parsing

class Solution {
    struct IncompleteExpression {
        unordered_map<string_view, int> variables;
        string_view varname;
        int count, value;
        char type;  // Function name initials

        IncompleteExpression() : variables(), varname(), count(0), value(), type() {}

        void update_arithmetic(int val) {
            if(type == 'a') { // addition
                if(count == 1) { // The first argument (the zeroth is the function name)
                    value = val;
                } else {         // Second parameter
                    value += val;
                }
            } else {       // multiplication
                if(count == 1) {
                    value = val;
                } else {
                    value *= val;
                }
            }
        }
    };
    
    struct Parser {
        vector<IncompleteExpression> nested;
        int value;

        // Find the value of a number
        static int eval_int(const char* str, size_t str_len) {
            int x = 0;
            for(size_t i = 0; i != str_len; ++i) {
                x = x * 10 + str[i] - '0';
            }
            return x; 
        }
        
        // Find the value of a variable
        int eval_variable(string_view name) {
            for(auto i = nested.rbegin(), e = nested.rend(); i != e; ++i) {
                auto x = i->variables.find(name);
                if(x != i->variables.end()) {
                    return x->second;
                }
            }
            return 0;
        }

        // Find the value of a variable or number
        int eval(const char* str, size_t str_len) {
            if(isdigit(*str)) {
                return eval_int(str, str_len);
            } else if (*str == '-') { // It is not supported to add a minus sign before a variable. The beginning of a minus sign can only be a number
                return - eval_int(str + 1, str_len - 1);
            } else return eval_variable(string_view(str, str_len));
        }

        // Left parenthesis encountered
        void left_parenthesis() {
            nested.emplace_back();
        }

        // Right parenthesis encountered
        void right_parenthesis() {
            auto& inner = nested.back();
            int val;
            if(!inner.varname.empty()) { // There is a variable name before the right parenthesis that has not been resolved e.g. (let x 8 x)
                val = eval_variable(inner.varname);
            } else {
                val = inner.value;
            }
            nested.pop_back();
            if(!nested.empty()) {  // Not the last brace
                auto& t = nested.back();
                if(t.type == 'l') { // let
                    if((t.count & 1) != 0) {
                        t.value = val;
                    } else {
                        t.variables[t.varname] = val;
                        t.varname = string_view(); // Clear unresolved variable names
                    }
                }  else {
                    t.update_arithmetic(val);
                }
                ++t.count;
            } else {// The last curly bracket. The final result is stored in Parser::value
                value = val;
            }
        }

        // It can be a function name, a variable name, or a number
        void new_identifier(const char* str, size_t str_len) {
            auto& t = nested.back();
            if(t.count == 0) {
                t.type = *str;
            } else if(t.type == 'l') { // let
                if((t.count & 1) != 0) {
                    if (isdigit(*str)) {
                        t.value = eval_int(str, str_len);
                    } else if (*str == '-') { // It is not supported to add a minus sign before a variable. The beginning of a minus sign can only be a number
                        t.value = - eval_int(str + 1, str_len - 1);
                    } else {
                        t.varname = string_view(str, str_len);
                    }
                } else {
                    t.variables[t.varname] = eval(str, str_len);
                    t.varname = string_view(); // Clear unresolved variable names
                }
            } else {
                t.update_arithmetic(eval(str, str_len));
            }
            ++t.count;
        }
    };
public:
    int evaluate(string expression) {
        Parser parser;
        for(auto i = expression.cbegin(), e = expression.cend(); i != e;) {
            if(*i == '(') {
                parser.left_parenthesis();
                ++i;
            } else if(*i == ')') {
                parser.right_parenthesis();
                ++i;
            } else if(isspace(*i)) {
                ++i;
            } else {
                auto j = i;
                for(; !isspace(*i) && *i != '(' && *i != ')'; ++i);
                parser.new_identifier(addressof(*j), i - j);
            }
        }
        return parser.value;
    }
};

1. Monotonically increasing number
   Given a nonnegative integer n, find the largest integer less than or equal to N. at the same time, this integer needs to meet that the number on each digit is monotonically increasing.

Greedy algorithm

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string strN = to_string(n);
        int i = 1;
        while (i < strN.length() && strN[i - 1] <= strN[i]) {
            i += 1;
        }
        if (i < strN.length()) {
            while (i > 0 && strN[i - 1] > strN[i]) {
                strN[i - 1] -= 1;
                i -= 1;
            }
            for (i += 1; i < strN.length(); ++i) {
                strN[i] = '9';
            }
        }
        return stoi(strN);
    }
};

1. Daily temperature
   According to the daily temperature list, please calculate how many days you need to wait for a higher temperature each day. If the temperature will not rise after that, please replace it with 0 in this position.

Use the monotone stack to access the subscript of each element. If the next element is greater than the top of the stack, it will be out of the stack and recorded, otherwise it will be stacked to the end

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> ans(n);
        stack<int> s;
        for (int i = 0; i < n; ++i) {
            while (!s.empty() && temperatures[i] > temperatures[s.top()]) {
                int previousIndex = s.top();
                ans[previousIndex] = i - previousIndex;
                s.pop();
            }
            s.push(i);
        }
        return ans;
    }
};

1. Delete and get points
   Give you an integer array nums, you can do some operations on it. In each operation, select any num [i], delete it and obtain the number of num [i]. After that, you must delete all elements equal to nums[i] - 1 and nums[i] + 1. You have 0 points at the beginning. Returns the maximum number of points you can get through these operations.

Dynamic programming solution after sorting. The key point is that when taking x points, all x points can be actually obtained, but x - 1 and x + 1 cannot. This can be used for dynamic programming with adjacent as 1

class Solution {
private:
    int rob(vector<int> &nums) {
        int size = nums.size();
        if (size == 1) {
            return nums[0];
        }
        int first = nums[0], second = max(nums[0], nums[1]);
        for (int i = 2; i < size; i++) {
            int temp = second;
            second = max(first + nums[i], second);
            first = temp;
        }
        return second;
    }

public:
    int deleteAndEarn(vector<int> &nums) {
        int n = nums.size();
        int ans = 0;
        sort(nums.begin(), nums.end());
        vector<int> sum = {nums[0]};
        for (int i = 1; i < n; ++i) {
            int val = nums[i];
            if (val == nums[i - 1]) {
                sum.back() += val;
            } else if (val == nums[i - 1] + 1) {
                sum.push_back(val);
            } else {
                ans += rob(sum);
                sum = {val};
            }
        }
        ans += rob(sum);
        return ans;
    }
};

1. Cherry picking
   An N x N grid represents a cherry field. Each grid is represented by one of the following three numbers:
   0 means the grid is empty, so you can go through it.
   1 means that there is a cherry in this grid. You can pick the cherry and pass through it.
   -1 means there are thorns in this grid, blocking your way.
   Your task is to pick as many cherries as possible under the following rules

In essence, it is no different from the dynamic planning of taking stairs

class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {
        int N = grid.size(), dp[N+1][N+1];
        memset(dp, 0x80, sizeof(dp)); //-2139062144, equivalent to INT_MIN
        dp[N-1][N-1] = grid[N-1][N-1]; // Initial boundary conditions
        for(int sum = 2*N - 3; sum >= 0; --sum)
        for(int i1 = max(0, sum - N + 1); i1 <= min(N-1,sum); ++i1)
        for(int i2 = i1; i2 <= min(N-1,sum); ++i2)
        {
            int j1 = sum - i1, j2 = sum - i2;
            if(grid[i1][j1] == -1 || grid[i2][j2] == -1) 
                dp[i1][i2] = INT_MIN;
            else
                dp[i1][i2] = grid[i1][j1] + (i1 != i2 || j1 != j2)*grid[i2][j2] + max(
                    max(dp[i1][i2+1], dp[i1+1][i2]), 
                    max(dp[i1+1][i2+1], dp[i1][i2])
                );
        }
        return max(0, dp[0][0]);     
    }
};

1. Network delay time
   There are n network nodes marked 1 to n. Give you a list of times, indicating the transmission time of the signal through the directed edge. times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time when a signal is transmitted from the source node to the target node. Now, a signal is sent from a node K. How long will it take for all nodes to receive the signal? If all nodes cannot receive the signal, return - 1.

disjkstra or Bellman Ford or spfa or floyd can be used, among which dijestra is the most recommended for simplicity and efficiency

class Solution {
public:
    /*Establish adjacent nodes, node represents vertex and weight represents weight*/
    struct Nodes {
        Nodes(int n, int w, Nodes* s) : node(n), weight(w), next(s) {};
        int node;
        int weight;
        Nodes* next;
    };
    /*Adjacent joint node*/
    struct Heads {
        Heads() : val(INT_MAX / 2), lists(nullptr), visit(true) {};
        int val;//Road strength from the source point to the node
        bool visit;//Mark whether you can visit
        Nodes* lists;//Adjacency node
    };

    /*x->y，Establish an adjacency table. If x is the source point, initialize the val value of y*/
    void initialize(Heads*& h, int x, int y, int weight, int k) {
        Nodes* ph = new Nodes(y, weight, h[x].lists);
        h[x].lists = ph;
        if (x == k)     h[y].val = weight;
        return;
    }
    int networkDelayTime(vector<vector<int>>& t, int n, int k) {
        Heads* h = new Heads[n];//Start with 0
        int size = t.size();
        k--;//Start with 0 and subtract one from the vertex
        h[k].val = 0, h[k].visit = false;//Source point processing

        /*initialization*/
        for (int i = 0; i < size; i++) {
            initialize(h, t[i][0] - 1, t[i][1] - 1, t[i][2], k);
        }

        /*Only the remaining n-1 vertices need to be relaxed at most*/
        for (int i = 0; i < n - 1; i++) {

            /*Find the nearest to the source point and write it down in book*/
            int mi = INT_MAX, book;
            for (int i = 0; i < n; i++) {
                if (h[i].visit && h[i].val < mi) {
                    mi = h[i].val;
                    book = i;
                }
            }
            /*If the source point cannot reach any point at this time, return directly*/
            if (mi == INT_MAX)    return -1;
            h[book].visit = false;//Mark not accessible

            /*Take this point as the center and start to relax*/
            Nodes* p = h[book].lists;
            while (p) {
                if (h[book].val + p->weight < h[p->node].val) {
                    h[p->node].val = h[book].val + p->weight;
                }
                p = p->next;
            }
        }
        int ret = 0;
        /*Answer processing, the answer is the longest point, that is, the least time we need*/
        for (int i = 0; i < n; i++) {
            ret = max(ret, h[i].val);
        }
        return ret == INT_MAX/2 ? -1 : ret;
    }
};