字典
2021-11-23 本文已影响0人
sweetBoy_9126
1. 是什么？
- 与集合类似，字典也是一种存储唯一值的数据结构，但它是以键值对的形式来存储
- ES6 中的字典就是 Map
- 字典的常用操作：键值对的增删改查。
var m = new Map();
// 增
m.set('a', 'aa');
// 删
m.delete('a'); // 删除集体某一个key
m.clear(); // 清除所有的 key
// 改
m.set('a', 'aaa')
// 查
m.get('a')
2. 场景
2.1. 两个数组的交集 leetCode: 349
解题思路
解题步骤
var intersection = function(nums1, nums2) {
var m = new Map();
nums1.forEach(n => m.set(n, true));
var arr = []
nums2.forEach(n => {
if (m.get(n)) {
arr.push(n);
// 如果不删会出现多个相同的值
m.delete(n)
}
})
return arr
};
时间复杂度两个for循环，每个复杂度都是当前项的长度，假设nums1长度是m，nums2长度是n，那么就是O(m+n);
空间复杂度：里面用到了一个字典，是O(m)
2.2. 有效括号 leetCode 20
对我们之前用栈的代码进行优化
var isValid = function(s) {
if (s.length % 2 === 1) {
return false;
}
const stack = [];
for (let i = 0; i < s.length; i++) {
if (['(', '{', '['].includes(s[i])) {
stack.push(s[i])
} else {
const lastS = stack[stack.length - 1]
if (
lastS === '(' && s[i] === ')' ||
lastS === '{' && s[i] === '}' ||
lastS === '[' && s[i] === ']'
) {
stack.pop()
} else {
return false
}
}
}
return stack.length === 0
};
优化
var isValid = function(s) {
if (s.length % 2 === 1) {
return false;
}
const map = new Map();
map.set('(', ')')
map.set('{', '}');
map.set('[', ']')
const stack = [];
for (let i = 0; i < s.length; i++) {
// 能取到值说明 s[i] 肯定是左括号
if (map.get(s[i])) {
stack.push(s[i])
} else {
const lastS = stack[stack.length - 1]
if (
// 栈里的最后一项能通过 get 获取到值，说明肯定是左括号，get拿到的值就是对应的右括号，如果当前项等于对应的右括号就可以从栈里移除掉
map.get(lastS) === s[i]
) {
stack.pop()
} else {
return false
}
}
}
return stack.length === 0
};
2.3. 两数之和 leetCode 1
解题思路
解题步骤
var twoSum = function(nums, target) {
let map = new Map();
let arr;
nums.forEach((n, index) => {
let n2 = target - n;
// 这里不能用 get 因为获取的是小标如果是0就不会进来
if (map.has(n2)) {
arr = [map.get(n2), index]
} else {
map.set(n, index)
}
})
return arr;
};
时间复杂度和空间复杂度都是 O(n)
2.4. 无重复字符的最长子串 leetCode 3
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
解题思路
解题步骤
var lengthOfLongestSubstring = function(s) {
var l = 0; // 左指针
var r = 0; // 右指针
var res = 0; // 非重复的最大长度
var map = new Map(); // 用来存储当前已经有的项
for (let r = 0; r < s.length; r++) {
// 如果当前右侧指针的值已经在字典里
if (map.has(s[r])) {
// 把左侧指针从当前重复项的下一项开始
l = map.get(s[r]) + 1
}
// 最大长度等于当前最大长度或者右指针-左指针+1
res = Math.max(res, r-l+1)
// 把每一项存到字典里
map.set(s[r], r)
}
return res;
};
上面的代码如果遇到以下用例就会报错
输入：
"abba"
输出：
3
预期结果：
2
原因执行到最后面一个a的时候上面的 if (map.has(s[r]))也会走进去，而实际上第一个a已经不在我们的区间内了，所以我们不止要判断字典里有这一项，还要这一项的索引值在我们左指针后面才可以
具体代码：
// 如果当前右侧指针的值已经在字典里并且在左指针和右指针的区间内
if (map.has(s[r]) && map.get(s[r]) >= l) {
l = map.get(s[r]) + 1
}
时间复杂度 O(n)
空间复杂度O(m) ,m 是字符串中不重复字符的个数
2.5. 最小覆盖子串 leetCode: 76
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解题思路
解题步骤
var minWindow = function(s, t) {
let l = 0;
let r = 0;
// 存储我们的子串需要的字符和个数
let need = new Map();
for (let key of t) {
// 这里如果我们的 字典 里已经存入过当前字符我们就要对它当前的长度加1，比如t是'aa'，应该是{'a': 2}
need.set(key, need.has(key) ? need.get(key) + 1 : 1)
}
// 获取字典里不重复字符的个数（比如： {a: 3, b: 1, c: 2} 那 size 就是 3）
let needType = need.size;
let res = ''
for (let r = 0; r < s.length; r++) {
const c = s[r]
if (need.has(c)) {
// 如果右指针对应的值在字典里，我们就把当前字典里的这个值次数减1
need.set(c, need.get(c) - 1)
// 如果当前右指针的字符的次数为0了，就把不重复元素的个数减1
if (need.get(c) === 0) {
needType -= 1;
}
}
// 当我们的needType 为0时说明我们已经找到满足条件的的子串，我们需要对满足条件的这个子串遍历
while (needType === 0) {
// 每次新的值等于左指针到右指针内的字符
const 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) {
// 同时对需要的不重复的字符加1
needType += 1
}
}
// 左指针右移
l += 1;
}
}
return res
};
