关于javascript:动图演示头条和滴滴的一道面试题smartRepeat-函数

8次阅读

共计 2857 个字符，预计需要花费 8 分钟才能阅读完成。

有幻想，有干货，微信搜寻 【大迁世界】 关注这个在凌晨还在刷碗的刷碗智。

本文 GitHub https://github.com/qq449245884/xiaozhi 已收录，有一线大厂面试残缺考点、材料以及我的系列文章。

在解说这道题之前咱们先来看下一个数据结构：栈，因为咱们须要用栈来解决这道题。

栈（stack）又名堆栈，它是一种运算受限的线性表，仅 在表尾能进行插入和删除操作。这一端被称为栈顶，绝对地，把另一端称为栈底。

向一个栈插入新元素又称作进栈、入栈或压栈；从一个栈删除元素又称作出栈或退栈。

后进先出（LIFO）特点：栈中的元素，最先进栈的必然是最初出栈，后进栈的肯定会先出栈。

JavaScript 中，栈能够用数组模仿。须要限度只能应用 push() 和pop()，不能应用 unshift() 和shift()。即，数组尾是栈顶。

当然，能够用面向对象等伎俩，将栈封装的更好。

这是头条和滴滴的一道面试题，题目是这样的：

试编写“智能反复”smartRepeat 函数，实现：

将 3[abc] 变为abcabcabc
将 3[2[a]2[b]] 变为 aabbaabbaabb
将 2[1[a]3[b]2[34[d]]] 变为abbbcccddddcccddddabbbcccddddcccdddd

不必思考输出字符串是非法的状况，比方：

2[a3[b]]是谬误的，应该补一个 1，即 2[1[a]3[b]]
[abc]是谬误的，应该补一个 1，即 1[abc]

大家一看到这题目，应该想到的用递归的形式来做，实际上这道题用递归是比拟难的。也是能做，但相比栈，栈的形式会简略的多。

初学者大坑：栈的题目和递归十分像，这类题目给人的感觉都是用递归解题。信念满满入手开始写了，却发现递归怎么都递归不进去。此时就要想到，不是用递归，而是用栈。

这道题目咱们能够应用两个栈来解，第一个栈寄存数字，第二个栈寄存字符串

这时候能够发现咱们指针只须要遍历一次就行了，怎么看？

规定是这样的子：遍历到数字就把数字压栈

而后持续遍历，这时遍历到方括号，或者说是遍历到数字和方括号，那么咱们就把另一个栈放入一个空字符串 ''。

而后下移，遇到 3，同样也是压栈：

而后下移，遇到方括号了，压入一个空字符串 ''

而后下移，遇到字母 a，那么遇到字母是什么规定呢，如图中所示：

而后下移，遇到 ], 留神，遍历到完结的右大括号的时候，是一个十分重要的工夫，那这个规定又是啥呢，如下图所示：

是不是有点看不懂了，那么咱们重头在跑一次

而后下移遇到 4[, 别离把数字 4 和空字符串压入：

而后下移遇到 1[, 别离把数字 1 和空字符串压入：

而后下移遇到 b，压入：

而后下移，遇到结束符 ]，别离要 1 和 ‘b’ 弹出来，此时在把 ‘b’ 反复一遍后拼接到第二个栈顶元素

而后下移，遇到 2，同样的操作：

而后下移遇到 c，间接写入：

而后下移，遇到结束符 ]，别离把 2 和 ‘c’，弹出，此时在把 ‘c’ 反复二遍后拼接到第二个栈顶元素

而后下移，遇到倒数第二个结束符 ]，别离把 4 和 ‘bccc’，弹出，此时在把 ‘bccc’ 反复四四遍后拼接到第二个栈顶元素

而后下移，遇到最初一个结束符 ]，别离把 2 和 ‘aaabccbccbccbcc’，弹出，此时在把 ‘aaabccbccbccbcc’ 反复两遍，这时个就不必拼到上一个元素了，因为曾经是最初一个了：

这个答案是不是就是咱们最初的答案了，神奇吧~

这时个咱们在按下面的流程来演示一上这题：

2[1[a]3[b]2[34[d]]] 变为abbbcccddddcccddddabbbcccddddcccdddd。

创立 index.js，输出以下内容：

// 试编写“智能反复”smartRepeat 函数，实现：// 将 3[abc]变为 abcabcabc
// 将 3[2[a]2[b]]变为 aabbaabbaabb
// 将 2[1[a]3[b]2[34[d]]]变为 abbbcccddddcccddddabbbcccddddcccdddd

function smartRepeat(templateStr) {
  // 指针
  var index = 0;
  // 栈 1，寄存数字
  var stack1 = [];
  // 栈 2，寄存长期字符串
  var stack2 = [];
  // 残余局部
  var rest = templateStr;

  while (index < templateStr.length - 1) {
    // 残余局部
    rest = templateStr.substring(index);

    // 看以后残余局部是不是以数字和[结尾
    if (/^\d+\[/.test(rest)) {
      // 失去这个数字
      let times = Number(rest.match(/^(\d+)\[/)[1]);
      // 就把数字压栈，把空字符串压栈
      stack1.push(times);
      stack2.push("");
      // 让指针后移，times 这个数字是多少位就后移多少位加 1 位。// 为什么要加 1 呢？加的 1 位是[。index += times.toString().length + 1;} else if (/^\w+\]/.test(rest)) {
      // 如果这个字符是字母，那么此时就把栈顶这项改为这个字母
      let word = rest.match(/^(\w+)\]/)[1];
      stack2[stack2.length - 1] = word;
      // 让指针后移，word 这个词语是多少位就后移多少位
      index += word.length;
    } else if (rest[0] == "]") {// 如果这个字符是]，那么就①将 stack1 弹栈，②stack2 弹栈，③把字符串栈的新栈顶的元素反复刚刚弹出的那个字符串指定次数拼接到新栈顶上。let times = stack1.pop();
      let word = stack2.pop();
      // repeat 是 ES6 的办法，比方 'a'.repeat(3)失去 'aaa'
      stack2[stack2.length - 1] += word.repeat(times);
      index++;
    }

    console.log(index, stack1, stack2);
  }

  // while 完结之后，stack1 和 stack2 中必定还残余 1 项。返回栈 2 中剩下的这一项，反复栈 1 中剩下的这 1 项次数，组成的这个字符串。如果剩的个数不对，那就是用户的问题，方括号没有闭合。return stack2[0].repeat(stack1[0]);
}

var result = smartRepeat("3[2[3[a]1[b]]4[d]]");
console.log(result);

~ 完，我是小智，刷牛客网去了，咱们下期见~

代码部署后可能存在的 BUG 没法实时晓得，预先为了解决这些 BUG，花了大量的工夫进行 log 调试，这边顺便给大家举荐一个好用的 BUG 监控工具 Fundebug。