题意：原题链接
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例:
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
很显然，遍历该二位数组是最愚蠢的做法，如果这样做也是挺智障的。那有没有更好的想法呐？emmmmmmm，好吧，还是直说吧，就不废话了 。用我们刚刚讲过的二叉查找树的思路解决。
思路：从该二维数组右上角的数字开始，如果该数字和target相等，那么查找完毕；如果小于，往左走，如果大于往下走 。就像二叉查找树一样，就
继续阅读 >>
刘生玺
18/07/28 15:34:19
最近写项目写得让人有点烦躁，于是找了点新鲜的东西搞——二叉查找树（BST），来提提兴趣，废话不多说，现在就让我们进入BST的世界吧！
1. 定义
二叉查找树（Binary Search Tree），又称二叉排序树（Binary Sort Tree），亦称二叉搜索树。二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
左、右子树也分别为二叉排序树；
比如：
其实说了这么多，不就是左边的节点比根节点小，右边的节点比根节点大嘛。哼~（当然还有相等的情况）
2. BST的来源
数组和链表以及BST在使用数据时的优缺点：
数据结构
优点
缺点
数组
直接使用下标查找
不便于删除或者插入
链表
删除或者插入方便
不便于查找
BST
兼顾具有两者的优点
。。。
可见
继续阅读 >>
刘生玺
18/07/27 14:49:03
最长上升子序列（LIS）的定义：
一个数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN)，我们可以得到一些上升的子序列(ai1, ai2, …, aiK)，这里1 <= i1 < i2 < … < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8).
三种求解方法：
1. O(n^2)的DP
2. O(nlogn)的二分+贪心法
3. O(nlogn)的树状数组优化的DP
题目：Longest Increasing Subsequence
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,
继续阅读 >>
刘生玺
18/07/20 12:10:14
题目：不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
说明：m 和 n 的值均不超过 100。
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
原题链接：https://leetcode-cn.com/explore/interview/card/top-interview-questions-medium/51/dynamic-programming/105/
继续阅读 >>
刘生玺
18/07/19 11:15:47
1. 感性认识“动态规划”
1. 基本概念
是求解决策过程(decision process)最优化的数学方法。把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，是一种解决这类过程优化问题的新方法。
2. 使用技巧：
动态规划算法通常用于求解具有某种最优性质的问题！！！特别的 ，动态规划（Dynamic Programming）对于子问题重叠的情况特别有效，因为它将子问题的解保存在表格中，当需要某个子问题的解时，直接取值即可，从而避免重复计算！
3. 基本思想与策略
我们通过一个问题来引出：
提问：动态规划与分治法有什么不同？
答：适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题
继续阅读 >>
刘生玺
18/07/18 19:02:57
全排列算法思想：
1. 全排列的定义和公式：
从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。由排列的定义，显然不同的顺序是一个不同的排列。从n个元素中取m个元素的所有排列的个数，称为排列数。从n个元素取出n个元素的一个排列，称为一个全排列。
公式：全排列数f(n) = n! (定义0!=1)
2. 时间复杂度：
n个数（字符、对象）的全排列一共有n!种，所以全排列算法至少时间O(n!)的。如果要对全排列进行输出，那么输出的时间要O(n∗n!)，因为每一个排列都有n个数据。所以实际上，全排列算法对大型的数据是无法处理的，而一般情况下也不会要求我们去遍历一个大型数据的全排列。
3. 全排列的初始思想
为了解决一个算法问题，我们选择从基本的想法做起。先回顾一下我们自己是如何写一组数的全排列的：1，3，5，9
首先肯定是 ：
1 ，[3， 5，9的全排列]
3
继续阅读 >>
刘生玺
18/07/17 11:08:08
1. 缓冲管理
为什么引入缓冲? （不想说了）
I/O缓冲方式
1. 单缓冲
块设备输入时, 输入到缓冲区的时间为T, OS将数据从缓冲区传到用户区的时间为M, CPU处理这块数据的时间为C; 显然T和C是可以并行的。
2. 双缓冲
为了加快I/O速度提高设备利用率,又引入了双缓冲机制(缓冲对换 Buffer Swapping); 如果C“<”T, 块设备可连续输入
3.缓冲池(Buffer Pool)
缓冲池的组成
空缓冲链队列emp:由空缓冲区组成
输入缓冲链队列inq:由装满输入数据的缓冲区组成
输出缓冲链队列out:由装满输出数据的缓冲区组成
4种工作缓冲区
收容输入、提取输入、收容输出、提取输出。
从某队列上取下来操作完后再挂到另一队列上
对缓冲池队列操作的两个过程
缓冲池中的队列是临界资源要考虑互斥与同步
2. 设备分配(暂略)
3. 设备驱动
1.设备驱动程序的功能和特点
1.设
继续阅读 >>
刘生玺
18/07/11 11:30:46
主要内容：
1 I/O系统的组成
2 I/O 控制方式
3 缓冲管理
4 设备分配
5 设备驱动
6 磁盘存取设备管理
1. I/O系统的基本功能
隐藏物理设备的细节
与设备的无关性
提高处理机和I/O设备的利用率
对I/O设备进行控制
确保对设备的正确共享
错误处理
说明：1，2是为了方便用户使用I/O设备。3，4是用于提高CPU与I/O设备的利用率。5，6是为了用户在共享设备时提供方便，以保证系统能够有条不紊的运行，当系统发生错误时能够及时发现错误，甚至于自动修正错误。
2. I/O系统的层次结构和模型
（1）I/O软件的层次结构
1.用户层I/O 软件
2.设备独立性软件
3.设备驱动程序
4.中断处理程序
（2）I/O系统的分层
(1) 中断处理程序。
(2) 设备驱动程序。
(3) 设备独立性软件。
3. I/O 设备分类
1.按使用特性分
1. 存储型设备
2. 输入型设备（外设 =>
继续阅读 >>
刘生玺
18/07/11 10:36:12
1. 半导体存储器的分类
从应用角度可将半导体存储器分为两大类：
RAM: RAM中的信息断电后即丢失
ROM: 断电后信息不会丢失，常用来存放不需要改变的信息(如某些系统程序)
1.1 RAM 的分类：
1. 双极型
2. MOS型
双极型:
存取速度快、集成度较低、功耗较大、成本较高等特点，适用于对速度要求较高的高速缓冲存储器
MOS型:
MOS型存储器具有集成度高、功耗低、价格便宜等特点，适用于内存储器
MOS型存储器按信息存放方式又可分为:
1.静态RAM(Static RAM，简称SRAM)
2.动态RAM(Dynamic RAM，简称DRAM)
1. 静态RAM:
SRAM存储电路以双稳态触发器为基础，状态稳定，只要不掉电，信息不会丢失。其优点是不需要刷新，控制电路简单，但集成度较低，适用于不需要大存储容量的计算机系统。
2. 动态RAM:
DRAM存储单元以电容为基础，电路简单，
继续阅读 >>
刘生玺
18/07/09 15:56:55
磁盘存储器具有容量大、存取速度快、支持随机存取的特点，因此被广泛应用于计算机系统中。对于操作系统来说，管理好磁盘的三大要求和目标是：
（1）合理有效利用磁盘：采用合理的文件存储空间分配算法，尽量减少磁盘碎片，提高硬盘的利用率；
（2）提高磁盘的I/O速度：采用缓存等技术，提供访问速度；
（3）提高磁盘可靠性：采用冗余和纠错检错等技术，保证磁盘的数据不会被破坏。
1. 外存的组织方式
文件是存放在磁盘上的，而磁盘是以盘块为基本的分配单位的，那么一个文件是怎么存放在磁盘上的呢，这就是外存的组织方式，主要有以下三种：
1.连续组织方式
2.链接组织方式
3.索引组织方式
文件的物理结构与外存分配方式有关，在采用连续分配方式时的文件物理结构是顺序式的文件结构，在采用链接分配方式将形成链接式文件结构，而索引分配方式将形成索引式文件结构。
1.1 连续组织方式：
要求为每一个文件分配一组相邻接的(也就是连续的)盘块。就好像分配一个连续的数组给文
继续阅读 >>
刘生玺
18/07/08 23:03:30