写点什么

JavaScript 刷 LeetCode 拿 offer-js 版字典

作者:Geek_07a724
  • 2022-11-14
    浙江
  • 本文字数:2258 字

    阅读完需:约 7 分钟

1. 字典简介

  • 与集合类似,字典也是一种存储唯一值的数据结构,但它是以键值对的形式来存储。

  • 使用 ES6 Map

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 解题思路

  • 求 nums1 和 nums2 多都有的值

  • 用字典建立一个映射关系,记录 nums1 里有的值

  • 遍历 nums2,找出 nums1 里也有的值

2.2 解题步骤

  • 新建一个字典,遍历 nums1,填充字典

  • 遍历 nums2, 遇到字典里的值就选出,并从字典中删除。


/** * @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 解题步骤

  • 新建一个字典作为婚姻介绍所

  • nums 里的值,逐个来介绍找对象,没有何止的就先登记者,有合适的就牵手


/** * @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;};
复制代码


  • 时间复杂度 O(n)

  • 空间复杂度 O(m)

6. LeetCode: 76. 最小覆盖子串

6.1 题目描述

6.2 解题思路

  • 先找出所有包含 T 的子串

  • 找出长度最小的那个子串,返回即可

6.3 解题步骤

  • 用双指针维护一个滑动窗口。

  • 移动右指针,找到包含 T 的子串,移动左指针,尽量减少包含 T 的子串的长度。

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};
复制代码


  • 时间复杂度 O(m+n),m 是 t 的长度,n 是 s 的长度

  • 空间复杂度 O(m)

7. 总结:

  • 与集合类似,字典也是一种存储唯一值的数据结构,但是它以键值对的形式来存储

  • ES6 中有字典,名为 Map

  • 字典的常用操作:键值对的增删改查


用户头像

Geek_07a724

关注

还未添加个人签名 2022-09-14 加入

还未添加个人简介

评论

发布
暂无评论
JavaScript刷LeetCode拿offer-js版字典_JavaScript_Geek_07a724_InfoQ写作社区