【戏玩算法】07-字典

Hi~，我是 一碗周，一个在舒适区垂死挣扎的前端，如果写的文章有幸可以得到你的青睐，万分有幸~

🫐 写在前面

在前面的几篇文章中，我们学习了栈、队列、链表以及集合，在这篇文章中学习一个新的数据结构——字典。

🍓 什么是字典

说到字典，第一时间想到的应该就是新华字典，实际上，这跟编程中的字典类似，两者都有一个特点，就是一一对应（yi yi dui ying），或者说是映射。

字典通常以**【键，值】** 对的形成存储，因为是以键值对的形式存储，更方便通过key来获取value

，比如存储用户信息：

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

🍋 JavaScript中的字典

在JavaScript中，对象好像拥有字典的所有特点，但是在ES6中新增Map，用来表示字典，这里的map不是翻译成地图，而是映射。

示例代码如下：

// 创建一个字典
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。

我们原来的解法：

/**
 * @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
};

在上面的代码中，条件判断中的判断条件非常的长，这时我们就可以利用字典来优化这个写法，实现代码如下：

/**
 * @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作为编程语言，从前端的角度去介绍数据结构与算法，如果对你所有帮助，可以点个关注支持一下啊~