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

109. Convert Sorted List to Binary Search Tree

思路:

链表实际上给出的是二叉树前序的结果,因为AVL树任意左右子树高度不超过1,我们可以选择链表中点,并将链表的长度尽可能一样长的两部分划分到左右子树,所以高度性质可以维持住。

在中序遍历链表,控制子树长度,即可构建符合题意的AVL树。

Read more

450. Delete Node in a BST

思路:

删除一个只有一个子节点,或者没有子节点的节点,比较简单。

删除有两个子节点的节点A,需要把找一个比A大的最小子节点B来替换该A。那么同时也需要递归的删除节点B

Read more

882. Reachable Nodes In Subdivided Graph

思路:

subdivision nodes可以化为路径的长度,将此问题转化为可以用dijstra求解的问题。

每次遍历到最新最短的节点都可以进行求出此点相连的边的可以累加subdivistion nodes的个数,但是需要控制重复累加比较麻烦。最后采用记录下每条边可到达的点,最后统一累计即可。

Read more

146. LRU Cache

思路:

LRU实现中”删除最近最少使用的数据值“表达可能会让人产生误解,更准确的意思是”删除最长时间未使用的数据值“。

硬件的实现可以用每次更新和添加元素A,累加除A之外的所有元素的计数值。

Read more

647. Palindromic Substrings

647. Palindromic Substrings1

思路:

Manacher算法:

回文字符串的判断方式方式会从中心点从发向外不断扩展,Manacher算法给出了缩减了字符串判断回文的重复步骤。其核心思想在于,一段回文s上的呈对称状的左右AB两点,B点的最小回文长度可以通过A点的回文长度和Bs边右边界的长度最小值决定。另外,为了改变回文串长度为偶数和奇数的不同,在每个字符前和后都插入一个#,如此插入后的T的最长回文串半径d,与S最长回文串半径k有, k = [d / 2]

[]向下取整。

Read more

227. Basic Calculator II

227. Basic Calculator II

思路

经典的中缀转后缀练手题,但是我偏不。

在遍历字符串把数字和运算符存储到一个数字栈和运算栈中,考虑到运算顺序是乘除>加减,且左边>右边,所以在压入新运算符op前把栈中优先级大于等于op的运算法弹出,并计算。

遍历完了运算栈可能还有运算符,逆向计算即可。最后数据栈弹出结果就完事。

代码

class Solution {
public:
    using ull = unsigned long long;
    ull func(char c, ull num1, ull num2){
        if(c == '+') return num1 + num2;
        if(c == '-') return num1 - num2;
        if(c == '*') return num1 * num2;
        if(c == '/') return num1 / num2;
        return 0;
    }
    int calculate(string s) {
        s += ']';
        stack<char> op;
        stack<ull> num;
        map<char, int> pri{{'+', 1},{'-', 1},{'*', 2},{'/', 2}};
        ull cal = 0;
        for(auto c : s){
            if(isdigit(c)) cal = cal * 10 + c - '0';
            else{
                if(c == ' ') continue;
                // cout << c << ' ' << cal << endl; 
                num.push(cal); 
                cal = 0;
                if(c == ']') continue;
                
                while(op.size() &&  pri[c] <= pri[op.top()]){
                    int num2 = num.top(); num.pop();
                    int num1 = num.top(); num.pop();
                    num.push( func(op.top(), num1, num2) );
                    op.pop();
                }
                op.push(c);
            }
        }
        // cout << num.size() << ' ' << op.size() << endl;
        while(op.size()){
            int num2 = num.top(); num.pop();
            int num1 = num.top(); num.pop();
            num.push( func(op.top(), num1, num2) );
            op.pop();
        }
        return num.top();


    }
};

5674. Largest Merge Of Two Strings

周赛的题目3

算法:

明显是贪心,但我贪错了!

一开始想着比较两个字符创的开头字符,选择字典序大的字符加入。如果两个字符相等就放着比较下一个,直到有不同的就可以全部加入。然后wa了4发。

正确的思路是:比较剩下的字符串,选择字典序大的字符创的的首个字符加入即可。

Read more