字典
简介
与集合类似，字典也是一种存储唯一值的数据结构，但它是以键值对的形式来存储。
ES6 中有字典，名为Map
字典的常用操作：键值对的增删改查
LeetCode：349. 两个数组的交集
- 解题思路
求 nums1 和 nums2 都有的值
用字典建立一个映射关系，记录 nums1 里都有的值
遍历 nums2 找出 nums1 里也有的值
- 解题步骤
新建一个字典，遍历 nums1,填充字典
遍历 nums2 遇到字典里的值就选出，并从字典中删除
/*
* @lc app=leetcode.cn id=349 lang=javascript
*
* [349] 两个数组的交集
*/
// @lc code=start
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersection = function (nums1, nums2) {
// 集合
// return [...new Set(nums1)].filter((item) => {
// return nums2.includes(item)
// })
// 字典
let m = new Map()
nums1.forEach(item => {
m.set(item, true)
})
let res = []
nums2.forEach(item => {
if (m.get(item)) {
res.push(item)
m.delete(item)
}
})
return res
}
// @lc code=end
LeetCode：20.有效的括号
LeetCode：20.有效的括号使用字典建立左右括号映射关系
/*
* @lc app=leetcode.cn id=20 lang=javascript
*
* [20] 有效的括号
*/
// @lc code=start
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function (s) {
// 有手就行
const stack = []
const map = new Map()
map.set('{', '}')
map.set('(', ')')
map.set('[', ']')
for (let i = 0; i < s.length; i++) {
if (map.has(s[i])) {
stack.push(s[i])
} else {
const top = stack[stack.length - 1]
if (map.get(top) === s[i]) {
stack.pop()
} else {
return false
}
}
}
return stack.length === 0
}
// @lc code=end
LeetCode：1. 两数之和
- 解题思路
把 nums 想象成相亲者
把 target 想象成匹配条件
用字典建立一个婚姻介绍所，存储相亲者的数字和下标
- 解题步骤
新建一个字典作为婚姻介绍所。
nums 里的值，逐个来介绍所找对象，没有合适的就先登记着，有合适的就牵手成功。
/*
* @lc app=leetcode.cn id=1 lang=javascript
*
* [1] 两数之和
*/
// @lc code=start
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
let map = new Map()
for ([index, val] of nums.entries()) {
let n = target - val
if (map.has(n)) {
return [map.get(n), index]
} else {
map.set(val, index)
}
}
}
// @lc code=end
LeetCode：3. 无重复字符的最长子串
- 解题思路
先找出所有的不包含重复字符的子串
找出长度最大那个子串，返回其长度即可。
- 解题步骤
用双指针维护一个滑动窗口(slice)，用来剪切子串。
不断移动右指针，遇到重复字符，就把左指针移动到重复字符的下一位。
过程中，记录所有窗口的长度，并返回最大值。
::: warning 有个坑
如果输入的为“abbcdea”,无重复字符的最长子串的长度应该为 5("bcdea")，此时左指针在索引为 2 的那一项，当右指针要马上指向最后一个 a 时，发现 map 中已经有一个 a 了，所以会移动左指针到索引为 1 的位置，这就导致输出结果为 6 了
解决方法：移动左指针时，必须确保重复字符的索引必须大于左指针的索引
:::
/*
* @lc app=leetcode.cn id=3 lang=javascript
*
* [3] 无重复字符的最长子串
*/
// @lc code=start
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function (s) {
let l = 0
let r = 0
let res = 0
let map = new Map()
for (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
}
// @lc code=end
LeetCode：76. 最小覆盖子串
- 解题思路
先找出所有的包含 T 的子串。
找出长度最小那个子串，返回即可。
- 解题步骤
用双指针维护一个滑动窗口。
移动右指针，找到包含 T 的子串，移动左指针，尽量减少包含 T 的子串的长度。
循环上述过程，找出包含 T 的最小子串
::: tip 提示 substring 参数为左闭右开区间，substring(a,b)可以得到从 a 开始到 b 结束（不包括 b 处）的子串 :::
/*
* @lc app=leetcode.cn id=76 lang=javascript
*
* [76] 最小覆盖子串
*/
// @lc code=start
/**
* @param {string} s
* @param {string} t
* @return {string}
*/
var minWindow = function (s, t) {
let l = 0
let r = 0
let res = ''
// 需要
const need = new Map()
for (let c of t) {
need.set(c, need.has(c) ? need.get(c) + 1 : 1)
}
let needType = need.size
while (r < s.length) {
const c = s[r]
if (need.has(c)) {
need.set(c, need.get(c) - 1)
if (need.get(c) === 0) needType--
}
while (needType === 0) {
let newRes = s.substring(l, r + 1)
if (!res || newRes.length < res.length) res = newRes
const c2 = s[l]
if (need.has(c2)) {
need.set(c2, need.get(c2) + 1)
if (need.get(c2) === 1) needType++
}
l++
}
r++
}
return res
}
// @lc code=end