算法|算法 - 字典算法-字典

字典

与集合类似，字典也是一种存储唯一值的数据结构，但它是以键值对的形式来存储
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 - nif (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'))