kiner算法刷题记（二）：递归与栈（解决表达式求值问题）

系列文章导引

• Kiner算法刷题记（一）：链表和链表思想

思考

• 要做一件事情，我们可以+1，也可以入栈，这只是一种思维方式的问题，本质上原理都是一样的
• 同理，要完成一件事情，我们可以-1，也可以出栈
• (()())这样我们其实可以理解为外层的一对括号代表一个大任务,但我们要完成这个大任务是有前置条件的，那就是完成里面的两个小任务，也就是中间的两对括号。因此，类似括号配对的这种思维方式，其实不仅仅用于对于一些字符串或html之类代码的解析上，还可以泛化为以下几种场景：
  • 一对()可以看成一个完整的事件，而(()())则可以看成具有完全包含关系的任务执行细节问题的处理。
  • 函数的执行，如：(()())我们可以把最外层的括号看成一个大函数Fn0，而在这个大函数Fn0中有调用了Fn1和Fn2，当我两个子函数执行完后，我们的Fn0也就执行完了。
  • 二叉树的深度优先遍历结果，即DFS。(()())可看成是一个根节点下有两个子节点

栈的典型应用场景

• 操作系统的线程栈（线程空间）

  • 当我们新申请一个线程空间时，Mac中线程栈的大小默认是8192kb,即8M左右。

    # mac中查看线程栈默认大小的命令
    ulimit -a
    

  • 当我们的函数调用层数过深时，我们再线程栈中压入的变量过多，超出了8192kb时，就会出现爆栈的情况

• 表达式求值3 + 5(如：逆波兰表达式求值)

  • 思考：使用递归方式解决表达式求值和使用栈解决表达式求值有没有什么区别

    • 答案：没有，其实递归本质上使用了系统给我们提供的变量栈。

  • 解决思路：将3 + 5在思维逻辑层面把它看做是以+为根节点，左子树为3，右子树为5的一个二叉树，即我们常说的：表达式树。

  • 表达式树的概念：通常以运算符作为根节点，计算因子做为其子树的属性结构

  • 例如：3 * (4 + 5)，这个本质上是一个乘法表达式，后面的加法本质上是我们要计算这个乘法表达式之前要解决的一个子问题，因此，我们可以在逻辑层面把上面的公式转换成以下二叉树：

            [ * ]
    [ 3 ]              [ + ]
    
                [ 4 ]        [ 5 ]
    
    

刷题

LeetCode 682：棒球比赛

解题思路

这道题是栈中比较基础题，主要利用了分治思想和栈的特性。大概的解题思路是这样的，循环我们的计分列表：

• 在遇到数字时将数字压入栈中。

• 当遇到+时，说明需要把最近两次得分相加，那我们就可以把栈顶元素和栈顶下一位元素拿出来相加（要注意，由于栈的特性，我们只能从栈顶获取元素，所以，要获取栈顶的下一位元素，我们需要先将栈顶弹出来，再获取，最后把栈顶元素重新压入栈中，并压入两个元素相加之和）。

• 如果遇到D时，说明我们需要把最近的一个积分乘以2，然后再将结果压入栈中。

• 如果遇到C时，说明上一次的计分无效，我们需要把栈顶元素弹出

• 当整个循环结束后，我们的栈中就存储了我们的整个计分结果，我们只需要将栈中元素依次弹出，并累加就是我们想要的答案了。

代码演示

/*
 * @lc app=leetcode.cn id=682 lang=typescript
 *
 * [682] 棒球比赛
 */

