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