前端面试总结--数据结构与算法五

发布时间:2019-08-19 发布网站:脚本宝典
脚本宝典收集整理的这篇文章主要介绍了前端面试总结--数据结构与算法五脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。

集合

集合是由一组无序且唯一的项组成。这个数据结构使用了与有限集合相同的数学概念。

创建一个集合

function Set(){
    VAR ITems = {};
}

集合的方法

add(value) -- 向集合添加一个新的项
remove(value) -- 从集合移除一个值
has(value) -- 如果值在集合中,返回true,否则返回false
clear() -- 移除集合中的所有项
size() -- 返回集合所包含元素的数量
values() -- 返回一个包含集合中所有值的数值

完整的集合代码

function Set(){
   var items = {};
   
   this.has = function(value){
       return items.hasOwnPRoPErty(value);
   };
   
   this.add = function(value) {
       if(!this.has(value)){
           items[value] = value;
           return true; 
       }
       return false;
   };
   
   this.remove = function(value) {
       if(this.has(value)){
           delete items[value];
           return true;
       }
       return false;
   };
   
   this.clear = function() {
       items = {};
   };
   
   this.size = function () {
       return Object.keys(items).length;
   };
   
   this.values = function(){
       return Object.keys(items);
   };
   
}
@H_88_126@集合操作

并集--对于给定的两个集合,返回一个包含两个集合中所有元素的新集合。

this.union = function(otherSet) {
    var unionSet = new Set();
    
    var values = this.values();
    for(var i=0;i<values.length;i++){
        unionSet.add(value[i]);
    }
    
    values = otherSet.values();
    for(var i=0;i<values.length;i++) {
        unionSet.add(values[i]);
    }
    return unionSet;
}

交集 -- 集合A和B的交集是元素存在于A中,其存在于B中。

this.intersection = function(otherSet) {
    var intersectionSet = new Set();
    
    var values = this.values();
    for(var i=0;i<values.length;i++){
        if(otherSet.has(values[i])){
            intersectionSet.add(values[i]);
        }
    }
    return intersectionSet;
} 

差集 -- 集合A和B的差集,是元素存在于A中,且元素不存在于B中。

