![[02/20][官改] Simplicity@MIX2S ROM更新-一一网](https://www.proyy.com/wp-content/uploads/2020/02/3070695309.jpg)
8、集合
- 集合是一个无序且唯一的数据结构
- ES6 中有集合，Set 数据结构
Set 常用方法
// set数据结构常见用法
// 去重
const arr = [1, 1, 2, 3, 4, 5, 3, 4];
const arr2 = [...new Set(arr)]; // [1,2,3,4,5]
// 判断元素是否在集合里
const set = new Set(arr);
const set1 = set.has(1); // true
const set2 = set.has(6); // false
// 求交集
const set3 = new Set([1, 2]);
const el = new Set([...set].filter((item) => set3.has(item))); // [1,2]
// set add方法
const addSet = new Set();
addSet.add(1);
const obj = {
a: 1,
b: 2,
};
addSet.add({
a: 1,
b: 2,
});
addSet.add(obj); // addSet同时存在两个对象，obj和 {a:1,b:2}两个对象存储的地址不一样
const set4 = addSet.has(obj); // true
const set5 = addSet.has({
// false
a: 1,
b: 2,
});
// delete 删除集合
addSet.delete(1);
addSet.delete(obj);
复制代码3、遍历操作
Set 结构的实例有四个遍历方法，可以用于遍历成员。
Set.prototype.keys()：返回键名的遍历器Set.prototype.values()：返回键值的遍历器Set.prototype.entries()：返回键值对的遍历器Set.prototype.forEach()：使用回调函数遍历每个成员
需要特别指出的是，Set的遍历顺序就是插入顺序。这个特性有时非常有用，比如使用 Set 保存一个回调函数列表，调用时就能保证按照添加顺序调用。
// Array.from方法可以将 Set 结构转为数组。
const items = new Set([1, 3, 4, 5, 6, 6, 7, 7]);
console.log(items);
const arr = Array.from(items);
console.log(arr); // [1,3,4,5,7]
// keys返回健明
for (let set of items.keys()) {
console.log(set); // 1, 3, 4, 5, 6, 7
}
// values返回键值
for (let set of items.values()) {
console.log(set); // 1, 3, 4, 5, 6, 7
}
// entries方法返回的遍历器，同时包括键名和键值，所以每次输出一个数组，它的两个成员完全相等。
for (let set of items.entries()) {
console.log(set); // [1, 1] [3, 3] [4, 4] [5, 5] [6, 6] [7, 7]
}
复制代码Set 结构的实例默认可遍历，它的默认遍历器生成函数就是它的values方法。
Set.prototype[Symbol.iterator] === Set.prototype.values;
// true
复制代码这意味着，可以省略values方法，直接用for...of循环遍历 Set。
// 简便写法
const item2 = new Set(["a", "b", "c", "d"]);
for (const set of item2) {
console.log(set);
}
复制代码遍历的应用
扩展运算符（...）内部使用for...of循环，所以也可以用于 Set 结构。
let set = new Set(["red", "green", "blue"]);
let arr = [...set];
// ['red', 'green', 'blue']
复制代码扩展运算符和 Set 结构相结合，就可以去除数组的重复成员。
let arr = [3, 5, 2, 2, 5, 5];
let unique = [...new Set(arr)];
// [3, 5, 2]
复制代码而且，数组的map和filter方法也可以间接用于 Set 了。
let set = new Set([1, 2, 3]);
set = new Set([...set].map((x) => x * 2));
// 返回Set结构：{2, 4, 6}
let set = new Set([1, 2, 3, 4, 5]);
set = new Set([...set].filter((x) => x % 2 == 0));
// 返回Set结构：{2, 4}
复制代码因此使用 Set 可以很容易地实现并集（Union）、交集（Intersect）和差集（Difference）。
let a = new Set([1, 2, 3]);
let b = new Set([4, 3, 2]);
// 并集
let union = new Set([...a, ...b]);
// Set {1, 2, 3, 4}
// 交集
let intersect = new Set([...a].filter((x) => b.has(x)));
// set {2, 3}
// （a 相对于 b 的）差集
let difference = new Set([...a].filter((x) => !b.has(x)));
// Set {1}
复制代码349. 两个数组的交集
var intersection = function (nums1, nums2) {
const set1 = new Set(nums1);
const set2 = new Set([...nums2].filter((item) => set1.has(item)));
return [...new Set(set2)];
};
const nums1 = [1, 2, 2, 1];
const nums2 = [2, 2];
intersection(nums1, nums2);
console.log(intersection(nums1, nums2));
复制代码9、字典
- 与集合类似，字典也是存储唯一值得数据结构，是以键值对(映射关系)的形式来存储
- ES6 中有字典，Map
1、基本用法
ES6 提供了 Map 数据结构。它类似于对象，也是键值对的集合，但是“键”的范围不限于字符串，各种类型的值（包括对象）都可以当作键。也就是说，Object 结构提供了“字符串—值”的对应，Map 结构提供了“值—值”的对应，是一种更完善的 Hash 结构实现。如果你需要“键值对”的数据结构，Map 比 Object 更合适。
const m = new Map();
m.set("name", "张三");
m.get("name");
console.log(m.get("name")); // 张三
console.log(m.has("name")); // true
console.log(m.has("age")); // false
console.log(m.delete("name")); // true
console.log(m.has("name")); // false
复制代码作为构造函数，Map 也可以接受一个数组作为参数。该数组的成员是一个个表示键值对的数组。
const map = new Map([
["name", "张三"],
["title", "Author"],
]);
map.size; // 2
map.has("name"); // true
map.get("name"); // "张三"
map.has("title"); // true
map.get("title"); // "Author"
复制代码如果读取一个未知的键，则返回undefined。
new Map().get("asfddfsasadf");
// undefined
复制代码注意，只有对同一个对象的引用，Map 结构才将其视为同一个键。这一点要非常小心。
const map = new Map();
map.set(["a"], 555);
map.get(["a"]); // undefined
复制代码上面代码的set和get方法，表面是针对同一个键，但实际上这是两个不同的数组实例，内存地址是不一样的，因此get方法无法读取该键，返回undefined。
同理，同样的值的两个实例，在 Map 结构中被视为两个键。
const map = new Map();
const k1 = ["a"];
const k2 = ["a"];
map.set(k1, 111).set(k2, 222);
map.get(k1); // 111
map.get(k2); // 222
复制代码2、实例的属性和操作方法
（1）size 属性
size属性返回 Map 结构的成员总数。
const map = new Map();
map.set("foo", true);
map.set("bar", false);
map.size; // 2
复制代码（2）Map.prototype.set(key, value)
set方法设置键名key对应的键值为value，然后返回整个 Map 结构。如果key已经有值，则键值会被更新，否则就新生成该键。
const m = new Map();
m.set("edition", 6); // 键是字符串
m.set(262, "standard"); // 键是数值
m.set(undefined, "nah"); // 键是 undefined
复制代码set方法返回的是当前的Map对象，因此可以采用链式写法。
let map = new Map().set(1, "a").set(2, "b").set(3, "c");
复制代码（3）Map.prototype.get(key)
get方法读取key对应的键值，如果找不到key，返回undefined。
const m = new Map();
const hello = function () {
console.log("hello");
};
m.set(hello, "Hello ES6!"); // 键是函数
m.get(hello); // Hello ES6!
复制代码（4）Map.prototype.has(key)
has方法返回一个布尔值，表示某个键是否在当前 Map 对象之中。
const m = new Map();
m.set("edition", 6);
m.set(262, "standard");
m.set(undefined, "nah");
m.has("edition"); // true
m.has("years"); // false
m.has(262); // true
m.has(undefined); // true
复制代码（5）Map.prototype.delete(key)
delete方法删除某个键，返回true。如果删除失败，返回false。
const m = new Map();
m.set(undefined, "nah");
m.has(undefined); // true
m.delete(undefined);
m.has(undefined); // false
复制代码（6）Map.prototype.clear()
clear方法清除所有成员，没有返回值。
let map = new Map();
map.set("foo", true);
map.set("bar", false);
map.size; // 2
map.clear();
map.size; // 0
复制代码（1）size 属性
size属性返回 Map 结构的成员总数。
const map = new Map();
map.set("foo", true);
map.set("bar", false);
map.size; // 2
复制代码（2）Map.prototype.set(key, value)
set方法设置键名key对应的键值为value，然后返回整个 Map 结构。如果key已经有值，则键值会被更新，否则就新生成该键。
const m = new Map();
m.set("edition", 6); // 键是字符串
m.set(262, "standard"); // 键是数值
m.set(undefined, "nah"); // 键是 undefined
复制代码set方法返回的是当前的Map对象，因此可以采用链式写法。
let map = new Map().set(1, "a").set(2, "b").set(3, "c");
复制代码（3）Map.prototype.get(key)
get方法读取key对应的键值，如果找不到key，返回undefined。
const m = new Map();
const hello = function () {
console.log("hello");
};
m.set(hello, "Hello ES6!"); // 键是函数
m.get(hello); // Hello ES6!
复制代码（4）Map.prototype.has(key)
has方法返回一个布尔值，表示某个键是否在当前 Map 对象之中。
const m = new Map();
m.set("edition", 6);
m.set(262, "standard");
m.set(undefined, "nah");
m.has("edition"); // true
m.has("years"); // false
m.has(262); // true
m.has(undefined); // true
复制代码（5）Map.prototype.delete(key)
delete方法删除某个键，返回true。如果删除失败，返回false。
const m = new Map();
m.set(undefined, "nah");
m.has(undefined); // true
m.delete(undefined);
m.has(undefined); // false
复制代码（6）Map.prototype.clear()
clear方法清除所有成员，没有返回值。
let map = new Map();
map.set("foo", true);
map.set("bar", false);
map.size; // 2
map.clear();
map.size; // 0
复制代码（1）size 属性
size属性返回 Map 结构的成员总数。
const map = new Map();
map.set("foo", true);
map.set("bar", false);
map.size; // 2
复制代码（2）Map.prototype.set(key, value)
set方法设置键名key对应的键值为value，然后返回整个 Map 结构。如果key已经有值，则键值会被更新，否则就新生成该键。
const m = new Map();
m.set("edition", 6); // 键是字符串
m.set(262, "standard"); // 键是数值
m.set(undefined, "nah"); // 键是 undefined
复制代码set方法返回的是当前的Map对象，因此可以采用链式写法。
let map = new Map().set(1, "a").set(2, "b").set(3, "c");
复制代码（3）Map.prototype.get(key)
get方法读取key对应的键值，如果找不到key，返回undefined。
const m = new Map();
const hello = function () {
console.log("hello");
};
m.set(hello, "Hello ES6!"); // 键是函数
m.get(hello); // Hello ES6!
复制代码（4）Map.prototype.has(key)
has方法返回一个布尔值，表示某个键是否在当前 Map 对象之中。
const m = new Map();
m.set("edition", 6);
m.set(262, "standard");
m.set(undefined, "nah");
m.has("edition"); // true
m.has("years"); // false
m.has(262); // true
m.has(undefined); // true
复制代码（5）Map.prototype.delete(key)
delete方法删除某个键，返回true。如果删除失败，返回false。
const m = new Map();
m.set(undefined, "nah");
m.has(undefined); // true
m.delete(undefined);
m.has(undefined); // false
复制代码（6）Map.prototype.clear()
clear方法清除所有成员，没有返回值。
let map = new Map();
map.set("foo", true);
map.set("bar", false);
map.size; // 2
map.clear();
map.size; // 0
复制代码3、遍历方法
Map 结构原生提供三个遍历器生成函数和一个遍历方法。
Map.prototype.keys()：返回键名的遍历器。Map.prototype.values()：返回键值的遍历器。Map.prototype.entries()：返回所有成员的遍历器。Map.prototype.forEach()：遍历 Map 的所有成员。
需要特别注意的是，Map 的遍历顺序就是插入顺序。
// 遍历方法
const m2 = new Map().set("a", 1).set("b", 2).set("c", 3);
for (const item of m2.keys()) {
console.log(item); // a,b,c
}
for (const item of m2.values()) {
console.log(item); // 1,2,3
}
for (const item of m2.entries()) {
console.log(item); // ["a", 1]["b", 2] ["c", 3]
}
复制代码Map 结构转为数组结构，比较快速的方法是使用扩展运算符（...）。
const map = new Map([
[1, 'one'],
[2, 'two'],
[3, 'three'],
]);
[...map.keys()]
// [1, 2, 3]
[...map.values()]
// ['one', 'two', 'three']
[...map.entries()]
// [[1,'one'], [2, 'two'], [3, 'three']]
[...map]
// [[1,'one'], [2, 'two'], [3, 'three']]
复制代码4、与其他数据结构的互相转换
（1）Map 转为数组
前面已经提过，Map 转为数组最方便的方法，就是使用扩展运算符（...）。
const myMap = new Map().set(true, 7).set({ foo: 3 }, ["abc"]);
[...myMap];
// [ [ true, 7 ], [ { foo: 3 }, [ 'abc' ] ] ]
复制代码（2）数组 转为 Map
将数组传入 Map 构造函数，就可以转为 Map。
new Map([
[true, 7],
[{ foo: 3 }, ["abc"]],
]);
// Map {
// true => 7,
// Object {foo: 3} => ['abc']
// }
复制代码（3）Map 转为对象
如果所有 Map 的键都是字符串，它可以无损地转为对象。
function strMapToObj(strMap) {
let obj = Object.create(null);
for (let [k, v] of strMap) {
obj[k] = v;
}
return obj;
}
const myMap = new Map().set("yes", true).set("no", false);
strMapToObj(myMap);
// { yes: true, no: false }
复制代码如果有非字符串的键名，那么这个键名会被转成字符串，再作为对象的键名。
（4）对象转为 Map
对象转为 Map 可以通过Object.entries()。
let obj = { a: 1, b: 2 };
let map = new Map(Object.entries(obj));
复制代码5、算法题解析
349. 两个数组的交集
// Map解题
var intersection = function (nums1, nums2) {
const map = new Map();
nums1.forEach(item => {
map.set(item, true)
})
const res = [];
nums2.forEach(item => {
if (map.get(item)) {
res.push(item)
map.delete(item)
}
})
return res;
};
复制代码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++) {
const t = s[i];
if(map.get(t)) {
stack.push(t) // 入栈
}else {
const top = stack[stack.length - 1] // 获取栈顶元素
if(t === map.get(top)) {
stack.pop();
}else {
return false
}
}
}
return stack.length === 0;
};
复制代码1. 两数之和
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
const map = new Map();
if(nums.length) {
for(let i = 0;i < nums.length; i++) {
const n1 = nums[i]
const n2 = target - n1 // target = 两个整数之和
if(map.has(n2)) {
return [map.get(n2),i]
}else {
map.set(n1,i)
}
}
}
};
复制代码3. 无重复字符的最长子串
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
let l = 0; // 左指针的初始位置
let res = 0; // 长度初始值为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;
};
复制代码10、树
- 一种分层数据的抽象模型
- 前端工作常见的树：
DOM树，级联选择器，树形控件等。 JS没有树，可以用Object和Array构建树。
// 树的模型
{
value:'gd',
id:19,
children:[
{
value:'gz',
id:2344,
children:[
{
value:'ht',
id:36888,
}
]
}
]
}
复制代码- 树的常用操作：深度、广度优先遍历，先中后序遍历
10-1深度、广度优先遍历
可以这么理解：深度优先遍历表示从头一页一页的看一本书，而广度优先遍历表示：先看书的目录。再深入了解书的章节
10-2深度优先遍历的算法口诀
- 访问根节点
- 对根节点的
children挨个进行深度优先遍历(即递归)
代码实现
const tree = {
val: 'a',
children: [{
val: 'b',
children: [{
val: 'd',
children: [],
}, {
val: 'e',
children: [],
}],
}, {
val: 'c',
children: [{
val: 'f',
children: [],
}, {
val: 'g',
children: [],
}],
}],
}
const dfs = (root) => {
console.log(root.val);
root.children.forEach(dfs) // 采用递归调用
}
dfs(tree); // a,b,d,e,c,f,g
复制代码10-3广度优先遍历的算法口诀
- 新建一个队列，把根节点挨个入队
- 把对头出队，进行访问
- 把对头的
children挨个入队 - 重复2,3的步骤，直到队列为空
const tree = {
val: 'a',
children: [{
val: 'b',
children: [{
val: 'd',
children: [],
}, {
val: 'e',
children: [],
}],
}, {
val: 'c',
children: [{
val: 'g',
children: [],
}, {
val: 'f',
children: [],
}],
}],
}
const bfs = (root) => {
const q = [root]
while (q.length > 0) {
const n = q.shift(); // 对头出队
console.log(n.val)
n.children.forEach(item => { // 把对头的`children`挨个入队
q.push(item)
})
}
}
bfs(tree) // a,b,c,d,e,f,g
复制代码10-4二叉树
- 树中的节点最多只能有两个字节点
- 在
JS中通常用Object来模拟二叉树
二叉树模型
{
val:'1',
left:{
val:'2',
left:null,
right:null
},
right:{
val:'3',
left:null,
right:null
}
}
复制代码10-4-1二叉树，先序遍历算法口诀
代码实现
const bt = {
val: '1',
left: {
val: '2',
left: {
val: '4',
left: null,
right: null
},
right: {
val: '5',
left: null,
right: null
}
},
right: {
val: '3',
left: {
val: '6',
left: null,
right: null
},
right: {
val: '7',
left: null,
right: null
}
}
}
// (递归版)
const preorder = (root) => {
if (!root) {
return false
}
console.log(root.val) // 1,2,4,5,3,6,7
preorder(root.left) // 对根节点的左子树进行先序遍历。
preorder(root.right) // 对根节点的右子树进行先序遍历。
}
preorder(bt)
/**
* 非递归
* 由于先访问根节点，可以看做栈来操作
*/
const preorder = (root) => {
if (!root) {
return false
}
const stack = [root];
while (stack.length) {
const n = stack.pop(); // 先访问栈顶元素，即根节点
console.log(n.val); // 1,2,4,5,3,6,7
// 根据后进先出，先操作右子树进行先序遍历
if (n.right) stack.push(n.right)
if (n.left) stack.push(n.left)
}
}
preorder(bt)
复制代码10-4-2二叉树，中序遍历算法口诀
代码实现
const bt = require('./bt.js')
// 递归
const inorder = (root) => {
if (!root) {
return false
}
inorder(root.left) // 对根节点的左子树进行中序遍历。
console.log(root.val) // 4,2,5,1,6,3,7
inorder(root.right) // 对根节点的右子树进行中序遍历。
}
inorder(bt)
/**
* 非递归
*/
const inorder = (root) => {
if (!root) {
return false
}
const stack = [];
let p = root;
while (stack.length || p) {
while (p) {
stack.push(p);
p = p.left
}
const n = stack.pop();
console.log(n.val); // 4,2,5,1,6,3,7
p = n.right
}
}
inorder(bt)
复制代码10-4-2二叉树，后序遍历算法口诀
代码实现
const bt = require('./bt.js')
// 递归版
const mdorder = (root) => {
if (!root) {
return false
}
mdorder(root.left) // 对根节点的左子树进行中序遍历。
mdorder(root.right) // 对根节点的右子树进行中序遍历。
console.log(root.val) // 4,5,2,6,7,3,1
}
mdorder(bt)
// 非递归
const mdorder = (root) => {
if (!root) {
return false
}
const stack = [root];
const outPutStack = [];
while (stack.length) {
const n = stack.pop(); // 先访问栈顶元素，即根节点
outPutStack.push(n) // 存入到逆向输出的数组里
if (n.left) stack.push(n.left)
if (n.right) stack.push(n.right)
}
while (outPutStack.length) {
const n = outPutStack.pop();
console.log(n.val); // 4,5,2,6,7,3,1
}
}
mdorder(bt)
复制代码10-5算法题解析
104. 二叉树的最大深度
var maxDepth = function(root) {
let res = 0 ;
const dfs = (item,l) => {
if(!item) {return false;}
if(!item.left && !item.right) {
res = Math.max(res, l)
}
dfs(item.left,l+1)
dfs(item.right,l+1)
}
dfs(root,1)
return res
};
复制代码111. 二叉树的最小深度
/**
* @param {TreeNode} root
* @return {number}
*/
var minDepth = function(root) {
if (!root) {
return 0;
}
const q = [[root,1]]
while(q.length) {
const [n,l] = q.shift();
if(!n.left && !n.right) {
return l;
}
if(n.left) q.push([n.left, l+ 1])
if(n.right) q.push([n.right, l+ 1])
}
};
复制代码102. 二叉树的层序遍历
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
if(!root) {return [];}
const q = [[root,0]];
let res = [];
while(q.length) {
const [n,leave] = q.shift();
if(!res[leave]) { // 层级为0 的时候，根节点入队
res.push([n.val])
}else {
res[leave].push(n.val) // 根据层级添加对应的val值
}
console.log(n.val,leave)
if(n.left) q.push([n.left,leave+1]);
if(n.right) q.push([n.right,leave+1]);
}
return res;
};
复制代码94. 二叉树的中序遍历
/**
* @param {TreeNode} root
* @return {number[]}
* 二叉树中序遍历
*/
var inorderTraversal = function(root) {
if(!root) {return [];}
const stack = [];
const res =[];
let p = root;
while(stack.length || p) {
while(p) {
stack.push(p);
p = p.left;
}
const n = stack.pop();
res.push(n.val)
p = n.right;
}
return res;
};
复制代码112. 路径总和
/**
* @param {TreeNode} root
* @param {number} targetSum
* @return {boolean}
*/
var hasPathSum = function(root, targetSum) {
if(!root) {return false;}
let res = false;
const dfs = (n,sum) => {
// 深度优先遍历
console.log(n.val,sum);
if(!n.left && !n.right && sum == targetSum) {
res = true;
}
if(n.left) dfs(n.left,sum + n.left.val);
if(n.right) dfs(n.right,sum + n.right.val);
}
dfs(root,root.val)
return res;
};
复制代码© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/4d3cf227a85d7e79f5d6b4efb6bde3e8.jpg)
![[桜井宁宁] 爆乳奶牛少女cos写真-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/d40483e126fcf567894e89c65eaca655.jpg)
