Redmi Pad評測：紅米充滿野心的一次嘗試
從Note系列到K系列，從藍牙耳機到筆記本電腦，紅米不知不覺之間也已經形成了自己頗有競爭力的產品體系，在中端和次旗艦市場上甚至要比小米新機的表現來得更好，正所謂“大丈夫生居
9月又是換工作的最佳時機。我幻想著只要換一份工作，就可以離開這個“破碎的地方”，賺更多的錢，做最舒服的事情，但事與愿違。
最近，一名女學生正在換工作。面試前她準備了很多問題。我以為她很有信心，結果卻在算法上吃了大虧。
什么樣的算法題能讓面試官對一個女孩說出這么狠的話：你工作了3年了，這道算法題你都解不出來？
這是LeetCode上的一道算法題，旨在考察考生對“棧”數據結構的熟悉程度。我們來看一下。
給定一個僅包含字符‘(‘、‘)’、‘{‘、‘}’、‘[‘和‘]’的字符串 s，確定輸入字符串是否有效。
如果滿足以下條件，輸入字符串有效：開括號必須由相同類型的括號括起來。左括號必須按正確的順序關閉。
示例1：
Input: s = "()"Output: true示例2：
Input: s = "()[]{}"Output: true示例3：
Input: s = "(]"Output: false示例4：
Input: s = "([)]"Output: false實施例5：
Input: s = "{[]}"Output: true限制條件：
問題信息
如果我們真的沒學過算法，也不知道那么多套路，那么通過問題和例子來獲取盡可能多的信息是非常重要的。
那么，我們可以得到以下信息：
得到以上信息后，我想既然[]、{}、()是成對出現的，那我是不是可以一一消除呢？如果最后的結果是空字符串，那不是就說明符合題意了嗎？
例如：
Input: s = "{[()]}"Step 1: The pair of () can be eliminated, and the result s is left with {[]}Step 2: The pair of [] can be eliminated, and the result s is left with {}Step 3: The pair of {} can be eliminated, and the result s is left with '', so it returns true in line with the meaning of the question代碼：
const isValid = (s) => { while (true) { let len = s.length // Replace the string with '' one by one according to the matching pair s = s.replace('{}', '').replace('[]', '').replace('()', '') // There are two cases where s.length will be equal to len // 1. s is matched and becomes an empty string // 2. s cannot continue to match, so its length is the same as the len at the beginning, for example ({], len is 3 at the beginning, and it is still 3 after matching, indicating that there is no need to continue matching, and the result is false if (s.length === len) { return len === 0 } }}暴力消除方式還是可以通過LeetCode的用例，但是性能差了一點，哈哈。
主題信息中的第二項強調對稱性。棧（后進先出）和（推入和彈出）正好相反，形成明顯的對稱性。
例如
Input: abcOutput: cba“abc”和“cba”是對稱的，所以我們可以嘗試從堆棧的角度來解析：
Input: s = "{[()]}"Step 1: read ch = {, which belongs to the left bracket, and put it into the stack. At this time, there is { in the stack.Step 2: Read ch = [, which belongs to the left parenthesis, and push it into the stack. At this time, there are {[ in the stack.Step 3: read ch = (, which belongs to the left parenthesis, and push it into the stack. At this time, there are {[( in the stack.Step 4: Read ch = ), which belongs to the right parenthesis, try to read the top element of the stack (and ) just match, and pop ( out of the stack, at this time there are {[.Step 5: Read ch = ], which belongs to the right parenthesis, try to read the top element of the stack [and ] just match, pop the [ out of the stack, at this time there are {.Step 6: Read ch = }, which belongs to the right parenthesis, try to read the top element of the stack { and } exactly match, pop { out of the stack, at this time there is still '' in the stack.Step 7: There is only '' left in the stack, s = "{[()]}" conforms to the valid bracket definition and returns true.代碼
const isValid = (s) => { // The empty string character is valid if (!s) { return true } const leftToRight = { '(': ')', '[': ']', '{': '}' } const stack = [] for (let i = 0, len = s.length; i < len; i++) { const ch = s[i] // Left parenthesis if (leftToRight[ch]) { stack.push(ch) } else { // start matching closing parenthesis // 1. If there is no left parenthesis in the stack, directly false // 2. There is data but the top element of the stack is not the current closing parenthesis if (!stack.length || leftToRight[ stack.pop() ] !== ch) { return false } } } // Finally check if the stack is empty return !stack.length}雖然暴力方案符合我們的常規思維，但是堆棧結構方案會更加高效。
在面試中，算法是否應該成為評價候選人的重要指標，我們不會抱怨，但近年來，幾乎每家公司都將算法納入了前端面試中。為了拿到自己喜歡的offer，復習數據結構、刷題還是有必要的。
本文鏈接：http://www.www897cc.com/showinfo-26-10891-0.html面試官：你工作了3年了，這道算法題你都答不出來？
聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。郵件：2376512515@qq.com
上一篇： 一文讀懂分布式追蹤：過去、現在和未來
下一篇： CSS實現十個功能強大的一行布局技巧
Copyright ? 2016-2023 天津谷騏科技有限公司 版權所有 sitemap.xml
違法及侵權請聯系：2376512515@qq.com 津ICP備18001702號
津公網安備 12010102000574號