312. Burst Balloons

312. Burst Balloons

思路:

Hard题做了才有收获啊!lc上题库里几道经典的具有锻炼思维和思考能力的题。

  1. 拿到手,首先映入脑海里明显应该是贪心或者分治算法:仔细思考一下,贪心发现没有依据,也没有例子;分治算法把考虑把求取问题dp(l, r)——开区间的(l,r)一组气球全部戳爆以后,可以获取最大金币数量。如果第一选取k个气球戳爆,则有子问题(l,k)(k,r),但是可以发现两个子问题是相互依赖的。也就是说一个问题解的选择会影响另一个问题的解的选择。所以这个思路也不行。

  2. Amazing的是,我们可以反过来考虑问题!我们把整个过程逆序,把戳爆存在的气球,变成从一个气球都不存在,添加一个个不存在的气球。dp(l, r)问题就是在寻找,把(l, r)中的所有位置填满气球,可以获得最大金币数量。思考一下如何分解为子问题:
    $$
    dp(l, r) = max_{i = l + 1}^{r - 1}[dp(l , i) + dp(i, r) + nums[i] * nums[l] * nums[r]]
    $$
    具体计算可以用记忆化搜索和DP计算。

看了下大神的解法,居然还有用启发式搜索的!太顶了!

Read more

438. Find All Anagrams in a String

思路:

双指针,指向模式串str的子串首位s和末尾+1e

遍历思路:

  1. 不断添加e位置上的字符c
  2. 如果c不属于p,则双指针跳过c
  3. 如果c属于p,则更新。
    1. 但是如果包括的c字符太多了,则移动s直至数量符合条件
    2. 如果所有字符数量都添加完全一致,则添加结果。移动s一位,更新即可。

看了其他题解,发现有一个条件我忽略了,指针之间的距离是相等的,也就是说这是一个滑动窗口问题~草了。

那这很简单,维护一下窗口值就行了。

可以说滑动窗口就是一个简单的双指针。

Read more

84. Largest Rectangle in Histogram

84. Largest Rectangle in Histogram

思路:

  1. 遍历高度数组的同时,维护形成的矩阵,并更新最大面积。
  2. 观察,矩阵的面积可以不严格递增的情况下在从左到右扩展的,再严格递减的情况下可以确定出矩阵面积。正向数据缓存,逆向面积计算-> 单调栈。read more

代码:

class Solution {
    map<int, pair<int,int>> reg;
public:
    int largestRectangleArea(vector<int>& heights) {
        int maxarea = 0;
        for(int i = 0; i < heights.size(); ++i){
            
            for(auto &item : reg){
                auto high = item.first; 
                auto &pii = item.second;
                auto l = pii.first;
                auto &r = pii.second;
                if(high > heights[i]){
                    reg.insert({heights[i], {l, i}});
                    maxarea = max(maxarea, heights[i] *(i - l + 1));
                    reg.erase(reg.find(high), reg.end());
                    
                    break;
                } 
                else if(high <= heights[i]){
                    r = i;
                    maxarea = max(high * (r - l + 1), maxarea);
                }
            }
            if(reg.count(heights[i]) == 0){
                reg.insert({heights[i], {i, i}});
                maxarea = max(maxarea, heights[i]);
            }
        }
        return maxarea;
    }
};
class Solution {
    stack<int> s;
public:
    int largestRectangleArea(vector<int>& heights) {
        int maxarea = 0;
        heights.push_back(0); // 为了计算所有面积
        for(int i = 0; i < heights.size(); ++i){
            if(s.empty()) s.push(i);
            else if(heights[s.top()] < heights[i]) s.push(i);
            else if(heights[s.top()] == heights[i]) s.top() = i; // 如果相邻的高度相同,则更新;因为不更新单调栈中矩阵左边界会扩展更多
            else if(heights[s.top()] > heights[i]){         
                while(!s.empty() && (heights[s.top()] > heights[i])){                    
                    int high = heights[s.top()]; 
                    s.pop();
                    int temparea = ( i - (s.empty() ? -1 : s.top()) - 1) * high;
                    maxarea = max(maxarea, temparea);
                }
                s.push(i);   
            }   
        }
        return maxarea;
    }
};

当然,这里也可以添加一个哨兵,不过没什么影响。

22. Generate Parentheses

思路:

正确的迭代方式是,从左到右的遍历中,每一个正确序列都有左括号的数量大于等于右括号的数量。而每一处符号要么是左括号,要么是右括号,后者符号都有选择的生成即可。

