关于leetcode:JavaScript刷LeetCode拿offerjs版字典

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
• 字典的罕用操作：键值对的增删改查