成人免费xxxxx在线视频软件_久久精品久久久_亚洲国产精品久久久_天天色天天色_亚洲人成一区_欧美一级欧美三级在线观看

頭條和滴滴的一道面試題:smartRepeat 函數

開發 前端
棧(stack)又名堆棧,它是一種運算受限的線性表,僅在表尾能進行插入和刪除操作。這一端被稱為棧頂,相對地,把另一端稱為棧底。

[[402509]]

在講解這道題之前我們先來看下一個數據結構:棧,因為我們需要用棧來解決這道題。

棧(stack)又名堆棧,它是一種運算受限的線性表,僅在表尾能進行插入和刪除操作。這一端被稱為棧頂,相對地,把另一端稱為棧底。

向一個棧插入新元素又稱作進棧、入棧或壓棧;從一個棧刪除元素又稱作出棧或退棧。

后進先出(LIFO)特點:棧中的元素,最先進棧的必定是最后出棧,后進棧的一定會先出棧。

JavaScript中,棧可以用數組模擬。需要限制只能使用push()和pop(),不能使用unshift()和shift()。即,數組尾是棧頂。

當然,可以用面向對象等手段,將棧封裝的更好。

面試題

這是頭條和滴滴的一道面試題,題目是這樣的:

試編寫“智能重復”smartRepeat函數,實現:

  • 將 3[abc] 變為abcabcabc
  • 將 3[2[a]2[b]] 變為 aabbaabbaabb
  • 將 2[1[a]3[b]2[3[c]4[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[3[c]4[d]]] 變為abbbcccddddcccddddabbbcccddddcccdddd。

代碼實現

創建 index.js,輸入以下內容:

  1. // 試編寫“智能重復”smartRepeat函數,實現: 
  2. // 將3[abc]變為abcabcabc 
  3. // 將3[2[a]2[b]]變為aabbaabbaabb 
  4. // 將2[1[a]3[b]2[3[c]4[d]]]變為abbbcccddddcccddddabbbcccddddcccdddd 
  5.  
  6. function smartRepeat(templateStr) { 
  7.   // 指針 
  8.   var index = 0; 
  9.   // 棧1,存放數字 
  10.   var stack1 = []; 
  11.   // 棧2,存放臨時字符串 
  12.   var stack2 = []; 
  13.   // 剩余部分 
  14.   var rest = templateStr; 
  15.  
  16.   while (index < templateStr.length - 1) { 
  17.     // 剩余部分 
  18.     rest = templateStr.substring(index); 
  19.  
  20.     // 看當前剩余部分是不是以數字和[開頭 
  21.     if (/^\d+\[/.test(rest)) { 
  22.       // 得到這個數字 
  23.       let times = Number(rest.match(/^(\d+)\[/)[1]); 
  24.       // 就把數字壓棧,把空字符串壓棧 
  25.       stack1.push(times); 
  26.       stack2.push(""); 
  27.       // 讓指針后移,times這個數字是多少位就后移多少位加1位。 
  28.       // 為什么要加1呢?加的1位是[。 
  29.       index += times.toString().length + 1; 
  30.     } else if (/^\w+\]/.test(rest)) { 
  31.       // 如果這個字符是字母,那么此時就把棧頂這項改為這個字母 
  32.       let word = rest.match(/^(\w+)\]/)[1]; 
  33.       stack2[stack2.length - 1] = word; 
  34.       // 讓指針后移,word這個詞語是多少位就后移多少位 
  35.       index += word.length; 
  36.     } else if (rest[0] == "]") { 
  37.       // 如果這個字符是],那么就①將stack1彈棧,②stack2彈棧,③把字符串棧的新棧頂的元素重復剛剛彈出的那個字符串指定次數拼接到新棧頂上。 
  38.       let times = stack1.pop(); 
  39.       let word = stack2.pop(); 
  40.       // repeat是ES6的方法,比如'a'.repeat(3)得到'aaa' 
  41.       stack2[stack2.length - 1] += word.repeat(times); 
  42.       index++; 
  43.     } 
  44.  
  45.     console.log(index, stack1, stack2); 
  46.   } 
  47.  
  48.   // while結束之后,stack1和stack2中肯定還剩余1項。返回棧2中剩下的這一項,重復棧1中剩下的這1項次數,組成的這個字符串。如果剩的個數不對,那就是用戶的問題,方括號沒有閉合。 
  49.   return stack2[0].repeat(stack1[0]); 
  50.  
  51. var result = smartRepeat("3[2[3[a]1[b]]4[d]]"); 
  52. console.log(result); 

 ~完,我是小智,我們下期見~

 

責任編輯:姜華 來源: 大遷世界
相關推薦

2024-10-11 17:09:27

2018-03-06 15:30:47

Java面試題

2011-05-23 11:27:32

面試題面試java

2009-08-11 14:59:57

一道面試題C#算法

2023-02-04 18:24:10

SeataJava業務

2009-08-11 10:12:07

C#算法

2017-11-21 12:15:27

數據庫面試題SQL

2022-04-08 07:52:17

CSS面試題HTML

2009-08-11 15:09:44

一道面試題C#算法

2023-08-01 08:10:46

內存緩存

2011-06-14 09:12:03

JavaScript

2021-10-28 11:40:58

回文鏈表面試題數據結構

2022-02-08 18:09:20

JS引擎解析器

2015-09-02 14:09:19

面試題程序設計

2017-03-10 09:33:16

JavaScript類型

2011-03-02 10:58:16

SQL server入門面試題

2021-03-16 05:44:26

JVM面試題運行時數據

2017-09-13 07:15:10

Python讀寫文件函數

2021-03-27 10:59:45

JavaScript開發代碼

2018-02-01 16:26:44

面試題static變量
點贊
收藏

51CTO技術棧公眾號

主站蜘蛛池模板: 99re在线免费视频 | 精品国产欧美 | 成人av播放 | 亚洲精品免费在线 | 在线色 | 国产一区免费 | 日韩一二区 | 黑人巨大精品欧美一区二区一视频 | 91毛片在线看 | 欧美福利一区 | 九一在线 | 欧美精品久久一区 | 天天操夜夜操 | 久久国产免费 | 91精品国产日韩91久久久久久 | 亚洲综合热 | 欧美一区二区在线观看 | 久久高清免费视频 | 97热在线| 久久99精品久久久久蜜桃tv | 午夜视频在线观看网址 | 综合久久综合久久 | av天天干| 国产偷录叫床高潮录音 | 亚洲精品一区二区三区蜜桃久 | 一级毛片免费视频观看 | 久久精彩视频 | 一区二区三区av | 很黄很污的网站 | 中文字幕av网 | 久久国产美女视频 | 久久一| 亚洲欧美视频 | 久久精品亚洲成在人线av网址 | 国产精品久久久久久久久免费软件 | 一区二区免费在线视频 | 国产精品成人一区二区三区夜夜夜 | 日韩网站在线观看 | 91久久久久 | www.蜜桃av| 欧美激情精品久久久久久变态 |