// @lc code=start
function calPoints(ops: string[]): number {
    // 用一个数组模拟栈，用来存储得分数据
    const stack: number[] = [];
    // 使用分治思想，对不同的情况采用不同的方式处理
    for(const op of ops) {
        switch(op) {
            case "+":
                // 遇到加号时，代表要将栈最上面的两个结果相加作为结果再压入栈中
                // 先将栈顶元素弹出，不然无法获取栈顶元素下一个元素
                const a = stack.pop();
                // 获取当前栈顶元素
                const b = stack[stack.length-1];
                // 再将原先的栈顶元素重新压入栈中，并将a+b的结果也压入栈中
                stack.push(a, a+b);
                break;
            case "D": 
                // 遇到D时，索命需要将栈顶元素乘以二再压入栈中
                const top = stack[stack.length-1];
                stack.push(top*2);
                break;
            case "C": 
                // 遇到C时，说明最后一次计分无效，将栈顶元素弹出
                stack.pop();
                break;
            default: 
                // 不是上述任一一个情况，说明是分数，则把分数压入栈中
                stack.push(parseInt(op));
        }
    }
    // 循环结束后，只需要将栈中的元素依次弹出并累加就是总分数了
    let num = 0;
    while(stack.length!==0) {
        num += stack.pop();
    }
    return num;
};
// @lc code=end

LeetCode 844: 比较含退格的字符串

解题思路

这道题也是典型的栈逻辑题，我们只需要将除了空字符串和#之外的其他字符串压入栈中，遇到#号时，我们就把栈顶元素弹出，这样就可以获得一串最终的字符串，最后，我们只需要比较两个原始字符串通过上述操作后的最终字符串是否相等即可

代码演示

/*
 * @lc app=leetcode.cn id=844 lang=typescript
 *
 * [844] 比较含退格的字符串
 */

// @lc code=start
function toRealString(s: string): string {
    // 用于存储结果字符的栈
    const stack = [];
    for(const char of s) {
        // 遇到空字符串就跳过
        if(char === " ") continue;
        // 遇到遇到了#，说明需要退格，就把栈顶元素弹出
        else if(char === "#") stack.pop();
        // 否则就是我们真实的字符，直接压入栈中
        else stack.push(char);
    }
    // 直接将栈转换为字符串，方便后续比较
    return stack.toString();
}

function backspaceCompare(S: string, T: string): boolean {
    return toRealString(S) === toRealString(T);
};
// @lc code=end

LeetCode 1021: 删除最外层的括号

解题思路

这道题是一道相当不错的栈思维题。为什么说是栈思维题呢？因为我们实际实现的时候，并没有使用到栈这样的数据结构，但却使用了栈的思维，即先进后出、后进先出。大家可以回去本文头部看一下我们思考当中的内容，应该就有一些思路了，我们可以使用+1来代表入栈，使用-1来代表出栈，而当我们的计数器结果为0时，说明已经栈空。那么，有了这一个思路打底，我们再来看看详细的解题思路吧。这道题就直接把解题思路写入代码注释当中，这样比较容易理解。

代码演示

/*
 * @lc app=leetcode.cn id=1021 lang=typescript
 *
 * [1021] 删除最外层的括号
 */

// @lc code=start
function removeOuterParentheses(S: string): string {
    // 虽然没有使用到栈的数据结构，但是使用到了栈的头指针思想
    
    let res = "";
    // 其中j代表的是第一个最外层括号的起始位置，count是左括号和右括号的差值
    // 当count为0的时候，就说明我们左括号和右括号配对成功了
    for(let i=0,j=0,count=0;i<S.length;i++) {
        // 遇到左括号则count加1
        if(S[i] === '(') ++count;
        // 右括号则count减一，这样一对括号就抵消了
        else --count;
        // 如果左右括号没有抵消，则继续下一次循环
        if(count !== 0) continue;
        // 如果左右括号抵消了，则我们需要把当前找到的括号序列的最外层的括号取消
        // 如: (()())(())
        // 我们可以吧上面的括号序列拆成两部分
        // (()()) 和 (())
        // 当我们第一次遇到左右括号抵消，也就是count为0时
        // 其实我们就已经找到了一个待处理的子序列了
        // 我们只需要将(()())最外层的括号去掉即可
        // 已知当前i已经走到了上述子序列的最后一个位置，也就是最外层右括号的位置
        // 而j是我们记录的最外层的左括号，那么，我们要截取调外层括号的起始点和终点应该为：

        // 注意，substr第二个参数是字符串的长度，
        // i-j+1为原本子序列的长度（为什么要加1呢？因为i和j都是下标，所以要转成长度的话，需要加1），
        // 因为我们要删除一对左右括号，所以要减2
        // substr(j+1, i - j + 1 - 2)
        // substr(j+1, i - j -1)
        res += S.substr(j+1, i - j - 1);
        // 截取并拼接之后，让起始位置移动到当前子序列最后一位的下一位，继续下一轮的处理
        j = i + 1;
    }
    return res;
};
// @lc code=end

