哲学家就餐问题
-
问题描述
假设有五位哲学家围坐在一张圆形餐桌旁,做以下两件事情之一:吃饭,或者思考。吃东西的时候,他们就停止思考,思考的时候也停止吃东西。餐桌中间有一大碗意大利面,每两个哲学家之间有一只餐叉。因为用一只餐叉很难吃到意大利面,所以假设哲学家必须用两只餐叉吃东西。他们只能使用自己左右手边的那两只餐叉。哲学家从来不交谈,这就很危险,可能产生死锁,每个哲学家都拿着左手的餐叉,永远都在等右边的餐叉(或者相反)。即使没有死锁,也有可能发生资源耗尽。
进程&线程
-
同步机制
临界区(critical section)、互斥量(mutex)、信号量(semaphore)、事件(event)
(1) 临界区:同一进程内,多线程之间的同步。通过对多线程的串行化来访问公共资源或一段代码。
(2) 互斥量:采用互斥对象机制,只有拥有互斥对象的线程才能访问公共资源。可以实现不同或者相同应用程序不同线程的资源共享。
(3) 信号量:允许多个线程在同一时刻访问同一资源。
PV操作:
P操作申请资源:
a. S减一
b. 如果S减一后仍然大于等于0,则进程继续执行
c. 否则进程被阻塞后进入该信号对应的队列中,转入进程调度
V操作释放资源:
a. S加一
b. 如果S加一后仍然大于0,则进程继续执行
c. 否则从该信号对应的等待队列中唤醒一个等待进程,然后返回原进程继续执行或转入进程调度
(3) 事件:通过通知的方式来保持线程的同步。
总结:
互斥量,信号量,事件可以跨进程使用,而临界区只能在进程内部各线程间使用。
最长升序序列
-
题目描述
网易有道笔试题:<叠罗汉>
</div>
描述:输入的为每个人的(体重,身高),在上面的人必须比下面的人体重小,身高低,问最多能叠多少个罗汉。
例如:输入(60,165),(78,175),(65,171),(70,178)
输出:3
**分析**
**a.** 先按照身高(或者体重排序)
【(60,165),(65,171),(78,175),(70,178)】
**b.** 然后将体重单独取出放到数组中去
【60,65,78,70】
**c.** 能够叠罗汉的最多人数就是这个数组的最长升序序列。求最长升序序列可以用以下两种方法:
**一、动态规划**,复杂度为O(n^2)
设d[i]表示以a[i]结尾的最长升序子序列的长度,则可以得到状态转移方程为d[i]=max{1,max{d[j]}+1},其中j=0,1,2,...i-1并且a[j]<a[i]。用一句话概括思路就是每次计算d[i]时,就要扫描数组a中前i-1个元素,如果遇到a[j]>a[i]则跳过a[j]继续扫描j...i-1的元素,否则如果a[j]<a[i]则用以a[j]为结尾的子序列长度+1就是以a[j]为倒数第二个元素,a[i]为倒数第一个元素的最长子序列长度。
09/122014树的总结
-
概述
数据结构中为了存储和查找的方便,用各种树结构来存储文件。涉及到的树结构包括:二叉查找树(二叉排序树)、平衡二叉树(AVL树)、红黑树、B-树、B+树、字典树(trie树)、后缀树、广义后缀树。
</div>09/122014二叉查找树的实现(java)
-
二叉查找树(二叉排序树)
</div>
(图a)
二叉查找树是一种动态查找表(图a),具有这些性质:
(1)若它的左子树不为空,则左子树上的所有节点的值都小于它的根节点的值;
(2)若它的右子树不为空,则右子树上所有节点的值都大于它的根节点的值;
(3)其他的左右子树也分别为二叉查找树;
(4)二叉查找树是动态查找表,在查找的过程中可见添加和删除相应的元素,在这些操作中需要保持二叉查找树的以上性质。
09/112014OS知识点
-
进程、线程
进程就是一个应用程序在处理机上的一次执行过程,它是一个动态的概念,而线程是进程中的一部分,进程包含多个线程在运行。
</div>
(1) 进程:一个程序再一个数据集合上的一次运行
(2) 线程:是进程中的一个实体,是被系统独立调度和执行的基本单元
进程和线程的主要差别在于它们是不同的操作系统资源管理方式。进程有独立的地址空间,一个进程崩溃后,在保护模式下不会对其它进程产生影响,而线程只是一个进程中的不同执行路径。线程有自己的堆栈和局部变量,但线程之间没有单独的地址空间,一个线程死掉就等于整个进程死掉,所以多进程的程序要比多线程的程序健壮,但在进程切换时,耗费资源较大,效率要差一些。但对于一些要求同时进行并且又要共享某些变量的并发操作,只能用线程,不能用进程。
09/112014计算机网络知识点
-
当你输入一个网址的时候,实际会发生什么?
</div>09/112014数据库知识点
-
范式
所谓范式就是符合某一种级别的关系模式的集合。通过分解把属于低级范式的关系模式转换为几个属于高级范式的关系模式的集合。这一过程称为规范化。
1、 第一范式(1NF):一个关系模式R的所有属性都是不可分的基本数据项。
那么符合第一模式的特点就有
1)有主关键字
2)主键不能为空,
3)主键不能重复,
4)字段不可以再分
2、 第二范式(2NF):关系模式R属于第一范式,且每个非主属性都完全函数依赖于键码。
关系中每一个非主属性不部分依赖于主键
3、 第三范式(3NF):关系模式R属于第一范式,且每个非主属性都不传递依赖于键码。
一般满足前三个范式就可以避免数据冗余。
4、 BC范式(BCNF):关系模式R属于第一范式,且每个属性都不传递依赖于键码。即每个决定因素都包含码。
08/272014网易面试准备
- 抽象类和接口
一个类可以有多个接口 只能有继承一个父类
抽象类可以有构造方法 <–> 接口中不能有构造方法。
抽象类中可以包含静态方法 <–> 接口中不能包含静态方法
抽象类中可以有普通成员变量 <–> 接口中没有普通成员变量
抽象类的可以有实现了的方法 <–> 接口里边全部方法都必须是abstract的
抽象类中的抽象方法的访问类型可以是public,protected <–> 接口中的抽象方法只能是public类型的,并且默认即为public abstract类型
抽象类和接口中都可以包含静态成员变量:
抽象类中的静态成员变量的访问类型可以任意 <–> 接口中定义的变量只能是public static final类型,并且默认即为public static final类型。 </div>08/202014网易有道实习笔试题
- 选择填空题(10道)
(1) f(n)=f(n-1)+f(n-1) 递归算法的时间复杂度
(2) 无数平行线,间距H,有一根长为L的针下落,问与线相交的概率答案 p=2L/(πH)
蒲丰投针问题08/152014Markdown 语法
- 兼容 </br> 因为 Markdown 允许 兼容 HTML ,在 Markdown 文件里加上一段 HTML 表格:
Foo1 Foo2 Foo3 Foo1 Foo2 Foo3
-
-
-
-
-