图结构
图结构什么是图存储结构存储具有”多对多”逻辑关系数据的结构——图存储结构。
与 链表 不同,图中存储的各个数据元素被称为顶点(而不是结点)。
注意:图存储结构中,习惯上用 Vi 表示图中的顶点,且所有顶点构成的集合通常用 V 表示,顶点的集合为 V={V1,V2,V3,V4}。
图存储结构可细分两种表现类型,分别为无向图和有向图。
图的基本常识
弧头和弧尾
有向图中,无箭头一端的顶点通常被称为”初始点”或”弧尾”,箭头直线的顶点被称为”终端点”或”弧头”。
入度和出度
对于有向图中的一个顶点 V 来说,箭头指向 V 的弧的数量为 V 的入度(InDegree,记为 ID(V));箭头远离 V 的弧的数量为 V 的出度(OutDegree,记为 OD(V))。
(V1,V2) 和 <V1,V2> 的区别
无向图中描述两顶点(V1 和 V2)之间的关系可以用 (V1,V2) 来表示,而有向图中描述从 V1 到 V2 的”单向”关系用 <V1,V2> 来表示。 由于图存储结构中顶点之间的关系是用线来表示的,因此 (V1,V2)还可以用来表示无向图中连接 V1 ...
PHP基础(二):面向对象
面向对象和面向过程有什么区别?主要有以下不同:
出发点不同
层次逻辑关系不同
数据处理方式与控制程序方式不同
分析设计与编码转换方式不同
面向对象的特征是什么?抽象封装封装是指将客观事物抽象成类,每个类对自身的数据和方法实行保护。类可以把自己的数据和方法只让可信的类或者对象操作,对不可信的类或者对象进行隐藏。
继承继承是一种联结类的层次结构,并且允许和鼓励类的重用,它提供了一种表述共性的方法。子类可以从父类那里继承方法和成员变量,且子类可以修改和增加新的方法使之更适合特殊的需要。
多态是指:相同的调用语句具有不同的表现形式。
面向对象的开发方式有什么优点?列举以下三个:
较高的开发效率(灵活性)
保证软件的鲁棒性(重用性)
鲁棒是Robust的音译,就是 健壮和强壮 的意思,它也是在异常和危险的情况下系统生存的能力。
保证软件的高可维护性(扩展性)
类与对象的区别是什么?对象是系统中用来描述客观事物的一个实体,它是构成系统的一个基本单位,一个对象由一组属性和对这组属性进行操作的一组服务组成。
类是具有相同属性和服务的一组对象的集合。
类和对象的关系就如同模具和铸件的关系,类 ...
Nginx
HTTP 原理及 Nginx 基础特性Web 服务Nginx: web server(static contents), web reverse proxy (http), cache
Varnish, squid: cache, http headers
Haproxy: tcp reverse proxy, http reverse proxy
Keepalived: HA
Ats: apache traffic server
mogileFS(分布式文件系统), NoSQL(MongoDB)
NginxApache: MPM(prefork, event)
c10k(concurrency), lighttpd, nginx
http protocolRequest => Response
请求报文:
响应报文:
响应码:
1XX: Informational(信息性状态码) 接受的请求正在处理
2XX: Success(成功状态码) 请求正常处理完毕
200 OK:处理成功
201 Created:服务器已经创建了资源
202 Accepted:已经接受请 ...
MySQL基础
MySQL 工作原理大体来说,MySQL 分为: server层和存储引擎层两部分。
连接器:负责跟客户端建立连接、获取权限、维持和管理连接
查询缓存:查询请求先访问缓存(key 是查询的语句,value 是查询的结果),命中则直接返回;不推荐使用缓存,更新会把缓存清除(关闭缓存,参数 query_cache_type 设置为 demand)
分析器:对 SQL 语句做解析,判断SQL是否正确
优化器:确定使用哪个索引,多表关联(join)的时候,决定各个表的连接顺序
执行器:执行语句,先判断用户有无查询权限,使用表定义的存储引擎
SQL语言/锁/事物及隔离级别SQL 是结构化查询语句(Structured Query Language)的缩写,其功能包括:
数据查询语句
数据操纵语句(Data Manipulation Language, DML)
数据定义语句(Data Definition Language, DDL)
数据控制语句(Data Control Language, DCL)
1.SQL 语言的功能1.1 数据查询1select * from ...
用户编程接口
库函数调用与系统调用有什么不同?库函数是语言或应用程序的一部分,它是高层的、完全运行在用户空间、为程序员提供调用真正的在幕后完成实际事物的系统调用接口。而系统函数是内核提供给应用程序的接口,属于系统的一部分。简单地说,库函数调用是语言或应用程序的一部分,而系统调用是操作系统的一部分。
静态连接和动态链接有什么区别?静态链接是指把要调用的函数或者过程直接链接到可执行文件中,成为可执行文件的一部分。换句话说,函数和过程的代码就在程序的.exe文件中,该文件包含了运行时所需的全部代码。
动态链接是相对于静态链接而言的,动态链接所调用的函数代码并没有被复制到程序的可执行文件中,而是仅仅在其中加入了所调用函数的描述信息(往往是一些重定位信息)。仅当应用程序被装入内存开始运行时,在操作系统的管理下,才在应用程序与相应的动态链接库(DDL)之间建立链接关系。当要执行所调用.dll文件中的函数时,根据链接产生的重定位信息,操作系统才转去执行.dll文件中相应的函数代码。
用户态和内核态有什么区别?内核态和用户态是操作系统的两种运行级别,它用于区分不同程序的不同权利。内核态就是拥有资源多的状态,或者说访 ...
查找表相关算法
两类查找问题
查找有无
元素 a 是否存在?set;集合
查找对应关系(键值对应)
元素 a 出现了几次?map;字典或映射
set和mapC++语言中,
set 和 map 的底层实现为平衡二叉树
unordered_set 和 unordered_map 的底层实现为哈希表
通常语言的标准库中都内置 set 和 map
容器类
屏蔽实现细节
了解语言中标准库里常见容器类的使用
常见操作
insert
find
erase
change(map)
set 和 map 可以有不同的底层实现
底层实现
普通数组实现
顺序数组实现
二叉查找树(平衡)
哈希表
插入
O(1)
O(n)
O(logn)
O(1)
查找
O(n)
O(logn)
O(logn)
O(1)
删除
O(n)
O(n)
O(logn)
O(1)
数据的顺序性
数据集中的最大值和最小值
某个元素的前驱和后继
某个元素的 floor 和 ceil
某个元素的排位 rank
选择某个排位的元素 select
面试实战
Intersection of Two Arrays(#349 ...
行为型模式
模板方法模式 TemplateMethod目的模板方法模式是一种行为型的设计模式。可能你已经见过这种模式很多次了。它是一种让抽象模板的子类「完成」一系列算法的行为策略。众所周知的「好莱坞原则」:「不要打电话给我们,我们会打电话给你」。这个类不是由子类调用的,而是以相反的方式。怎么做?当然很抽象啦!换而言之,它是一种非常适合框架库的算法骨架。用户只需要实现子类的一种方法,其父类便可去搞定这项工作了。这是一种分离具体类的简单办法,且可以减少复制粘贴,这也是它常见的原因。
UML图
命令行模式 Command目的为了封装调用和解耦。我们有一个调用程序和一个接收器。 这种模式使用「命令行」将方法调用委托给接收器并且呈现相同的「执行」方法。 因此,调用程序只知道调用「执行」去处理客户端的命令。接收器会从调用程序中分离出来。这个模式的另一面是取消方法的 execute (),也就是 undo () 。命令行也可以通过最小量的复制粘贴和依赖组合(不是继承)被聚合,从而组合成更复杂的命令集。
应用场景
文本编辑器:所有事件都是可以被解除、堆放,保存的命令
Symfony2:SF2 命令可以从 CLI ...
树结构
树结构树的存储结构将具有“一对多”关系的集合中的数据元素按照树的形式进行存储,称这种存储结构为“树型”存储结构。
树的结点
结点:使用树结构存储的每一个数据元素都被称为“结点”
父结点(双亲结点)、子结点和兄弟结点
根结点:每一个非空树都有且只有一个被称为根的结点
叶子结点:若结点没有任何子结点,那么此结点称为叶子结点
子树和空树
子树(注意:单个结点也是一棵树)
空树:如果集合本身为空,那么构成的树就被称为空树。空树中没有结点。
注意:在树结构中,对于具有同一个根结点的各个子树,相互之间不能有交集。
结点的度和层次
结点的度:对于一个结点,拥有的子树数(结点有多少分支)称为结点的度。
注意:一棵树的度是树内各结点的度的最大值。
结点的层次:从一棵树的树根开始,树根所在层为第一层,根的孩子结点所在的层为第二层, 依次类推。
注意:一棵树的深度是树中结点所在的最大的层次。
注意:若两个结点的父结点虽不相同,但是它们的父结点处在同一层次上,那么这两个结点互为堂兄弟。
有序树和无序树
如果树中结点的子树从左到右看,谁在左边,谁在右边,是有规定的,这棵树称为有序树;反之称为无序树。
注意:在有 ...
PHP基础(一):语言
PHP语言PHP(原始为Personal Home Page的缩写,后为Hypertext Preprocessor)是一种开源脚本语言。它融合了C、Java、Perl等的优势和特点,主要用于服务端的脚本程序,可以完成其他的CGI(Common Gateway Interface,通用网关接口)程序能够完成的工作,如:收集表单数据、生成动态网页 等。
PHP与ASP、JSP有什么区别?ASP、JSP、PHP三者都提供在HTML代码中混合某种程序代码、由语言引擎解释执行,但JSP代码被编译成servlet并由Java虚拟机解释执行,这种编译操作仅在对JSP页面的第一次请求时发生。在ASP、JSP、PHP环境下,HTML代码主要负责描述信息的显示样式,而程序代码则用来描述处理逻辑。普通的HTML页面只依赖于Web服务器,而ASP、JSP、PHP页面需要附加的语言引擎分析和执行程序代码。程序代码的执行结果被重新嵌入到HTML代码中,然后一起发送给浏览器。ASP、JSP、PHP三者都是面向web服务器的技术,客户端浏览器不需要任何附加的软件支持。
PHP与HTML有什么区别?PHP解析器解析一 ...
RESTful架构风格
RESTful架构风格RESTful是一种遵守REST设计的架构风格。
RESTREST是Representational State Transfer的缩写,表示表述性状态转移。
资源
REST是面向资源的,资源是网络上的一个实体,可以是一个文件、一张图像、一首歌曲,甚至是一个服务。资源可以设计地很抽象,但只要是具体信息,就可以是资源,因为资源的本质是一串二进制数据。并且每个资源必须有URL,通过URL来找到资源。
表述
资源在某个特定时刻的状态说明被称为表述(Representation),表述由数据和描述数据的元数据(如HTTP报文)组成。资源的表述有多种格式,这些格式也被称为MIME类型,如文本的TXT格式、图像的PNG格式、视频的mkv格式等。一个资源可以有多种表述,例如服务器响应一个请求,返回的资源可以是json格式的数据,也可以是xml格式的数据。
表述性状态转移
表述性状态转移的目的是操作资源,通过转移和控制资源的表述就能实现此目的。例如客户端可以向服务器发送GET请求,服务器将资源的表述转移到客户端;客户端也可以向服务器发送POST请求,传递表述改变服务器 ...
调度算法
调度算法有哪些?调度算法分为三大类:
批处理中的调度
交互系统中的调度
实时系统中的调度
批处理中的调度:
先来先服务
短作业优先
最短剩余时间优先
交互式系统中的调度:
时间片轮转调度
高优先级调度
最短进程优先
页面置换算法有哪些?
算法
注释
最优算法
不可实现,但可以用作基准
NRU(最近未使用) 算法
和 LRU 算法很相似
FIFO(先进先出) 算法
有可能会抛弃重要的页面
第二次机会算法
比 FIFO 有较大的改善
时钟算法
实际使用
LRU(最近最少使用)算法
比较优秀,但是很难实现
LFU(最不经常使用)算法
NFU(最不经常使用)算法
和 LRU 很类似
老化算法
近似 LRU 的高效算法
工作集算法
实施起来开销很大
工作集时钟算法
比较有效的算法
影响调度程序的指标有哪些?会有下面几个因素决定调度程序的好坏:
CPU使用率:CPU正在执行任务(即不处于空闲状态)的时间百分比。
等待时间:这是进程轮流执行的时间,也就是进程切换的时间
吞吐量:单位时间内完成进程的数量
响应时间:这是从提 ...
数组中的算法
如何写出正确的程序
明确变量的含义
循环不变量
小数据量调试
大数据量测试
面试实战
Binary Search(#704)
Move Zeros(#283)
Sort Colors(#75)
Two Sum II - Input array is sorted(#167) 思想:对撞指针
Minimum Size Subarray Sum(#209) 思想:滑动窗口
Longest Substring Without Repeating Characters(#3) 思想:滑动窗口
程序见代码。
TCP篇
TCP(Transimission Control Protocol)是一种 面向连接的、可靠的、基于字节流的 通信协议,位于OSI参考模型的传输层中,具备顺序控制、重发控制、流量控制和拥塞控制等众多功能,保证数据能够安全抵达目的地。
接下来简单了解一下用TCP进行数据传输的通信过程。首先通过三次握手建立连接;然后把发送窗口调整到合适的大小,既能避免网络拥塞,也能提高传输效率;在传输过程中,发出去的每个包都会得到对面的确认,当运送的数据包丢失时,可以执行超时重发,当数据包乱序时(有些数据包先送达目的地,有些后到),通过数据包中的序号可以按顺序排列,同时也能丢弃重复的包;再根据端口号将数据准确传送至通信中的应用程序,端口号相当于程序地址;等到所有数据安全到达后,执行四次挥手断开连接,本次传输完成。
一、连接管理1.1 建立连接(三次握手)客户端会先经历三次握手,然后才能建立连接,具体过程如下:
1.2 断开连接(四次挥手)当要断开连接时,通信两端就会进行四次挥手的操作。由于连接是双向的,所以客户端和服务器端都要发送FIN标志位的包,才算彻底断开了连接,具体过程如下:
为什么需要 T ...
结构型模式
代理模式 Proxy目的代理模式(Proxy)为其他对象提供一种代理以控制对这个对象的访问。使用代理模式创建代理对象,让代理对象控制目标对象的访问(目标对象可以是远程的对象、创建开销大的对象或需要安全控制的对象),并且可以在不改变目标对象的情况下添加一些额外的功能。在某些情况下,一个客户不想或者不能直接引用另一个对象,而代理对象可以在客户端和目标对象之间起到中介的作用,并且可以通过代理对象去掉客户不能看到的内容和服务或者添加客户需要的额外服务。经典例子就是网络代理,你想访问 Facebook 或者 Twitter ,如何绕过 GFW(Great FireWall, 防火长城)?找个代理网站。
应用场景
Doctrine2 使用代理来实现框架的 “魔术”(例如:延迟加载),而用户仍然使用他们自己的实体类且不会使用到代理
UML图
装饰模式 Decorator目的为类实例动态增加新的方法。
应用场景
Zend Framework: Zend_Form_Element 实例的装饰者
Web Service Layer: 用于 REST 服务的 JSON 和 XML 装饰者 (当然,在这个例 ...
栈和队列
栈和队列什么是栈栈存储结构与之前学习的线性存储结构有所差异,这缘于栈对数据“存”和“取”的过程有特殊的要求:
栈只能从表的一端存取数据,另一端是封闭的
在栈中,无论是存数据还是取数据,都必须遵循“先进后出”的原则,即最先进栈的元素最后出栈。
因此,栈是一种只能从表的一端存取数据且遵循“先进后出”原则的线性存储结构。
进栈和出栈
在实际应用中,通常只会对栈执行以下两种操作:
l 向栈中添加元素,此过程被称为“进栈”(入栈或压栈)
l 从栈中取出元素,此过程被称为“出栈”(或弹栈)
栈的具体实现
栈是一种“特殊”的线性存储结构,具体实现有以下两种方式:
顺序栈
链栈
两种实现方式的区别,仅限于数据元素在实际物理空间上存放的相对位置,顺序栈底层采用的是数组;链栈底层采用的是链表。
栈的应用
l 浏览器的“回退”功能
l 检测代码中的括号匹配问题
l 数值的进制转换功能
l …
顺序栈实现及其基本操作见代码。
链栈实现及其基本操作见代码。
什么是队列与栈结构不同的是,队列的两端都是“开口”,要求数据只能从一端进,从另一端出。
通常,称进数据的一端为 “队尾”,出数据的一端为 “ ...