LeetCode 636: 函数的独占时间

解题思路

这道题其实主要有两个要点，只要把这两个要点解决，那这道题也就简单了。

1. 怎么有效的判断函数的开始与结束的编辑

   要界定开始和结束其实很简单，直接把传输的字符串进行切割便可获取当前的状态是开始还是结束，不过需要注意的是，我们需要维护一个数组用来模拟栈操作，数组的索引其实就是对应了函数的id

2. 函数开始时，从上一次到当前位置的时间要算在上一个函数头上还是算在当前函数头上，函数结束时呢？

   我们可以就简单画一个图示意一下：

   # start0和end0分别代表函数1的开始和结束，start1和end1分别代表函数2的开始和结束
   |___________________|___________________|___________________|
   start0           start1								end1								 end0
   |___________________||——————————————————||——————————————————|
   				time1									time2							time3
   

   从上面的图中，我们可以看出，start0到start1的距离，试试应该是函数1的独立运行时间，所以，当我们到了start1时，应该把时间算到函数1头上，即，我们需要把time1加到函数1的时间fnTime1中，即：fnTime1 += time1,当到了end1的时候,显而易见，我们time2的时间应该是函数2的执行时间，即fnTime2 += time2，最后，我们到达了end0，很显然，end1到end0的时间也是函数1独占的时间，再累加上去就可以了fnTime1 = time3。

代码演示

/*
 * @lc app=leetcode.cn id=636 lang=typescript
 *
 * [636] 函数的独占时间
 */

// @lc code=start
function exclusiveTime(n: number, logs: string[]): number[] {
    // 其实就是用栈去模拟函数的执行过程，需要搞清楚的是，遇到开始执行时，
    // 我们的执行时间应该要加个上一个函数的执行时间，而遇到结束状态是，
    // 我们的时间才是加给当前函数的执行时间

    // 初始化一个结果数组，长度为函数的数量，并为其初始填充0作为每个项的初始值
    const res: number[] = new Array<number>(n);
    res.fill(0);
    // 维护一个用于存储胡函数id的栈
    const stack: number[] = [];

    // pre用于记录上一次操作的时间
    for(let i=0,pre=0;i<logs.length;i++) {
        // 将id，status，time结构出来，并将id和time转成整数
        const [sid, status, stime] = logs[i].split(':');
        const last = stack.length - 1;
        let id = parseInt(sid);
        let time = parseInt(stime);
        console.log(id, status, time);

        // 28~33行是针对36~55行的一个优化，本质上是一样的，但是代码更加简洁，不过较难理解
        let offset = (status === 'end'? 1 : 0);// 遇到结束状态时，计算时间需要额外加上1
        if(stack.length!==0) res[stack[last]] += time - pre + offset;
        pre = time + offset;

        (status === 'start') ? stack.push(id) : stack.pop();


        // 如果是开始状态
        // if(status === 'start') {
        //     // 当栈不为空时，我们需要为栈顶元素加上当前时间遇上一个时间的差值，因为一旦遇到任务开始
        //     // 状态，就说明，上一个函数的执行被挂起，时间暂停计数，那么，当前时间戳减去上一个时间就是
        //     // 我们上一个函数独立运行的一段时间
        //     if(stack.length!==0) {
        //         res[stack[last]] += time - pre;
        //     }
        //     // 把当前时间赋值给上一个时间，方便下一轮进行运算
        //     pre = time;
        //     // 遇到开始状态，都需要把当前函数的id压入栈中
        //     stack.push(id)
        // } else {
        //     // 遇到结束状态，我们需要计算出当前函数的执行时间，就拿当前时间减去函数开始执行的时间加1即可
        //     res[id] += time - pre + 1;
        //     // 上一个时间修正为当前时间加1
        //     pre = time + 1;
        //     // 因为遇到了结束状态，所以栈顶元素出栈，当前函数已经处理完毕
        //     stack.pop();
        // }
    }

    return res;
};
// @lc code=end

