基本概念

所谓贪心是指：在对问题求解时，总是做出在当前看来是最好的选择。
也就是说，不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优解。

贪心法没有固定的算法框架，算法设计的关键是贪心策略的选择。

注意：

• 贪心算法不是对所有问题都能得到整体最优解。
• 选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。

所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。

网络的网络

网络把主机连接起来，而互联网是把多种不同的网络连接起来，因此互联网是网络的网络。

操作系统

1.一个二进制文件运行出结果，操作系统做了什么（这是一个很全面的题）

2.死锁的条件及银行家算法、资源分配图之类的

3.进程间通信方式

1

信号、管道、消息队列、共享内存

数据结构与算法

1.数组、链表（单向、双向、双端）、栈和队列、二叉树、红黑树、哈希表、堆（最大和最小）、图

2.个人经验：栈和队列、哈希表、链表、二叉树的题较多，图的较少

3.查找：二分查找及其变形

4.二叉树：前序、中序、后序遍历，按规定方式打印，两个节点之间操作（最近公共祖先、距离）等问题。

5.最大堆和最小堆：大数量级数据找最大几个等问题、堆如何调整等问题。

6.图：深度优先、广度优先、单源最小路径Dijkstra，任意两点间最短路径Floyd-Warshall，最小生成树Prime和Kruskal

7.红黑树：特点及如何调整（基本上没人让你手撸红黑树）

8.栈和队列：经常作为算法题要用到的数据结构

8.八大排序：3个简单的：冒泡、选择、插入及其优化，5个高级的：快速排序、归并排序、堆排序、希尔排序、桶排序（快排、归并、堆很重要，经常手撸）

9.时间复杂度及空间复杂度分析

10.动态规划dp：这个比较难，背包问题之内的

推荐：数据结构C语言版（严蔚敏）、Java数据结构和算法（Robert Lafore）、剑指offer及leetcode刷题、大神可以看一下算法导论

Mysql

数据库三范式

第一范式（1NF）

无重复的列：数据库表的每一列都是不可分割的基本数据项，同一列中不能同时有多个值，即实体中的某个属性不能有多个值或者不能有重复的属性。如果出现重复的属性，就可能需要定义一个新的实体，新的实体由重复的属性构成，新实体与原实体之间为一对多关系。在第一范式（1NF）中表的每一行只包含一个实例的信息。

举例1：一张学生表Student(stuNo,stuName,age,age,sex)是不符合第一范式的，因为有重复列age属性。去除重复列age以后的Student(stuNo,stuName,age,sex)是符合第一范式的。

第二范式（2NF）

属性完全依赖于主键【消除部分子函数依赖】：数据库表中的每个实例或行必须可以被唯一地区分。为实现区分通常需要为表加上一个列，以存储各个实例的唯一标识。例如员工信息表中加上了员工编号（emp_id）列，因为每个员工的员工编号是唯一的，因此每个员工可以被唯一区分。这个唯一属性列被称为主关键字或主键、主码。实体的属性完全依赖于主关键字。所谓完全依赖是指不能存在仅依赖主关键字一部分的属性，如果存在，那么这个属性和主关键字的这一部分应该分离出来形成一个新的实体，新实体与原实体之间是一对多的关系。为实现区分通常需要为表加上一个列，以存储各个实例的唯一标识。简而言之，第二范式就是属性完全依赖于主键。

这里说的主关键字可能不只有一个，有些情况下是存在联合主键的，就是主键有多个属性。

第三范式（3NF）

属性不依赖于其它非主属性【消除传递依赖】：一个数据库表中不包含已在其它表中已包含的非主关键字信息。

前记

刷了这几年的题，总体还是比较简单的，就是有些填空题比较坑，总结一下题型和技巧。

注意 scanner.close(); 等代码规范，以免出现意想不到的事。毕竟不是项目，代码丑也没人看。

结果填空

购物单

小明刚刚找到工作，老板人很好，只是老板夫人很爱购物。老板忙的时候经常让小明帮忙到商场代为购物。小明很厌烦，但又不好推辞。

这不，XX大促销又来了！老板夫人开出了长长的购物单，都是有打折优惠的。
小明也有个怪癖，不到万不得已，从不刷卡，直接现金搞定。
现在小明很心烦，请你帮他计算一下，需要从取款机上取多少现金，才能搞定这次购物。

取款机只能提供100元面额的纸币。小明想尽可能少取些现金，够用就行了。
你的任务是计算出，小明最少需要取多少现金。

正则表达式

有的时候，恰当地使用正则，可以让我们的工作事半功倍！

如下代码用来检验一个四则运算式中数据项的数目，请填写划线部分缺少的代码。

注意：只填写缺少代码，不要写任何多余内容，例如，已有的双引号。