leetcode解题思路分析（八十四）735 - 743 题

一时失言乱红尘 2022-08-30 01:51 150阅读 0赞

1.  星星碰撞  
    给定一个整数数组 asteroids，表示在同一行的行星。对于数组中的每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向（正表示向右移动，负表示向左移动）。每一颗行星以相同的速度移动。  
    找出碰撞后剩下的所有行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。

**很适合用栈解决**

class Solution { 
    public:
        vector<int> asteroidCollision(vector<int>& asteroids) { 
            vector<int> ans; // 假装是栈，只做push_back操作、pop_back()操作
            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(ans.empty() || ans.back() < 0) ans.push_back(asteroids[i]);
                    else if(ans.back() == -asteroids[i]) ans.pop_back(); // 两者都删除
                }
            }
            return ans;
        }
    };

1.  lisp语法解析

class Solution { 
        struct IncompleteExpression { 
            unordered_map<string_view, int> variables;
            string_view varname;
            int count, value;
            char type;  // 函数名首字母
    
            IncompleteExpression() : variables(), varname(), count(0), value(), type() { }
    
            void update_arithmetic(int val) { 
                if(type == 'a') {  // 加法
                    if(count == 1) {  // 第一个参数（第零个是函数名）
                        value = val;
                    } else {          // 第二个参数
                        value += val;
                    }
                } else {        // 乘法
                    if(count == 1) { 
                        value = val;
                    } else { 
                        value *= val;
                    }
                }
            }
        };
        
        struct Parser { 
            vector<IncompleteExpression> nested;
            int value;
    
            // 求一个数字的值
            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; 
            }
            
            // 求一个变量的值
            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;
            }
    
            // 求一个变量或数字的值
            int eval(const char* str, size_t str_len) { 
                if(isdigit(*str)) { 
                    return eval_int(str, str_len);
                } else if (*str == '-') {  // 不支持变量前加负号，负号开头的只能是数字
                    return - eval_int(str + 1, str_len - 1);
                } else return eval_variable(string_view(str, str_len));
            }
    
            // 遇到左括号
            void left_parenthesis() { 
                nested.emplace_back();
            }
    
            // 遇到右括号
            void right_parenthesis() { 
                auto& inner = nested.back();
                int val;
                if(!inner.varname.empty()) {  // 右括号前有个变量名还没解析 e.g. (let x 8 x)
                    val = eval_variable(inner.varname);
                } else { 
                    val = inner.value;
                }
                nested.pop_back();
                if(!nested.empty()) {   // 不是最后一个大括号
                    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(); // 清空未解析的变量名
                        }
                    }  else { 
                        t.update_arithmetic(val);
                    }
                    ++t.count;
                } else { // 最后一个大括号，得到最终结果存在Parser::value里
                    value = val;
                }
            }
    
            // 可能是函数名、变量名或数字
            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 == '-') {  // 不支持变量前加负号，负号开头的只能是数字
                            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(); // 清空未解析的变量名
                    }
                } 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.  单调递增的数字  
    给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。

**贪心算法求解**

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.  每日温度  
    请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。

**使用单调栈存取每一个元素的下标，如果下一个元素大于栈顶则出栈并记录，否则一直堆到最后**

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.  删除并获得点数  
    给你一个整数数组 nums ，你可以对它进行一些操作。每次操作中，选择任意一个 nums\[i\] ，删除它并获得 nums\[i\] 的点数。之后，你必须删除 所有 等于 nums\[i\] - 1 和 nums\[i\] + 1 的元素。开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

**排序后动态规划求解。要点在于取x点数时，所有的x实际都能取到，但是x - 1和 x + 1不可以，以此来做相邻为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.  摘樱桃  
    一个N x N的网格(grid) 代表了一块樱桃地，每个格子由以下三种数字的一种来表示：  
    0 表示这个格子是空的，所以你可以穿过它。  
    1 表示这个格子里装着一个樱桃，你可以摘到樱桃然后穿过它。  
    \-1 表示这个格子里有荆棘，挡着你的路。  
    你的任务是在遵守下列规则的情况下，尽可能的摘到最多樱桃

**本质上和走楼梯的动态规划没有区别**

class Solution { 
    public:
        int cherryPickup(vector<vector<int>>& grid) { 
            int N = grid.size(), dp[N+1][N+1];
            memset(dp, 0x80, sizeof(dp)); //-2139062144, 作用相当于 INT_MIN
            dp[N-1][N-1] = grid[N-1][N-1]; // 初始边界条件
            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.  网络延迟时间  
    有 n 个网络节点，标记为 1 到 n。给你一个列表 times，表示信号经过 有向 边的传递时间。 times\[i\] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

**disjkstra或者Bellman-ford或者spfa或者floyd均可，其中迪杰斯特拉简单高效最为推荐**

class Solution { 
    public:
        /*建立邻接节点,node表示顶点,weight表示权*/
        struct Nodes { 
            Nodes(int n, int w, Nodes* s) : node(n), weight(w), next(s) { };
            int node;
            int weight;
            Nodes* next;
        };
        /*邻接头节点*/
        struct Heads { 
            Heads() : val(INT_MAX / 2), lists(nullptr), visit(true) { };
            int val;//源点到该节点的路劲
            bool visit;//标记是否可以拜访
            Nodes* lists;//邻接节点
        };
    
        /*x->y，建立邻接表,如果x是源点的话,初始化y的val值*/
        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];//以0开头
            int size = t.size();
            k--;//以0开头，顶点减一
            h[k].val = 0, h[k].visit = false;//源点处理
    
            /*初始化*/
            for (int i = 0; i < size; i++) { 
                initialize(h, t[i][0] - 1, t[i][1] - 1, t[i][2], k);
            }
    
            /*最多只需松弛其余n-1个顶点*/
            for (int i = 0; i < n - 1; i++) { 
    
                /*找出离源点最近的，并用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 (mi == INT_MAX)    return -1;
                h[book].visit = false;//标记不可拜访
    
                /*以这个点为中心，开始松弛*/
                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;
            /*答案处理,答案是最长的点,即我们最少需要的时间*/
            for (int i = 0; i < n; i++) { 
                ret = max(ret, h[i].val);
            }
            return ret == INT_MAX/2 ? -1 : ret;
        }
    };