如何便可以递归生成所有符合题意的括号。

Read more

32. Longest Valid Parentheses

思路:

栈验证匹配括号很简单,但是用如何获取多个匹配成功的括号组合长度就很麻烦!

难的是想到,连续的有效括号()())()()只需要记录一个最先未匹配的位置。具体做法是,在栈中存储一个最后没有匹配到的右括号下标。

代码

class Solution {
public:
    int longestValidParentheses(string s) {
        int maxlen = 0; 
        stack<int> st;
        
        st.push(-1); // 压入一个最后未匹配的)。
        for(int i = 0; i < s.size(); ++i){
            if(s[i] == ')'){
                st.pop();
                if(!st.empty()){ // 刚刚的)匹配成功,可以计算最长匹配
                    maxlen = max(maxlen, i - st.top()); 
                }else st.push(i); // 说明该)没有匹配到,是新的最后的最右括号
            }else st.push(i);
        }
        return maxlen;
    }
};

124. Binary Tree Maximum Path Sum

124. Binary Tree Maximum Path Sum

思路:

这题有意思在DP。但算不上hard。

树上的最大路径之和可以转化为一个节点上的左右子树连起来的路径,而左右路径的最大长度分别可以通过左右子树的路径的一部分求得。考虑到子树路径之和小于0的情况,有当前节点和左右子树路径的最大长度为:DP[i] = max(max(DP[i * 2],0), max(DP[i * 2 + 1],0) + val 。同时可以求出,当前节点最长路径,pathsum = max(DP[i * 2],0) + max(DP[i * 2 + 1],0) + val

Read more

42. Trapping Rain Water

42. Trapping Rain Water

思路:

这题蛮hard的,挺考验思路;

思考一下,下雨的过程,水往低处流,一点一点汇聚起来,逐渐逐渐升高水面。我们是否可以在先求出低水平面的水量,在此之上求出高水平面的水量。

43234中就有两个水沟:2上的1*1的水沟,和323上的3*1水沟。

用这种想法,我们只需要遍历得到一个水平面的右边界,记录该水平面的左边界,获取低水平面的高度,填充下新水平面的水量即可。

最小值单调栈S可以帮助我们维持左边界的pos,记S的栈顶元素指向的高度为aa之下的元素指向的高度为b。其性质必然有a > b。遍历到高度c

  • c < a,则对蓄水没有影响。
  • 如果c > b,则三者形成了一个水沟,计算🦁式子见代码,并且该水沟可能可以继续往上“看看”,在适当条件上看看单调栈,循环填充高水位水沟。
  • 如果c==a,则显然应该替换掉a,因为单调栈维持的是等高水沟的最新端,试想33323

经过上述填充过程,单调栈的性质也要维护一下,详细见代码。

Read more

面试题 04.09. BST Sequences LCCI

面试题 04.09. BST Sequences LCCI

懵树下你和我,快乐刷刷题

思路

二叉树的构建,是从根节点开始的,每构建的一个节点,就添加了一个可能两个新扩展节点,我们可以在其中任意选择一个节点新构建,如此递归下去,完成整棵树的构建。

那么,我们需要模拟整棵树的构建遍历过程,用deque存储每次构建时可以选择的节点,递归构造。如果deque为空,说明建构完成,把记录构建顺序的path加入答案即可。建构完成后回溯进行下一个节点的构建。

Read more

331. Verify Preorder Serialization of a Binary Tree

331. Verify Preorder Serialization of a Binary Tree

思路:

  1. 按照字符串提供的数据按前序遍历伪建树,如果用完了所有字符就建树成功。
  2. 前序遍历允许我们的用栈记录当前节点以及之前节点应该生长的分支数,比如碰到一个数字,上一个节点的减一分支数,插入一个当点节点的分支数2。遍历过程中,栈为空或者遍历后,字符数还有剩余,显然建树失败。
Read more

错排问题:年会抽奖

所谓错排问题就是N个1~N数字的序列都恰好不在对应位上,比如序列3 1 2

题目:年会抽奖

今年公司年会的奖品特别给力,但获奖的规矩却很奇葩:

  1. 首先,所有人员都将一张写有自己名字的字条放入抽奖箱中;
  2. 待所有字条加入完毕,每人从箱中取一个字条;
  3. 如果抽到的字条上写的就是自己的名字,那么“恭喜你,中奖了!”
    现在告诉你参加晚会的人数,请你计算有多少概率会出现无人获奖?
Read more