数据结构（五）字典

1. 定义

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

es6中有字典Map

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

2. 具体操作

创建

1
2
3
4
5
6
7
import { defaultToString } from '../util';
export default class Dictionary {
    constructor(toStrFn = defaultToString) {
        this.toStrFn = toStrFn;
        this.table = {};
    }
}

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

1
2
3
4
5
6
7
8
9
class ValuePair {
    constructor(key, value) {
        this.key = key;
        this.value = value;
    }
    toString() {
    	return `[#${this.key}: ${this.value}]`;
    }
}

使用

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

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    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)：通过使用键值作为参数来从字典中移除键值对应的数据值。

    1
    2
    3
    4
    5
    6
    7
    remove(key) {
        if (this.hasKey(key)) {
            delete this.table[this.toStrFn(key)];
            return true;
        }
        return false;
    }

  • hasKey(key)：如果某个键值存在于该字典中，返回true，否则返回false。

    1
    2
    3
    hasKey(key) {
    	return this.table[this.toStrFn(key)] != null;
    }

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

    1
    2
    3
    4
    get(key) {
        const valuePair = this.table[this.toStrFn(key)]; 
        return valuePair == null ? undefined : valuePair.value; 
    }
    1
    2
    3
    4
    5
    6
    get(key) {
        if (this.hasKey(key)) {
        	return this.table[this.toStrFn(key)];
        }
        return undefined;
    }

  • clear()：删除该字典中的所有值。

    1
    2
    3
    clear() {
    	this.table = {};
    }

  • size()：返回字典所包含值的数量。与数组的length 属性类似。

    1
    2
    3
    size() {
    	return Object.keys(this.table).length;
    }

  • isEmpty()：在size 等于零的时候返回true，否则返回false。

    1
    2
    3
    isEmpty() {
    	return this.size() === 0;
    }

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

    1
    2
    3
    keys() {
    	return this.keyValues().map(valuePair => valuePair.key);
    }
    1
    2
    3
    4
    5
    6
    const keys = [];
    const valuePairs = this.keyValues();
    for (let i = 0; i < valuePairs.length; i++) {
    	keys.push(valuePairs[i].key);
    }
    return keys;

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

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

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

    1
    2
    3
    keyValues() {
    	return Object.values(this.table); //Object.values()为ECMAScript 2017
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    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 方法相似）。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    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()

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    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. 使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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

LeetCode349

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @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里，并在字典里删除这个值

LeetCode2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * @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;
};

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

栈：后进先出

字典：键对匹配

LeetCode1

1
2
3
4
5
6
7
8
9
10
11
12
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);
        }
    }
};

内存消耗大，执行时间快

LeetCode

1
2
3
4
5
6
7
8
9
10
11
12
13
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里

LeetCode76

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * @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;
};

使用滑动窗口，并使用map进行键对匹配