LeetCode 20：有效的括号

解题思路

这道题我们也是需要将我们的左括号压入栈中，遇到括号时弹出栈顶元素并对比当前右括号是否与弹出的左括号配对，若配对，则说明合法，否则不合法。

PS: 下面给出的两种解决方案，本质上其实是一样的，只是第二总方案是采用计数器的方式实现，目的是为了让大家不要太过于拘泥于栈这样的数据结构，而是要把思维发散出来，学会栈的思维而非栈的结构。这一点跟之前本人写的关于俩表的系列文章中的链表思维是一样的，感兴趣的同学也可以去看一下。Kiner算法刷题记（一）：链表和链表思想

代码演示

• 方案一：

  /**
   * @param {string} s
   * @return {boolean}
   */
  var isValid = function(s) {
  
      if(s.length===0){
          return true;
      }
      
      let left = "([{";
      let right = ")]}";
  
      let stack = new Stack();
      for(let i=0;i<s.length;i++){
          let char = s[i];
          if(left.indexOf(char)>=0){
              stack.push(char);
          }else if(right.indexOf(char)>=0&&left.indexOf(stack.head())===right.indexOf(char)){
              stack.pop();
          }else{
              return false;
          }
      }
  
      return stack.empty();
  };
  function Stack(){
      let arr = [];
      this.push = function(val){
          arr.push(val);
      }
      this.pop = function(){
          return arr.pop();
      }
      this.tail = function(){
          return arr[0];
      }
      this.head = function(){
          return arr[arr.length-1]
      }
      this.size = function(){
          return arr.length;
      }
      this.empty = function(){
          return this.size()===0;
      }
  }
  

• 方案二：

  /*
   * @lc app=leetcode.cn id=20 lang=typescript
   *
   * [20] 有效的括号
   */
  
  // @lc code=start
  function isValid(s: string): boolean {
      // 有多少种括号，就定义多少个计数器
      let count1 = 0, count2 = 0, count3 = 0;
      // 分别定义左括号集合和右括号集合，方便之后出现括号数量合法，但括号嵌套层级不合法的情况
      let subStrLeft = '({[';
      let subStrRight = ')}]';
      // 用于存储存储括号类型对应的索引，如是{的话，那么他在左括号集合中的索引应该是1，当我们找到下一个右括号时，
      // 只需要看一下下一个右括号在右括号集合中的索引是否也为1即可
      let idxStack = [];
      for(let i=0;i<s.length;i++) {
          // 获取当前字符在左括号集合中的索引
          let lIdx = subStrLeft.indexOf(s[i]);
          // 获取当前字符在右括号集合中的索引
          let rIdx = subStrRight.indexOf(s[i]);
          // 如果当前字符在左括号集合中能找到，说明当前字符是左括号中的一个，把左括号的索引压入栈中
          if(lIdx!==-1) idxStack.push(lIdx);
          // 如果当前字符在右括号集合中能找到，说明当前字符是右括号中的一个，把就可以把栈顶的最近一个
          // 左括号的索引弹出，并判断是否与当前右括号的索引配对，如果不配对，则说明非法，直接返回false
          if(rIdx!==-1 && rIdx!==idxStack.pop()) return false;
          // 也遇到左括号，分别累加不同类型左括号的数量
          if(lIdx === 0) ++count1;
          else if (lIdx === 1) ++count2;
          else if (lIdx === 2) ++count3;
          // 遇到右括号，分别累加右括号的数量
          if(rIdx === 0) --count1;
          else if (rIdx === 1) --count2;
          else if(rIdx === 2) --count3;
          // 每一轮循环都要判断一下，右括号是否比左括号多，即计数器是否小于0，
          // 因为一个合法的括号序列，在遍历的过程中，左括号永远是大于或等于右括号数量的
          if(count1<0 || count2<0 || count3<0) return false;
      }
  
      // 循环结束时，只要所有的计数器都为0，即代表所有的左右括号都被抵消掉了，则说明合法，否则不合法
      return count1===0&&count2===0&&count3===0;
  };
  // @lc code=end