算法 - 字典

字典

• 与集合类似，字典也是一种存储唯一值的数据结构，但它是以键值对的形式来存储
• ES6中有字典，名为Map
• 字典的常用操作：键值对的增删改查

const map = new Map()

// 增加
map.set('a': 'aa')
map.set('b': 'bb')

// 获取
map.get('a')

// 改
map.set('a': 'aaa')

// 删除
map.delete('b')

// 删除所有
map.clear()

两个数组的交集

leeCode第349题

• 之前使用集合来解决，现在使用字典来解决
• 求 nums1 和 nums2 都有的值
• 用字典建立一个映射关系，记录 nums1 里有的值，填充字典
• 遍历 nums2，遇到字典里的值就选出，并从字典中删除

const intersection = function(nums1, nums2) {
    const map = new Map()
    nums1.forEach(num => {
        map.set(num, true)
    });

    const res = []
    nums2.forEach(num => {
        if(map.get(num)) {
            res.push(num)
            map.delete(num)
        }
    })

    return res
};

const arr1 = [1,2,2,1] // [4,9,5]
const arr2 = [1,2] // [9,4,9,8,4]
const res = intersection(arr1, arr2)
console.log(res)

有效的括号

leeCode第20题

• 之前是使用栈来解决的，现在使用字典来解决
• 通过定义字典，左括号则入栈，否则取出栈顶字典值判断是否一致
• 之前解法为了兼容里面有非括号，但是重新看了一下题目其实已经说了输入只有括号符，所以没必要特地去处理其他字符

const isValid = function(s) {
    if (s.length % 2) 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]
        if (map.has(c)) {
            stack.push(c)
        } else {
            const t = stack[stack.length - 1]
            if (map.get(t) === c) {
                stack.pop()
            } else {
                return false
            }
        }
    }

    return !stack.length
}

console.log(isValid("()"))
console.log(isValid("()[]{}"))
console.log(isValid("([)]"))
console.log(isValid("{[]}"))
console.log(isValid("{[]"))

两数之和

leeCode第1题

• target为匹配条件
• 先进入的nums为匹配者，如果没找到合适的则记录本身匹配答案

const twoSum = function(nums, target) {
    const map = new Map()

    for (let i = 0; i < nums.length; i++) {
        const n = nums[i]
        const n2 = target - n

        if (map.has(n2)) {
            return [map.get(n2), i]
        } else {
            map.set(n, i)
        }
    }
}

console.log(twoSum([2,7,11,15], 9))
console.log(twoSum([3,2,4], 6))
console.log(twoSum([3,3], 6))

无重复字符的最长子串

leeCode第3题

• 用双指针维护一个滑动窗口，用来剪切字符串
• 不断移动右指针，遇到重复字符，就把左指针移动到重复字符的下一位
• 找出长度最大那个子串，返回其长度即可

const lengthOfLongestSubstring = function(s) {
    let l = 0
    let res = 0
    const map = new Map()

    for (let r = 0; r < s.length; r++) { // 不停移动右指针
        if (map.has(s[r]) && map.get(s[r]) >= l) { // 如果重复的数字比左指针下标少则证明被排除在外了，无需管
            l = map.get(s[r]) + 1
        }
        res = Math.max(res, r - l + 1) // 记录字符最大值
        map.set(s[r], r) // 记录该字符下标
    }
    return res
}


console.log(lengthOfLongestSubstring('abcabcbb'))
console.log(lengthOfLongestSubstring('bbbbb'))
console.log(lengthOfLongestSubstring('pwwkew'))
console.log(lengthOfLongestSubstring('abbcdea'))

最小覆盖子串

leeCode第76题

• 用双指针维护一个滑动窗口
• 移动右指针，找到包含T的子串，移动左指针，尽量减少包含T的子串的长度
• 循环上述过程，找到包含T的最小子串

const minWindow = function(s, t) {
    let l = 0
    let r = 0
    const map = new Map()
    for (let c of t) {
        map.set(c, map.has(c) ? map.get(c) + 1 : 1)
    }
    let needType = map.size
    let res = ''

    while (r < s.length) {
        const c = s[r]
        if (map.has(c)) {
            map.set(c, map.get(c) - 1)

            if (map.get(c) === 0) needType--
        }
        while (needType === 0) {
            const newRes = s.substring(l, r + 1)
            if (!res || newRes.length < res.length) res = newRes
            const c2 = s[l]
            if (map.has(c2)) {
                map.set(c2, map.get(c2) + 1)
                if (map.get(c2) === 1) needType++
            }
            l++
        }
        r++
    }
    return res
}

console.log(minWindow('ADOBECODEBANC', 'ABC'))
console.log(minWindow('a', 'a'))