js数据结构-字典

1.什么是字典?

  • 字典是一种以键值对的形式存储唯一值的数据结构
  • ES6中有字典,名为Map

2.常用操作

  • 添加元素 set
  • 删除元素 delete
  • 更改元素 set
  • 查找元素 get
  • 清空字典 clear

3.代码示例

//创建字典
const myMap = new Map();

//增,'a'为键,'aa'为值
myMap.set('a','1');  // {a:1}
myMap.set('b','2');   //{a:1,b:2}

//删
myMap.delete('b');    // {a:1}

//改
myMap.set('a','3'); //{a:3}

//查
let c = myMap.get('a');  // c = 3

//清除全部键值对
myMap.clear();  // {}

4.LeetCode

接下来使用字典这个数据结构来刷LeetCode有关字典的题目,巩固提升对字典的了解。

题号349.两个数组的交集(简单)

题目要求:
js数据结构-字典

解题思路:
方法二: 使用字典

  1. 利用字典元素的唯一性,将数组一的值赋值给字典作为键
  2. 如果数组二的值出现在字典键中,则说明是相交的元素,压入栈中,删除字典中该元素,防止重复
    编写代码
var intersection = function(nums1, nums2) {
   const map = new Map();
   const res = [];
   nums1.forEach(n => { 
       map.set(n,true);
   })
   nums2.forEach(m => { 
       if(map.get(m)) { 
           res.push(m);
           map.delete(m);//防止重复
       }
   })
   return res;
};

复杂度分析

  • 时间复杂度: O(m+n)
  • 空间复杂度: O(n)

题号3.无重复字符的最长子串(中等)

题目要求:
![在这里插入图片描述](https://www.icode9.com/i/ll/?i=e5c60896bf544ef28703749ab7a7e2cf.png?,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5pyo5Y-v55Sf5qOu,size_19,color_FFFFFF,t_70,g_se,x_16

解题思路:
思路: 字典 + 双指针 维护一个滑动窗口

  1. 用双指针维护一个滑动窗口,用来剪切子串
  2. 不断移动右指针,遇到重复的字符,就把左指针移动到之前存储过这个重复字符的下一位,然后再存一遍这个字符
  3. 过程中,记录所有窗口的长度,并返回最大值
  4. map.get(s[r]) >= l 用来预防窗口外字符等于当前右指针的情况,窗口外字符已经不属于当前滑动窗口,比如abba,执行到左指针为第二个b时,接着执行,左指针会跑到第一个a,这样就错误了

编写代码

var 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;  // l移动到之前存储该元素位置的下一位,后面会再存储这个元素一次
        }
        res = Math.max(res,r-l+1);
        map.set(s[r],r); //存储元素位置
    }
    return res;
};

复杂度分析

  • 时间复杂度: O(n)
  • 空间复杂度: O(m) ,m是字符串中不重复字符的个数

题号76.最小覆盖子串(困难)

题目要求:
js数据结构-字典

解题思路:
思路:

  1. 用双指针维护一个滑动窗口
  2. 统计需要字符的种类和数量
  3. 移动右指针,找到包含T的子串
  4. 移动左指针,尽量减少包含T的子串的长度
  5. 循环上述过程,找到包含T的最小子串

编写代码

/**
 * @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 needTypeCount = need.size;
    // 定义一个要返回的字符串
    let res = '';
    while (r < s.length) { 
        // 获取右指针当前字符
        const c = s[r];
        // 判断是否是需要的字符,如果是,那就让需要的字符减一
        if (need.has(c)) {
        //need.get(c)变成负数的话就说明子串中多富裕几个字符,在移动左指针的时候加回来就可以
            need.set(c,need.get(c) - 1); 
            // 如果当前需要的字符数量等于0,那就让当前需要类型数量减一
            if (need.get(c) === 0) needTypeCount -= 1;
        }
        //如果需要的字符类型数量都等于0了,就说明满足题目要求的全部字符都出现了
        while (needTypeCount === 0) {
            //subStirng是左开右闭的,所以是r+1
            const newRes = s.substring(l, r + 1);
            //如果刚开始res是空字符串,就先给他赋值为newRes 
            if (!res || newRes.length < res.length) res = newRes;
            // 温饱满足了,尝试奔小康,尝试减少字符串的长度,
            const c2 = s[l];
            // 如果当前左指针指向的是需要的字符,因为我们要尝试缩短字符串长度,移动左指针
            // 所以设置需要当前这个字符数的数量加一
            if (need.has(c2)) {
                need.set(c2,need.get(c2) + 1);
                //如果需要的字符数等于 1 说明子串不满足包含所有字母种类了 needTypeCount+1
                if (need.get(c2) === 1) needTypeCount += 1;
            }
            l += 1; 
        }
        r += 1;
    }
    return res;
};

复杂度分析

  • 时间复杂度:O(m+n) m是t的长度,n是s的长度
  • 空间复杂度: O(m) m是t中不同字符的个数
上一篇:567. 字符串的排列 (滑动窗口)


下一篇:【每日一题】32. 比赛 (DFS / 概率DP)