1. 字典简介
1.1 字典的常用操作
const m = new Map();
// 增
m.set('a', 'aa');
m.set('b', 'bb');
// 删
m.delete('b');
m.clear();
// 改
m.set('a', 'aaa')
// 查
m.get('a');
复制代码
2. LeetCode: 349. 两个数组的交集
2.1 解题思路
2.2 解题步骤
/** * @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]} */
var intersection = function (nums1, nums2) {
// 集合Set 实现方式
// return [...new Set(nums1)].filter(item => nums2.includes(item))
const map = new Map();
nums1.forEach(n => {
map.set(n, true)
})
const res = [];
nums2.forEach(n => {
if (map.get(n)) {
res.push(n);
map.delete(n);
}
})
return res
};
复制代码
3. LeetCode:20. 有效的括号
/** * @param {string} s
* @return {boolean} */
var isValid = function (s) {
if (s.length % 2 === 1) { return false }
const stack = [];
const map = new Map();
map.set('(', ')')
map.set('[', ']')
map.set('{', '}')
for (let i = 0; i < s.length; i += 1) {
const c = s[i];
if (c === '(' || c === '{' || c === '[') {
stack.push(c)
} else {
const t = stack[stack.length - 1];
if (
map.get(t) === c
) {
stack.pop();
} else {
return false;
}
}
}
return stack.length === 0;
};
复制代码
参考视频:传送门
4. LeetCode: 1. 两数之和
4.1 解题思路
输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
复制代码
把 nums 想象成相亲者
把 target 想象成匹配条件
用字典建立一个婚姻介绍所,存储相亲者的数字和下标
4.2 解题步骤
/** * @param {number[]} nums
* @param {number} target
* @return {number[]} */
var twoSum = function (nums, target) {
const map = new Map()
for (let i = 0; i < nums.length; i += 1) {
const n = nums[i];
const n2 = target - n;
if (map.has(n2)) {
return [map.get(n2), i]
} else {
map.set(n, i)
}
}
};
复制代码
执行用时:56 ms, 在所有 JavaScript 提交中击败了 99.77%的用户
内存消耗:39.9 MB, 在所有 JavaScript 提交中击败了 37.04%的用户
内存消耗为 O(n), 我们可以通过二分查找,用时间换空间的方式,进行处理
5. LeetCode: 3. 无重复字符的最长子串
5.1 题目描述
5.2 解题步骤
5.3 代码实现
/** * @param {string} s
* @return {number} */
var lengthOfLongestSubstring = function (s) {
let l = 0; // 左指针位置
let res = 0; // 定义返回结果
const map = new Map();
for (let r = 0; r < s.length; r += 1) {
// 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;
};
复制代码
6. LeetCode: 76. 最小覆盖子串
6.1 题目描述
6.2 解题思路
先找出所有包含 T 的子串
找出长度最小的那个子串,返回即可
6.3 解题步骤
6.3 代码实现
/** * @param {string} s
* @param {string} t
* @return {string} */
var minWindow = function (s, t) {
let l = 0;
let r = 0;
const need = new Map();
for (let c of t) {
need.set(c, need.has(c) ? need.get(c) + 1 : 1)
}
let needType = need.size;
let res = '';
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 -= 1;
}
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) needType += 1;
}
l += 1;
}
r += 1;
}
return res
};
复制代码
7. 总结:
评论