this.difference = function(otherSet){
    var differenceSet = new Set();
    var values = this.values();
    for(var i=0; i<values.length;i++){
        if(!otherSet.has(value[i)){
            differenceSet.add(values[i]);
        }
    }
    return differenceSet;
}

ES6中的Set &amp; WeakSet

ES6的标准中实现了Set的数据结构,它可以这样被使用。

const s = new Set();

[2, 3, 5, 4, 5, 2, 2].foreach(x => s.add(x));

for (let i of s) {
  console.log(i);
}
@H_45_304@// 2 3 5 4

Set 实例的属性和方法

Set 结构的实例有以下属性。

  • Set.prototype.constructor:构造函数,默认就是Set函数。

  • Set.prototype.size:返回Set实例的成员总数

Set 实例的方法分为两大类:操作方法(用于操作数据)和遍历方法(用于遍历成员)。下面先介绍四个操作方法。

  • add(value):添加某个值,返回Set结构本身。

  • delete(value):删除某个值,返回一个布尔值,表示删除是否成功。

  • has(value):返回一个布尔值,表示该值是否为Set的成员。

  • clear():清除所有成员,没有返回值。

*去除数值重复元素的方法

// 去除数组的重复成员
[...new Set(array)]

*Array.From方法可以将 Set 结构转为数组

const items = new Set([1, 2, 3, 4, 5]);
const array = Array.from(items);

遍历操作

Set 结构的实例有四个遍历方法,可以用于遍历成员。

  • keys():返回键名的遍历器

  • values():返回键值的遍历器

  • entries():返回键值对的遍历器

  • forEach():使用回调函数遍历每个成员

Set的遍历顺序就是插入顺序。这个特性有时非常有用,比如使用Set保存一个回调函数列表,调用时就能保证按照添加顺序调用。
keys方法、values方法、entries方法返回的都是遍历器对象。由于 Set 结构没有键名,只有键值(或者说键名和键值是同一个值),所以keys方法和values方法的行为完全一致。

let set = new Set(['red', 'green', 'blue']);

for (let item of set.keys()) {
  console.log(item);
}
// red
// green
// blue

for (let item of set.values()) {
  console.log(item);
}
// red
// green
// blue

for (let item of set.entries()) {
  console.log(item);
}
// ["red", "red"]
// ["green", "green"]
// ["blue", "blue"]

Set结构的实例的forEach方法,用于对每个成员执行某种操作,没有返回值。

 let set = new Set([1, 2, 3]);
set.forEach((value, key) => console.log(value * 2) )
// 2
// 4
// 6

实现并集(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}

// 差集
let difference = new Set([...a].filter(x => !b.has(x)));
// Set {1}  

WeakSet

WeakSet 结构与 Set 类似,也是不重复的值的集合。但是,它与 Set 有两个区别。

首先,WeakSet 的成员只能是对象,而不能是其他类型的值。

const ws = new WeakSet();
ws.add(1)
// TypeError: Invalid value used in weak set
ws.add(Symbol())
// TypeError: invalid value used in weak set

上面代码试图向 WeakSet 添加一个数值和Symbol值,结果报错,因为 WeakSet 只能放置对象。

其次,WeakSet 中的对象都是弱引用,即垃圾回收机制不考虑 WeakSet 对该对象的引用,也就是说,如果其他对象都不再引用该对象,那么垃圾回收机制会自动回收该对象所占用的内存,不考虑该对象还存在于 WeakSet 之中。

这是因为垃圾回收机制依赖引用计数,如果一个值的引用次数不为0,垃圾回收机制就不会释放这块内存。结束使用该值之后,有时会忘记取消引用,导致内存无法释放,进而可能会引发内存泄漏。WeakSet 里面的引用,都不计入垃圾回收机制,所以就不存在这个问题。因此,WeakSet 适合临时存放一组对象,以及存放跟对象绑定的信息。只要这些对象在外部消失,它在 WeakSet 里面的引用就会自动消失。

由于上面这个特点,WeakSet 的成员是不适合引用的,因为它会随时消失。另外,由于 WeakSet 内部有多少个成员,取决于垃圾回收机制有没有运行,运行前后很可能成员个数是不一样的,而垃圾回收机制何时运行是不可预测的,因此 ES6 规定 WeakSet 不可遍历。

WeakSet的应用

WeakSet 结构有以下三个方法。

  • WeakSet.prototype.add(value):向 WeakSet 实例添加一个新成员。

  • WeakSet.prototype.delete(value):清除 WeakSet 实例的指定成员。

  • WeakSet.prototype.has(value):返回一个布尔值,表示某个值是否在WeakSet 实例之中。

 const ws = new WeakSet();
    const obj = {};
    const foo = {};
    
    ws.add(window);
    ws.add(obj);
    
    ws.has(window); // true
    ws.has(foo);    // false
    
    ws.delete(window);
    ws.has(window);    // false

WeakSet没有size属性,没有办法遍历它的成员。

    ws.size // undefined
    ws.forEach // undefined
    
    ws.forEach(function(item){ console.log('WeakSet has ' + item)})

// TypeError: undefined is not a function

上面代码试图获取size和forEach属性,结果都不能成功。

WeakSet 不能遍历,是因为成员都是弱引用,随时可能消失,遍历机制无法保证成员的存在,很可能刚刚遍历结束,成员就取不到了。WeakSet 的一个用处,是储存 DOM 节点,而不用担心这些节点从文档移除时,会引发内存泄漏。

参考:

  1. Learning Javascript Data Structures and Algorithms

  2. Set和Map数据结构

推荐一个找vue,Angular组件的轮子工厂

前端面试总结--数据结构与算法一
前端面试总结--数据结构与算法二
前端面试总结--数据结构与算法三
前端面试总结--数据结构与算法四

脚本宝典总结

以上是脚本宝典为你收集整理的前端面试总结--数据结构与算法五全部内容,希望文章能够帮你解决前端面试总结--数据结构与算法五所遇到的问题。

如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。