【戲玩演算法】07-字典

語言: CN / TW / HK

theme: fancy highlight: atom-one-light


持續創作,加速成長!這是我參與「掘金日新計劃 · 6 月更文挑戰」的第11天,點選檢視活動詳情

Hi~,我是一碗周,如果寫的文章有幸可以得到你的青睞,萬分有幸~

🫐 寫在前面

在前面的幾篇文章中,我們學習了棧、佇列、連結串列以及集合,在這篇文章中學習一個新的資料結構——字典。

🍓 什麼是字典

說到字典,第一時間想到的應該就是新華字典,實際上,這跟程式設計中的字典類似,兩者都有一個特點,就是一一對應(yi yi dui ying),或者說是對映

字典通常以**【鍵,值】** 對的形成儲存,因為是以鍵值對的形式儲存,更方便通過key來獲取value

,比如儲存使用者資訊:

javascript { 'username': '一碗周', 'age': 18 }

🍋 JavaScript中的字典

在JavaScript中,物件好像擁有字典的所有特點,但是在ES6中新增Map,用來表示字典,這裡的map不是翻譯成地圖,而是對映。

示例程式碼如下:

```javascript // 建立一個字典 const map = new Map()

// 往字典中儲存資訊 map.set('username', '一碗周') map.set('age', 18)

console.log(map) // Map(2) { 'username' => '一碗周', 'age' => 18 }

```

🍊 字典的應用

在學習連結串列的時候我們做了一個演算法題,是力扣中題號為20的一道題,它的題目:有效的括號,題目大意就是判斷給定字串中的括號是否匹配,匹配返回true,否則返回false

解題思路如下:

  1. 判斷字串的長度是否為偶數,不為偶數直接返回false,因為括號都是成對出現的;

  2. 新建一個棧;

  3. 遍歷字串,遍歷到每一項時如果時左括號,將其壓入棧;如果是右括號,與棧頂對比,如果相匹配則出棧,不匹配則返回false

我們原來的解法:

```javascript /* * @param {string} s * @return {boolean} / var isValid = function(s) { if (s.length % 2 !== 0) return false

const stack = []

for(let i = 0; i<s.length; i++) {
    const c = s[i] // 記錄當前項
    if (c === '(' || c === '[' || c==='{') {
        stack.push(c)
    } else {
        const t = stack[stack.length - 1] // 獲取棧頂元素
        if (
            (t === '(' && c === ')') ||
            (t === '[' && c === ']') ||
            (t === '{' && c === '}') 
        ) {
            stack.pop()
        } else {
            return false
        }
    }
}
// 如果為0表示全部匹配,有剩餘則表示不匹配
return stack.length === 0

}; ```

在上面的程式碼中,條件判斷中的判斷條件非常的長,這時我們就可以利用字典來優化這個寫法,實現程式碼如下:

javascript /** * @param {string} s * @return {boolean} */ var isValid = function(s) { // 1. 判斷字串的長度是否為偶數,不為偶數直接返回false,因為括號都是成對出現的; if (s.length % 2 !== 0) return false const stack = [] const map = new Map() // 將所有括號的對應關係儲存在字典中 map.set('(', ')') map.set('[', ']') map.set('{', '}') for(let i = 0; i<s.length; i++) { const c = s[i] // 記錄當前項 // 判斷是否存在 key 也就是左括號,如果儲存,將左括號儲存在棧中 if (map.has(c)) { stack.push(c) } else { const t = stack[stack.length - 1] // 獲取棧頂元素 if (map.get(t) === c) { // 獲取最後一個左括號,判斷是否與右括號匹配 stack.pop() // 出棧 } else { return false } } } // 如果為0表示全部匹配,有剩餘則表示不匹配 return stack.length === 0 };

在這個程式碼中,我們優化了if語句中的判斷條件。

🍉 寫在最後

本篇文章到這就結束了\~

本專欄採用JavaScript作為程式語言,從前端的角度去介紹資料結構與演算法,如果對你所有幫助,可以點個關注支援一下啊\~