归档: 2016/8

2016

【贪心算法】Kruskal算法的实现与应用

问题背景假设我们有n个位置的集合V={v1, v2, ..., vn}，我们想在它们顶部建立一个通信网络，网络应该是连通的，即任何两个位置vi和vj之间至少存在一条路径可以相互到达。对于确定的两个位置(vi,vj)，假设在这两个位置之间建立网络连接的费用为c(i,j)，c(i,j) > 0。将上述问题抽象成一个无向图G=(V,E)，用图来表示可能被建立的链接的集合，图的每个结点代表每个位置，

JavaScript-OOP常见模式总结（二）

前言：之前我总结了JavaScript OOP常见的几种模式，今天继续把剩下的几种模式整理总结一遍。这几种模式相对于之前的工厂模式，构造函数模式等基础模式来说算是进阶版，有兴趣可以先看之前那篇博文熟悉一下几种基础的OOP模式，《JavaScript OOP常见模式总结》一、创建对象模式1. 动态原型模式该模式将所有信息都封装在构造函数中，可以在构造函数中初始化原型，并且保持了同时使用构造函数和原型

【贪心算法】区间调度问题总结

1. 单区间调度问题问题定义：存在单一资源，有一组以时间区间形式表示的资源请求reqs={req-1, req-2, ..., req-n}，第i个请求希望占用资源一段时间来完成某些任务，这段时间开始于begin(i)终止于end(i)。如果两个请求req-i和req-j在时间区间上没有重叠，则说这两个请求是相容的，求出这组请求的最大相容子集(最优子集)。举个例子：有一间多媒体课室，某一个周末有多

JavaScript-OOP常见模式总结

一、创建对象模式1. 工厂模式使用一个函数作为工场函数，封装以特定接口创建对象的细节，每次调用工场函数都能生产一个对象。工厂模式的缺点是无法解决对象识别问题(即知道一个对象的类型)，而且每次调用函数，都会创建一个带有属性和方法的对象，也就是说，一些共同的方法会被多次创建，即每个方法都会在每个对象上重新创建一遍。以下面的代码为例，obj1和obj2都分别有各自的setProperty方法，也就是说s