阅读 3345

五分钟带你领略: 腾讯半年来出现最频繁的算法之一——字符串解码

简要介绍

大家好,我是神三元。今天给大家分享一道有意思的算法题,在leetcode平台上截图如下:

近半年来广受各大公司的青睐,出现非常频繁,在腾讯仅仅半年就出现了17次,如果说给满分给5颗星的话,那么这一题算得上实打实的五星题。

那究竟是什么让这个算法从众多的leetcode题库中脱颖而出,在各个大厂中一而再、再而三地出现呢?

接下来,就让我们解开它的奥秘,领略这个算法到底多么经典!

开局思路

刚开始拿到这道题,看到括号匹配问题,直觉上就想到了利用栈先进后出的性质,来完成前后字符串的拼接。但是后来尝试了很久,发现问题并没有那么简单,主要归纳如下:

  1. 在中括号层次比较深的情况下,如何完成回溯,将当前的字符与之前的字符拼接。
  2. 当出现次数并不是个位数,而是类似100,1000 这样的多位数,如何来解析。

接着,我们利用不同的方法,来一步步来解决这两个棘手的问题。

利用栈

说一下整体思路。扫描一遍字符串,针对不同的字符进行不同的处理:

首先有两个重要的变量,表示重复次数的 multi 值和累积字符串 res。

    1. 遇到数字, 直接参加计算,累积multi值。
    1. 遇到普通字符(除[,]外),累积到 res 后面。
    1. 遇到 [, 将之前累积的字符串res压栈,当前multi值压到另一个栈。然后当前 multi归零,res置空。
    1. 遇到 ], 取出栈中multi值,将当前的 res 字符串重复 multi 次,赋值给临时变量tmp,然后让另一个存放累积字符串的栈中弹出栈顶元素和当前的tmp拼接,作为最新的累积字符串赋值给res。

如果现在没看懂,没有关系,给出代码就明白了,让大家直观感受一下:

var decodeString = function (s) {
  // 存放 【重复次数】 的栈
  let countStack = [];
  // 存放 【累积字符串】 的栈
  let resStack = [];
  // 用来累积的字符串 res
  let res = "";
  // 表示重复次数
  let multi = 0;
  for (let i = 0; i < s.length; i++) {
    let cur = s.charAt(i);
    if (cur == '[') {
      // 双双压栈,保存了当前的状态
      countStack.push(multi);
      resStack.push(res);
      // 纷纷置空,准备下面的累积
      multi = 0;
      res = "";
    } else if (cur == ']') {
      // 遇到 ],表示累积结束,要算账了。
      // 【当前的串出现多少次】还保存在栈中,把它取出来
      let count = countStack.pop();
      let temp = "";
      // 让 [ 和 ] 之间的字符串(就是累积字符串res)重复 count 次
      for(let i = 0; i < count; i++) {
        temp += res;
      }
      // 和前面已经求得的字符串进行拼接
      res = resStack.pop() + temp;
    } else if (cur >= '0' && cur <= '9') {
      // multi累积
      multi = multi * 10 + (cur - '0');
    } else {
      // 字符累积
      res += cur;    
    }
  }
  return res;
};
复制代码

利用递归程序

递归的思路就容易一点,一旦遇到[,立马进入新的递归程序,扫描到对应的]为止。也就是说,凡是遇到括号,括号里面的事情,全部交给子程序完成。建议大家看完代码再来体会这句话:

var decodeString = function (s) {
  // 从第 0 个元素开始处理
  return dfs(s, 0);
};

let dfs = (s, n) => {
  let res = "";
  // 保存起始索引
  let i = n;
  // 同上,表示重复的次数
  let multi = 0;
  while(i < s.length) {
    let cur = s.charAt(i);
    // 遇到数字,累积 multi 值
    if(cur >= '0' && cur <= '9') 
      multi = multi * 10 + (cur - '0');
    else if(cur === '[') {
      // 划重点!给子程序,把对应的 ] 索引和括号包裹的字符串返回
      // 即tmp 的格式为 [索引,字符串]
      let tmp = dfs(s, i + 1);
      // 这样下次遍历就是从对应的 ] 后面遍历了,因为当前已经把括号里面的处理完了
      i = tmp[0];
      // 需要重复的字符串已经返回来了
      let repeatStr = tmp[1];
      for(let j = 0; j < multi; j++) {
        res += repeatStr;
      }
      // 当前已经把括号里面的处理完,multi 置零,为下一轮遍历准备
      multi = 0;
    }else if(cur === ']') {
      // 遇到了对应的 ] ,返回 ] 索引和括号包裹的字符串
      return [i, res];
    } else {
      res += cur;
    }
    // 继续遍历
    i++;
  }
  return res;
}
复制代码

两种方法都顺利通过。

估计做完这道题,仔细回味一下,也能够发现这道题的经典之处了:

  1. 考察对栈这种数据结构的理解
  2. 考察字符串的基本操作,涉及对编程语言的考察
  3. 考察对递归和回溯思想的理解。(其实字符串拼接就是向前回溯的过程)

做完这道题,是不是刷新了自己对于栈这种数据结构的认知呢?

它其实具有着天然的递归性质,只是我们初学的时候,容易先入为主地把这种先入后出的数据结构想的太简单。当然它还有其他神奇的功能,我们放在下一期来分享。

❤️ 看完两件事

如果你觉得这篇内容对你挺有启发,我想邀请你帮我两个小忙:

  1. 点赞,让更多的人也能看到这篇内容(收藏不点赞,都是耍流氓 -_-)

  2. 关注公众号「前端三元同学」,每日坚持灵魂之问,遇见更好的自己!

关注下面的标签,发现更多相似文章
评论