leetcode 记录 day3

蜡烛之间的盘子

首先预处理出每个位置左边第一个蜡烛的位置，以及右边第一个蜡烛的位置，然后用前缀和算就行

括号生成

直接dfs，过程中用栈判断是否合法

合并K个升序链表

用优先队列帮我们从K个表头中找最小的那个，然后append到答案链表中

最长有效括号

因为不合法的情况有两种。

一种是右括号多了，当右括号多的时候，之后的合法括号序列一定在这个右括号后面

左括号多的情况下，则是没有对应的右括号去栈中与他更新答案，即合法的序列在此之前就出现了。

我们每次成功构造出合法序列的时候一定是右括号成功匹配左括号的时候，所以只要在成功匹配的地方尝试更新答案即可

对于多余的左括号，就会放在栈中，没有影响。

对于多出来的右括号，则会把现有的栈pop空，我们把这个右括号的位置记下来，那么下次成功匹配以后，我们就可以找到最左边的不合法的位置，从而更新答案

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> st;
        int ans = 0;
        st.push(-1);
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') {
                st.push(i);
            } else {
                st.pop();
                if (st.empty()) {
                    st.push(i);
                } else {
                    ans = max(ans, i - st.top());
                }
            }
        }
        return ans;
    }
};

跳跃游戏

这个可以直接记录我们可能跳到的最远的地方，然后不断更新就行

我当时做的时候没考虑到这个，而是用了一个差分来进行区间加，当这个位置的值大于1的时候，就可以继续跳跃

跳跃游戏2

就是让多记录一下跳的最小的次数

考虑的核心在于，我们即便是跳过了可以跳到的更远的地方，也不需要考虑回去重跳的情况

即如果当前这次跳跃最远可以到i，那么所有小于i的地方都可以成为下一次起跳的起点，我们不需要考虑具体是在哪里起跳，只要考虑最远能到哪里就行

合并区间

按照左端点排序后模拟合并就行

序列化与反序列化

这个貌似模拟就可以，与直接的前序不同的是，遇到null我们要给他添加到字符串中

零钱兑换