【戲玩算法】07-字典

語言: CN / TW / HK
時間 2022-06-12 15:15:14

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作為編程語言，從前端的角度去介紹數據結構與算法，如果對你所有幫助，可以點個關注支持一下啊\~

「」
「」