JavaScript数据结构（五）字典

1. 定义

字典是以**[键，值]**的形式来存储元素。字典也称作映射、符号表或关联数组。

es6中有字典Map

常用操作：键值对的增删改查

2. 具体操作

创建

import { defaultToString } from '../util';
export default class Dictionary {
    constructor(toStrFn = defaultToString) {
        this.toStrFn = toStrFn;
        this.table = {};
    }
}

在字典中，理想的情况是用字符串作为键名，值可以是任何类型。但是，由于JavaScript 不是强类型的语言，我们不能保证键一定是字符串。我们需要把所有作为键名传入的对象转化为字符串，使得从Dictionary 类中搜索和获取值更简单。

class ValuePair {
    constructor(key, value) {
        this.key = key;
        this.value = value;
    }
    toString() {
    	return `[#${this.key}: ${this.value}]`;
    }
}

使用

set(key,value)：向字典中添加新元素

如果key 已经存在，那么已存在的 value 会被新的值覆盖

set(key, value) {
    if (key != null && value != null) {
        const tableKey = this.toStrFn(key);  //获取表示key的字符串
        //创建一个新的键值对，并赋值给table对象上的key属性
        this.table[tableKey] = new ValuePair(key, value);  
        return true;
    }
    return false;
}

remove(key)：通过使用键值作为参数来从字典中移除键值对应的数据值。

remove(key) {
    if (this.hasKey(key)) {
        delete this.table[this.toStrFn(key)];
        return true;
    }
    return false;
}

hasKey(key)：如果某个键值存在于该字典中，返回true，否则返回false。
```
hasKey(key) {
	return this.table[this.toStrFn(key)] != null;
}
```
Js

get(key)：通过以键值作为参数查找特定的数值并返回。

get(key) {
    const valuePair = this.table[this.toStrFn(key)]; 
    return valuePair == null ? undefined : valuePair.value; 
}

get(key) {
    if (this.hasKey(key)) {
    	return this.table[this.toStrFn(key)];
    }
    return undefined;
}

clear()：删除该字典中的所有值。
```
clear() {
	this.table = {};
}
```
Js
size()：返回字典所包含值的数量。与数组的length 属性类似。
```
size() {
	return Object.keys(this.table).length;
}
```
Js
isEmpty()：在size 等于零的时候返回true，否则返回false。
```
isEmpty() {
	return this.size() === 0;
}
```
Js

keys()：将字典所包含的所有键名以数组形式返回。

keys() {
	return this.keyValues().map(valuePair => valuePair.key);
}

const keys = [];
const valuePairs = this.keyValues();
for (let i = 0; i < valuePairs.length; i++) {
	keys.push(valuePairs[i].key);
}
return keys;

values()：将字典所包含的所有数值以数组形式返回。

values() {
	return this.keyValues().map(valuePair => valuePair.value);
}

keyValues()：将字典中所有[键，值]对返回。

keyValues() {
	return Object.values(this.table); //Object.values()为ECMAScript 2017
}

keyValues() {
    const valuePairs = [];
    for (const k in this.table) { 
        if (this.hasKey(k)) {
        	valuePairs.push(this.table[k]);
        }
    }
    return valuePairs;
};

forEach(callbackFn)：迭代字典中所有的键值对。callbackFn 有两个参数：key 和value。该方法可以在回调函数返回false 时被中止（和Array 类中的every 方法相似）。

forEach(callbackFn) {
    const valuePairs = this.keyValues(); // {1}
    for (let i = 0; i < valuePairs.length; i++) { // {2}
        const result = callbackFn(valuePairs[i].key, valuePairs[i].value); // {3}
        if (result === false) {
        	break; // {4}
        }
    }
}

toString()

toString() {
    if (this.isEmpty()) {
    	return '';
    }
    const valuePairs = this.keyValues();
    let objString = `${valuePairs[0].toString()}`;
    for (let i = 1; i < valuePairs.length; i++) {
    	objString = `${objString},${valuePairs[i].toString()}`;
    }
    return objString;
}

3. 使用

const dictionary = new Dictionary();
dictionary.set('Gandalf', 'gandalf@email.com');
dictionary.set('John', 'johnsnow@email.com');
dictionary.set('Tyrion', 'tyrion@email.com');

console.log(dictionary.hasKey('Gandalf')) //true
console.log(dictionary.size());  //3
console.log(dictionary.keys());  //["Gandalf", "John", "Tyrion"]
console.log(dictionary.values()); //["gandalf@email.com", "johnsnow@email.com", "tyrion@email.com"]
console.log(dictionary.get('Tyrion'));  //tyrion@email.com

dictionary.remove('John');

dictionary.forEach((k, v) => {
	console.log('forEach: ', `key: ${k}, value: ${v}`);
});

4. LeetCode

JavaScript数据结构（五）字典

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    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;
};

将nums1的每个值以key的形式存在字典里，值设置为true

遍历nums2，如果在字典里找到有对应的值，则添加到res里，并在字典里删除这个值

JavaScript数据结构（五）字典

/**
 * @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++) {
        const c = s[i];
        if(map.has(c)) {  //如果这个值和map匹配上，则向栈中添加
            stack.push(c);
        } else {
            const t = stack[stack.length - 1]; //栈顶元素
            if(map.get(t) === c) {  //键对匹配上，删除栈内的元素
                stack.pop();
            } else {
                return false;
            }
        }
    }
    return stack.length === 0;
};

使用栈和字典这两个数据结构

栈：后进先出

字典：键对匹配

JavaScript数据结构（五）字典

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)) {  //在map中寻找是否有能匹配上的值
            return [map.get(n2), i];
        }else{
            map.set(n, i);
        }
    }
};

内存消耗大，执行时间快

JavaScript数据结构（五）字典

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;
        }
        res = Math.max(res, r - l + 1);
        map.set(s[r], r);
    }
    return res;
};

使用滑动窗口，如果map里有这个元素且在窗口内，则左指针向右移动

直到不满足条件，取窗口大小与res进行比较，res存储较大的那个数，并将右指针与指向的数字以键对的形式存储到map里

JavaScript数据结构（五）字典

/**
 * @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);
    }  //need存储t各个字符所需要的个数
    let needType = need.size;  // 不同字符种类数
    let res = '';
    while(r < s.length) { //右指针移动
        const c = s[r];
        if(need.has(c)) {  //找到need里有对应的值，则减少该字符想要的个数
            need.set(c, need.get(c) - 1);
            if(need.get(c) === 0) needType--;  //当该字符变为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];  //c2存放左指针对应的值
            if(need.has(c2)) {  //如果左指针对应的值是need的
                need.set(c2,need.get(c2) + 1);  //因为移动，会将这个值移出窗口，会使得need里c2需要的个数+1
                if(need.get(c2) === 1) needType++; //如果刚好为1个，即需要多增加一个type
            }
            l++;  //当窗口里找到所有t，左指针移动
        }
        r++;  //当need不为0，右指针移动，继续寻找对应
    }
    return res;
};