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; } -
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 = {}; } -
size()：返回字典所包含值的数量。与数组的length 属性类似。
size() { return Object.keys(this.table).length; } -
isEmpty()：在size 等于零的时候返回true，否则返回false。
isEmpty() { return this.size() === 0; } -
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
/**
* @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里，并在字典里删除这个值
/**
* @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;
};
使用栈和字典这两个数据结构
栈：后进先出
字典：键对匹配
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);
}
}
};
内存消耗大，执行时间快
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里
/**
* @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进行键对匹配
常见问题FAQ
- 免费下载或者VIP会员专享资源能否直接商用？
- 本站所有资源版权均属于原作者所有，这里所提供资源均只能用于参考学习用，请勿直接商用。若由于商用引起版权纠纷，一切责任均由使用者承担。更多说明请参考 VIP介绍。
- 提示下载完但解压或打开不了？
- 找不到素材资源介绍文章里的示例图片？
- 模板不会安装或需要功能定制以及二次开发？
发表评论
还没有评论，快来抢沙发吧！