在ACM可以做任何事情之前，必须准备预算并获得必要的财务支持。此行动的主要收入来自不可逆转的捆绑资金（IBM）。背后的想法很简单。每当一些ACM成员有任何小钱时，他拿走所有硬币并将它们扔进存钱罐。你知道这个过程是不可逆转的，硬币不能在不打破猪的情况下被移除。经过足够长的时间，存钱罐里应该有足够的现金来支付需要支付的所有东西。
但是存钱罐存在很大问题。无法确定内部有多少钱。因此，我们可能会将猪分成碎片，但却发现没有足够的钱。显然，我们希望避免这种不愉快的情况。唯一的可能性是称重存钱罐并试图猜测里面有多少硬币。假设我们能够确切地确定猪的重量并且我们知道给定货币的所有硬币的重量。然后，我们可以保证在存钱罐中有一些最低金额。你的任务是找出最坏的情况，并确定存钱罐内的最低现金数量。我们需要你的帮助。不再过早破猪！
输入由T个测试用例组成。它们的数量（T）在输入文件的第一行给出。每个测试用例都以包含两个整数E和F的行开头。它们表示空猪和装满硬币的猪的重量。两种重量均以克为单位。没有猪的体重超过10公斤，这意味着1 <= E <= F <= 10000.在每个测试用例的第二行，有一个整数N（1 <= N <= 500）给出了数字以给定货币使用的各种硬币。在此之后正好是N行，每行指定一种硬币类型。这些行包含两个整数，Pand W（1 <= P <= 50000,1 <= W <= 10000）。P是以货币单位表示的硬币值，W是以克为单位的重量。
为每个测试用例打印一行输出。该行必须包含句子“存钱罐中的最小金额是X.” 其中X是使用给定总重量的硬币可以实现的最小金额。如果无法准确达到重量，请打印一行“这是不可能的”。
3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4
The minimum amount of money in the piggy-bank is 60.
The minimum amount of money in the piggy-bank is 100.
This is impossible.
完全背包问题。重量一定，找到最小的价值的硬币填充。完全背包问题，各个输入项之间没有关系。
#include<iostream>
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
int main() {
ios::sync_with_stdio(false);
int t, e, f, n;
scanf("%d", &t);
while (t--) {
scanf("%d%d", &e, &f);
scanf("%d", &n);
int dp[maxn];
dp[0] = 0;
//初始为最大
for (int i = 1; i < maxn; i++)
dp[i] = INF;
for (int i = 0; i < n; i++) {
//得到输入，直接用该硬币填充，取最小
int weight, value;
scanf("%d%d", &value, &weight);
for (int j = weight; j <= f - e; j++)
//动态转移方程
dp[j] = min(dp[j], dp[j - weight] + value);
}
if (dp[f - e] == INF) printf("This is impossible.\n");
else printf("The minimum amount of money in the piggy-bank is %d.\n", dp[f - e]);
}
return 0;
}
电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。
某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。
多组数据。对于每组数据：
第一行为正整数n，表示菜的数量。n<=1000。
第二行包括n个正整数，表示每种菜的价格。价格不超过50。
第三行包括一个正整数m，表示卡上的余额。m<=1000。
n=0表示数据结束。
对于每组输入,输出一行,包含一个整数，表示卡上可能的最小余额。
1
50
5
10
1 2 3 2 1 1 2 3 2 1
50
0
-45
32
01背包问题，每种饭菜只能购买一份，利用有限的钱，购买价值最大的饭菜。
#include<iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false);
int n, V, w[1005], dp[1005];
while (cin >> n &&n) {
memset(dp, 0, sizeof(dp));
//读入初始值
for (int i = 1; i <= n; i++)
cin >> w[i];
cin >> V;
//将饭菜价格排序
sort(w + 1, w + 1 + n);
if (V < 5) cout << V << endl;
else {
for (int i = 1; i < n; i++) {
for (int j = V - 5; j >= w[i]; j--) {
//动态转移方程
dp[j] = max(dp[j], dp[j - w[i]] + w[i]);
}
}
cout << V - dp[V - 5] - w[n] << endl;
}
}
return 0;
}
RPG girls今天和大家一起去游乐场玩，终于可以坐上梦寐以求的过山车了。可是，过山车的每一排只有两个座位，而且还有条不成文的规矩，就是每个女生必须找个个男生做partner和她同坐。但是，每个女孩都有各自的想法，举个例子把，Rabbit只愿意和XHD或PQK做partner，Grass只愿意和linle或LL做partner，PrincessSnow愿意和水域浪子或伪酷儿做partner。考虑到经费问题，boss刘决定只让找到partner的人去坐过山车，其他的人，嘿嘿，就站在下面看着吧。
聪明的Acmer，你可以帮忙算算最多有多少对组合可以坐上过山车吗？
输入数据的第一行是三个整数K , M , N，分别表示可能的组合数目，女生的人数，男生的人数。
0<K<=10001<=N 和M<=500.
接下来的K行，每行有两个数，分别表示女生Ai愿意和男生Bj做partner.
最后一个0结束输入。
对于每组数据，输出一个整数，表示可以坐上过山车的最多组合数。
6 3 3
1 1
1 2
1 3
2 1
2 3
3 1
0
3
由题目知，考的是二分图匹配问题，输出最大匹配数。邻接矩阵的大小初始化为510*510。
#include<iostream>
using namespace std;
const int maxn = 510;
//used表示每一轮里，妹子有没有被匹配到
int line[maxn][maxn], used[maxn], nxt[maxn];
int k, u, v, n, m;
//利用匈牙利算法实现二分图的匹配，寻找有没有与i匹配的妹子
bool Find(int x) {
for (int i = 1; i <= m; i++) {
//如果互相喜欢，并且妹子名花无主
if (line[x][i] && !used[i]) {
used[i] = 1; //用于记录这个妹子是否使用过了
//如果妹子没有匹配到人，或已经匹配到了这个男生
if (nxt[i] == 0 || Find(nxt[i])) {
nxt[i] = x; //将妹子分配给x男生
return true;
}
}
}
return false;
}
//匹配函数
int match() {
int sum = 0;
//遍历每个男生，看能不能匹配到女生
for (int i = 1; i <= n; i++) {
memset(used, 0, sizeof(used)); //每一轮都需要清空
if (Find(i)) sum++;
}
return sum;
}
int main()
{
ios::sync_with_stdio(false);
while (cin>>k&&k){
cin >> n >> m;
//注意每轮需要对数组进行初始化
memset(nxt, 0, sizeof(nxt));
memset(line, 0, sizeof(line));
while (k--) {
cin >> u >> v;
line[u][v] = 1;
}
cout << match() << endl;
}
return 0;
}
1.JSP概述
* JSP(Java Serve Pages) 是Java Web服务器端的动态资源。它与html页面的作用是相同的，显示数据和获取数据
* JSP = html + Java脚本 + JSP动态标签
* 作用
* Servlet：
> 缺点：不适合设置html响应体，需要大量的response.getWriter().print("<html>");
> 有点：动态资源，可以编程
* html：
> 缺点：html是静态页面，不能包含动态信息
> 优点：不用为输出html标签而发愁
* jsp：
> 优点：在原有html的基础上添加java脚本，构成jsp页面
* jsp和Servle的分工
* JSP： （相当于一个服务员）
> 作为请求发起页面，例如显示表单、超链接。
> 作为请求结束页面，例如显示数据
* Servlet：
> 作为请求中处理数据的环节
* JSP的组成 （相当于一个厨师）
* JSP = html + Java脚本 + JSP动态标签
* jsp中无需创建即可使用的对象一共有9个，被称之为9大内置对象。例如：request对象、out对象
* 3中java脚本：
** <%...%>：java代码片段（常用），用于定义0~N条Java语句！方法内能写什么，它就可以放什么！
** <%=...%>：java表达式，用于输出（常用），用于输出一条表达式的结果。prnt里可以放什么，它就可以放什么
** <%!...%>：声明，用来创建类的成员变量和成员方法（基本不用，但容易考到），类体力可以放什么，它就可以放什么
2.jsp原理（理解）
* jsp其实是一种特殊的Servlet
> 当jsp页面第一次被访问时，服务器会把jsp编译成java文件（这个java其实是一个servlet类）
> 然后再把java编译成.class
> 然后常见该类对象
> 最后调用它的service()方法
> 第二次请求同一jsp时，直接调用service()方法
* 在tomcat的work目录下可以找到jsp对应的.java源代码
* 查看jsp对于java文件
> java脚本
> html
* jsp注释
<%-- ... -- %>：当服务器把jsp编译成java文件时已经忽略了注释部分！
2. JSP三大指令
一个jsp页面中可以有0~N个指令的定义：
(1) page --> 最复杂：<%@page language="java" info="xxx"...%>
* pageEncoding和contentType：
> pageEncoding：它指定当前jsp页面的编码，只要不说谎，就不会有乱码！在服务器要把jsp编译成.java时需要使用此！
> contentType：它表示添加一个响应头:Content-Type！等同与response.setContentType("text/html;charset=utf-8")；
> 如果两个属性只提供一个，name另一个的默认值为设置那一个。
> 如果两个属性都没有设置，name默认为isc
* import：导包！可以出现多次
* errorPage和isErrorPage
> errorPage：当前页面如果抛出异常，那么要转发到哪一个页面，由errorPaget来指定
> isErrorPage：它指定当前页面是否为处理错误的页面！
当该属性为true时这个页面会设置状态码为500！而且这个页面可以使用9大内置对象中的exception!
* autoFlush和buffer
> autoFlush：指定jsp的输出流缓冲区满时，是否自动刷新！默认为true，如果为false，那么在缓冲区满时抛出异常！
> buffer：指定缓冲区大小，默认为8kb，通常不需要修改！
* isELignored：是否忽略el表达式，默认值为false，不忽略，即支持！
* 基本没用：
> language：指定当前jsp编译后的语言类型，默认值为java。
> info：信息
> isThreadSafe：当前的jsp是否支持并发访问！
> session：当前页面是否支持session，如果为false，那么当前页面就没有session这个内置对象！
> extends：让jsp生成的servlet去继承该属性指定的类！
(2) include --> 静态包含
* 与 RequestDispatcher的include()方法的功能相似！
* <%@include%>它是在jsp编译成java文件时完成的！它们共同生成一个java(就是一个servlet)文件，然后再生成一个class!
* RequestDispatcher的include()是一个方法，包含和被包含的是两个servlet，即两个.class！它们只是把响应的内容在运行时合并了！
* 作用：把页面分解了，使用包含的方式组合在一起，这样一个页面中不变的部分，就是一个独立的Jsp,而我们只需要处理变化的页面。
(3) tglib --> 导入标签库
* 两个属性：
> prefix：指定标签库在本页面中的前缀！由我们自己来起名称
> uri：指定标签库的位置！
> <$@taglib prefix="pre" uri="/struts-tags"%> 前缀的用法：<pre:text>
3. 九大内置对象
* out --> jsp的输出流，用来向客户端响应
* page --> 当前jsp对象！ 它的引用类型是Object，即真身中有如下代码：Object page = this ;
* config --> 它对应真身中的ServletConfig对象！
* pageContext --> 一个顶9个！
* request --> HttpServletEequest
* response --> HttpServletResponse
* exception --> Throwable
* session --> HttpSession
* application --> ServletContext
① request
request.getParameter(string);
//注意编码问题，可以将字符串转为字节数组，再创建字符串
request.setAttribute(key,value); value是Object类型
request.getAttribute(key);
//转发
request.getRequestisDispatcher("login.jsp").forward(request,response);
② response
PrintWriter writer = response.getWriter();
③ pageContext
* 一个顶9个！
* Servlet中有三大域，而JSP中有四大域，它就是最后一个域对象！
> ServletContext：整个应用程序
> session：整个会话（一个会话只有一个用户）
> request：一个请求链(指转发、重定向)！
> pageContext：一个jsp页面！这个域是在当前jsp页面和当前jsp页面中使用的标签之间共享数据！
** 域对象
** 代理其他域：pageContext.setAttribute("xxx","XXX",ageContext.SESSION_SCOPE);
** 全域查找：pageConte
4. HttpSession概述
* HttpSession是由JvaWeb提高的，用来会话跟踪的类。session是服务器端对象，保存在服务器端！！！
* HttpSession是Servlet三大域对象之一（request、session、appliaction(ServletContext)），所以它也有setAttribute()、getAttribute()、removeAttribute()方法
* HttpSession底层依赖Cookie，或是URL重写！
5. HttpSession的作用
* 会话范围：会话范围是某个用户从首次访问服务器开始，到该用户关闭浏览器结束！
< 会话：一个用户对服务器的多次连贯性请求！所谓连贯性请求，就是该用户多次请求中间没有关闭浏览器！
* 服务器会为每个客户端创建一个session对象，session就好比客户在服务器端的账户，他们被服务器保存到一个Map中，这个Map被称之为session缓存！
> Servlet中的到session对象：HttpSession session = request.getSession()；
> Jsp中得到session对象：session是jsp内置对象之下，不用创建就可以直接使用！
* session域相关方法
> void setAttribute(String name,Object value)
> Object getAttribute(String name);
> void removeAttribute(String name);
1.什么Servlet
Servlet（Server Applet）是Java Servlet的简称，称为小服务程序或服务连接器，用Java编写的服务器端程序，具有独立于平台和协议的特性，主要功能在于交互式地浏览和生成数据，生成动态Web内容。
狭义的Servlet是指Java语言实现的一个接口，广义的Servlet是指任何实现了这个Servlet接口的类，一般情况下，人们将Servlet理解为后者。Servlet运行于支持Java的应用服务器中。从原理上讲，Servlet可以响应任何类型的请求，但绝大多数情况下Servlet只用来扩展基于HTTP协议的Web服务器
* Serblet 是JavaWeb的三大组件之一（Servlet、Filter、Listener），属于动态资源，服务器小程序
* 作用：处理请求，服务器会把接收到的请求交给Servlet处理
接收请求数据 处理请求 完成响应
* Servlet 功能需要我们自己编写
2.实现Servlet的方式（由我们编写）
实现Servlet有三种方式：
* 实现 javax.servlet.Servlet接口
* 继承 javax.servlet.GenericServlet类
* 继承 javax.servlet.http.HttpServlet类
通常我们会去继承 HttpServlet类来完成我们的Servlet，但是从1 接口学习
** Servlet中的方法大多数不由我们来调用,而是由Tomcat来调用。并且Servlet的对象也不由我们来创建，由Tomcat创建
生命周期方法
* void init(ServletConfig)：出生之后（1次）
* void service(ServletRequest request,ServletResponse response)：每次处理请求时都会被调用
* void destory()：临死之前（1次）
特性：
* 单例，一个类只有一个对象；当然可能存在多个Servlet类！
* 线程不安全的，所以他的效率是高的
Servlet类由我们来写，但对象由服务器来创建，并且由服务器来调用相应的方法
3.GenericServlet
是Servlet接口的实现类，我们可以通过继承GenericServlet来编写自己的Servlet
ServletConfig是什么？ 见图9_3
4.Servlet细节（线程安全）
* 不要创建成员变量，使用局部变量
* 可以创建无状态的成员
* 可以创建有状态的成员，但状态必须为只读的
一个类型的Servlet只有一个实例对象，有可能一个Servlet同时处理多个请求
* 在第一次访问时创建Servlet
* 在服务器启动时创建Servlet,必须在xml写语句,定义启动顺序
<load-on-startup>0</load-on-startup>
<url-pattern>/AServlet</url-pattern> 路径 也可以写通配符 /路径匹配（优先级最高） .扩展名匹配
*只能放在两边，放前面 路径匹配 放后面 扩展名匹配
/*匹配所有url（优先级最低）
*.do 匹配扩展名
5.web.xml文件继承（了解）
在\conf\web.xml中的内容，相当于写到了每个项目的web.xml中，它是所有web.xml的父文件
6.ServletContext（重要）
一个项目只有一个ServletContext对象
我们可以咋N多个Servlet中来获取这个唯一的对象，使用它可以给多个Servlet传递数据
* ServletContext对象的创建是在服务器启动时完成的
* ServletContext对象的销毁是在服务器关闭时完成的
* ServletContext对象的作用是在整个Web应用的动态资源之间共享数据！
* ServletContext的获取
在GenericeServlet或HttpServlet中获取ServletContext对象 (ServletConfig、ServletContextEvent也有这个方法
getServletContext()方法
this.getServletConfig().getServletContext();
7.域对象的功能
域对象就是用来在多个Servlet中传递数据，域对象内部有一个Map用来存储数据
* 域对象必须有要存数据功能
* 域对象必须要有取数据功能
ServletContext是JavaWeb四大域对象之一
（PageContext、ServletRequest、ServletContext）
* ServeletContext对象用来操作数据的方法
* void setAttribute(String name,Object value)：用来存储一个对象（存出一个域属性） 多次调用该方法，并且使用相同的nmae 那么么会覆盖上一次的值
* Object getAttribute(String name)：用来获取ServletContext中的数据
* void removeAttribute(String name)：用来移除ServletContext中的域属性
* Enumeration getAttributeNames()：获取所有域属性的名称
* Sevlet也可以获取初始化参数，但他是局部的参数；
一个Servlet只能获取自己的初始化参数，不能获取别人的，即初始化参数只为一个Serlvet准备
* 可以配置公共的初始化参数，为所有Servlet而用！这需要使用ServletContext才能使用
8.获取资源的方法（**************************）
* 获取真实路径
String path = this.getServletContext().getRealPath("/index.jsp");
* 获取资源流
* 获取资源的路径后，再创建输出流对象！
InputStream input = this.getServletContext().getResourceAsStream("index.jsp");
* 获取所有资源路径
* 获取当前路径下所有资源路径
Set<String> paths = this.getServletContext().getResourcePaths("/WEB-INF");
9.练习：访问量统计
一个项目中所有的资源被访问都要对访问量进行累加
创建一个int类型的变量，用来保存访问量，然后把它保存到ServletContext的域中，这样可以保存所有的Servlet都可以访问到
* 最初时，ServletContext中没有保存访问量相关的属性；
* 当本站被第一次访问时，创建一个变量，设置其值为1；保存到ServletContext中；
* 当以后的访问时，就可以从ServletContext中获取这个变量，然后在其基础上加1。
* 获取ServletContext对象，查看是否存在名为count的属性，如果存在，说明不是第一次访问，如果不存在，说明是第一次访问
* 第一次访问：调用ServletContext的setAttribute()传递一个属性，名为count，值为1；
* 后续访问：调用ServletContext的getAttribute()方法获取原来的访问量，给访问量+1，再调用
ServletContetx()的setAttribute()方法进行设置
* 代码
protected void doGet(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException {
ServletContext app = this.getServletContext();
Integer count =(Integer)app.getAttribute("count");
if(count==null){
app.setAttribute("count", 1);
}else{
app.setAttribute("count", count+1);
}
/*
* 向浏览器输出
* 需要使用响应对象
*/
PrintWriter pw = response.getWriter();
pw.print("<h1>"+count+"</h1>");
}
xml是一种可扩展标记语言，它的设计宗旨是传输数据，而不是显示数据。它的标签没有预定义，需要自行定义标签。
<?xml version="1.0" encoding="UTF-8"?>
<goodslist>
<!-- 下面是商品信息 -->
<good id="1001" birthday="2018-4-1">
<price>12</price>
<name>香蕉</name>
<place>广州</place>
</good>
<good id="1002" birthday="2018-4-2">
<price>13</price>
<name>苹果</name>
<place>陕西</place>
</good>
<Good>xml里区分大小写,属性自己定义,每一个xml必须有一个根标签</Good>
<!-- 约束：约束文档，DTD，Schema -->
</goodslist>
$lt; < 小于
> > 大于
%anp; & 和号
' ' 单引号
" " 引号
ctrl + shift +c 添加注释
dtd约束：内部引入
<?xml version="1.0"?>
<!DOCTYPE note [
<!ELEMENT note (to,from,heading,body)> note下有且只能有这四个标签
<!ELEMENT to (#PCDATA)>
<!ELEMENT from (#PCDATA)>
<!ELEMENT heading (#PCDATA)>
<!ELEMENT body (#PCDATA)>
]>
<note>
<to>George</to>
<from>John</from>
<heading>Reminder</heading>
<body>Don't forget the meeting!</body>
</note>
dtd约束：外部引入本地约束文件，还可以引入网络上的约束
<!ELEMENT note (to,from,heading,body)>
<!ELEMENT to (#PCDATA)>
<!ELEMENT from (#PCDATA)>
<!ELEMENT heading (#PCDATA)>
<!ELEMENT body (#PCDATA)>
xml里引入dtd
<?xml version="1.0"?>
<!DOCTYPE note SYSTEM "note.dtd">
schema约束文档本身也是一个xml文档，后缀为xsd,语法更加容易阅读，功能更加强大。
我们也不需要写schema的约束文档，我们只需要直接使用框架提供给我们的约束文档，里面有命名空间。
<?xml version="1.0"?>
<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema" //给xmlns起别名xs
targetNamespace="http://www.w3school.com.cn"
xmlns="http://www.w3school.com.cn" //命名空间
elementFormDefault="qualified">
<xs:element name="note"> //xs:表示使用xs里的标签
<xs:complexType>
<xs:sequence>
<xs:element name="to" type="xs:string"/>
<xs:element name="from" type="xs:string"/>
<xs:element name="heading" type="xs:string"/>
<xs:element name="body" type="xs:string"/>
</xs:sequence>
</xs:complexType>
</xs:element>
</xs:schema>
用来解析标签，解析成一个树，并得到一个document对象。
我们可以使用dom4j来进行dom方式的解析，dom4j是一个开源xml解析软件包。
解析的时候需要做哪些事情 (1) 解析根元素 (2) 解析有哪些子元素 (3) 解析一个元素有哪些属性 (4) 得到元素的文本内容 (5) 修改、添加、删除某个元素节点 (6) 修改、添加、删除某个属性
import java.util.Iterator;
import org.dom4j.Attribute;
import org.dom4j.Document;
import org.dom4j.Element;
import org.dom4j.io.SAXReader;
public class ParseXML {
public static void main(String[] args) throws Exception{
SAXReader reader = new SAXReader();
Document document = reader.read("NewFile.xml");
Element root = document.getRootElement();
// System.out.println(root.getName()+":"+root.getData());
Iterator<Element> it = root.elementIterator();
while(it.hasNext()) {
Element ele = it.next();
if(ele.getName().equals(""good")){
Element name = ele.element("name");
if(name!=null) System.out.println(name.getText());
}
System.out.println(ele.getName());
Iterator<Attribute> attributes = ele.attributeIterator();
while(attributes.hasNext()) {
Attribute ab = attributes.next();
System.out.println(ab.getName()+":"+ab.getValue());
}
}
//xml：Element Attribute
Element ele = null;
ele.elementIterator("good")
}
}
//Element.getText()获得标签内容
JavaWeb是以Java语言为基础，使用JSP和Servlet来开发Web程序
JavaEE是Java的企业级应用，里面包含的功能比较多。JavaEE是一个大杂烩，包括Applet、EJB、JDBC、JNDI、Servlet、JSP等技术的标准，运行再一个完整的应用服务器上，用来开发大规模、分布式、健壮的网络应用。
可以粗略的认为JavaWeb就是JavaEE的一部分。
后续学习 SSM、SSH框架
//jsp中引入java类
<%@page import="java.util.Date" %>
//注释
<%-- --%>
//jsp定义表达式
<%! %>
<%
//接受请求这种的数据
String usernmae = request.getParameter("username");
//out可以输出标签
out.println("<font color='green'>注册成功</font>");
%>
//
http协议规定了我们在发起http请求的时候，这个请求的数据包里面都包含了什么样的数据以及数据按照什么样的先后顺序存放在数据包里。
1.http协议
协议：协议的甲乙双方，就是客户端（浏览器）和服务器！
理解成双方通信的格式！
* 请求协议
* 响应协议
2.体系结构
C/S 客户端/服务器结构模型
B/S 浏览器/服务器结构模型
3.Web资源
html静态资源
JSP/Servlet 动态资源
4.Tomcat服务器
默认端口号8080 若要修改 在 server.xml
* bin 可运行文件
* conf 配置文件
* lib jar包
* webapps 存放web项目的目录
* work 运行时生成的文件
响应头 Referer：显示请求来自哪个页面，统计请求量 和 作防盗链
Content-Type：表单的数据类型 提交给服务器的格式化编码数据
状态码：
200 OK 请求成功;
202 Accepted 服务器已经接受请求，但尚未处理;
205 Reset Content 服务器成功处理了请求，且没有返回任何内容；
302 Move temporarily 重定向
4开头 请求错误
404 NotFound 没有找到该资源
5开头 服务器端错误
500 Internal Server Error 无法处理请求
用GET提交数据时，数据会加在路径后面，
而POST请求则不会，Content-Length表示请求体的长度，POST请求有该头。
1、排序的定义
所谓排序，是整理表中的记录，使之按关键字递增（或递减） 有序排列。
2、内排序和外排序
在排序过程中，若整个表都是放在内存中处理，排序时不涉 及数据的内、外存交换，则称之为内排序；
反之，若排序过程中要进行数据的内、外存交换，则称之为 外排序。
3、内排序的分类
内排序：
基于比较的排序算法：插入排序、交换排序、选择排序、归并排序
不基于比较的排序算法：基数排序
基于比较的内排序算法效率：
(1) 最好的平均时间复杂度为O(nlog2 n)。
(2) 最好情况是排序序列正序，此时的时间复杂度为O(n)。
4、内排序算法的稳定性
如果待排序的表中，存在有多个关键字相同的记录，经过排序后这些 具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是稳定的。
反之，若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。
5、正序和反序
若待排序的表中元素已按关键字排好序，称此表中元素为正序；
反之，若待排序的表中元素的关键字顺序正好和排好序的顺序相反， 称此表中元素为反序。
有一些排序算法与初始序列的正序或反序有关，另一些排序算法 与初始序列的情况无关。
主要的插入排序方法：
(1) 直接插入排序 (2) 折半插入排序 (3) 希尔排序
直接插入排序的算法，平均时间复杂度O(n^2)：
public static int[] insertSort(int[] list) {
int first,position;
int temp; //临时存放list[first]
for(first=1;first<list.length;first++) {
if(list[first] < list[first-1]) { //如果list[first]小于左边的有序表最大值
position = first;
temp = list[first];
while(position>0 && list[position-1]>temp) { //找temp的插入位置，将大于它的右移
list[position] = list[position-1];
position--;
}
list[position] = temp;
}
}
return list;
}
查找采用折半查找方法，称为二分插入排序或折半插入排序。
折半插入排序算法：
void BinInsertSort(RecType R[],int n){
int i,j,low,high,mid;
RecType tmp;
for(i=1;i<n;i++){
if(R[i].key<R[i-1].key){
tmp=R[i];
low=0;hight=i-1;
while(low<=high){
mid=(low+high)/2;
if(tmp.key<R[mid].key)
high=mid-1;
else
low=mid+1;
}
for(j=i-1;j>=high+1;j--)
R[j+1]=R[j];
R[high+1]=temp;
}
}
}
折半插入排序采用折半查找，查找效率提高。但元素移动次数不变，仅仅将分散移动改为集合移动。
将排序序列分为d个组，在各组内进行直接插入排序，递减d=d/2，重复之前步骤，直到d=1。
希尔排序算法，时间复杂度约为O(n^1.3)：
public static void shellSort(int[] arr) {
//增量每次都是/2
for(int step = arr.length/2;step>0;step/=2) {
//从增量那组开始进行插入排序，直至完毕
for(int i=step;i<arr.length;i++) {
int j=i;
int temp = arr[i];
//j-step就是代表与它前一组相同位置的元素
while(j-step>=0 && arr[j-step]>temp) {
arr[j] = arr[j-step];
j=j-step;
}
arr[j]=temp;
}
}
}
两个记录反序时进行交换。
常见的交换排序方法：(1) 冒泡排序 (2) 快速排序
冒泡排序算法，平均时间复杂度为O(n^2)：
public static void bubbleSort(int[] list) {
int i,j,temp; bool exchange;
for(i = 0; i<list.length; i++){
exchange=false;
for(j=0; j<list.length-i-1; j++) {
if(list[j]>list[j+1]){
temp = list[j];
list[j]=list[j+1];
list[j+1]=temp;
exchange=true;
}
if(exchange==false) return; //若没有交换的，则直接返回。
}
}
}
每趟使表的第1个元素放入适当位置（归位），将表一分为二，对 子表按递归方式继续这种划分，直至划分的子表长为0或1（递归出 口）。
快速排序算法：
public static void quickSort(int[] arr,int p,int r) {
if(p<r){
int q = partition(arr,p,r);
//对左半段排序
quickSort(arr,p,q-1);
//对右半段排序
quickSort(arr,q+1,r);
}
}
private static int partition(int arr[],int p,int r) {
int i=p,j=r+1;
int x = arr[p];
int temp;
//将<x的元素交换到左边区域
//将>x的元素交换到右边区域
while(true) {
//找到左边大于x的位置，再找到右边小于x的位置
while(arr[++i]<x && i<r);
while(arr[--j]>x);
if(i>=j)break;
//连个位置上的元素进行交换
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
arr[p] = arr[j];//j的位置刚好是分界点
arr[j] = x;
return j;
}
快速排序的平均时间复杂度为O(nlog2 n)，平均所需栈空间为O(log2 n)。
常见的选择排序方法：(1) 简单选择排序 (2) 堆排序
####8.4.1 简单选择排序
简单选择排序算法：
public static void selectionSort(int[] arr) {
//记录当前趟数的最小值的下标
int pos;
//交换的变量
int temp;
//外层循环控制需要排序的趟数
for(int i=0;i<arr.length-1;i++) {
//新的趟数，将下标赋值为i
pos=i;
//内层循环控制遍历数组的个数并得到最大数的下标
for(int j=i+1;j<arr.length;j++)
if(arr[j]<arr[pos]) {
pos=j;
}
//交换
if(pos!=i){
temp = arr[pos];
arr[pos] = arr[i];
arr[i]=temp;
}
}
}
简单选择排序的最好、最坏和平均时间复杂度为O(n^2)。
####8.4.2 堆排序
1、堆的定义
一个序列R[1..n]，关键字分别为k1、k2、… 、kn。
该序列满足如下性质（简称为堆性质）：
① ki≤k2i 且ki≤k2i+1
② ki≥k2i 且ki≥k2i+1
满足第①种情况的堆称为小根堆，满足第②种情况的堆称为大根堆。
2、堆排序算法设计
堆排序的关键是构造堆，这里采用筛选算法建堆。
所谓“筛选”指的是，对一棵左/右子树均为堆的完全二叉树， “调整”根节点使整个二叉树也成为一个堆。
堆排序算法：
public static void heapSort(int[] arr) {
int current;
int i;
//建立初始堆
buildHeap(arr);
for(i = arr.length-1; i>0 ; i--) {
current = arr[i];
arr[i] = arr[0];
insertHeap(arr,current,0,i-1);
}
}
private static void insertHeap(int[] arr,int current,int low,int high) {
int large;
large = 2 * low + 1;
while (large <= high) {
if (large < high&&arr[large] < arr[large + 1])
large++;
if (current > arr[large])
break;
else {
arr[low] = arr[large];
low = large;
large = 2 * low + 1;
}
}
arr[low] = current;
}
//建立初始堆
private static void buildHeap(int[] arr){
for(int left = arr.length/2-1 ; left >= 0 ; left--) {
int current = arr[left];
insertHeap(arr,current,left,arr.length-1);
}
}
堆排序的时间复杂度为O(nlog n)，空间复杂度为O(1)，不稳定。
简单选择排序算法→(利用了连续多次查找最大记录的特性)→堆排序算法
1、归并的思路
归并排序是多次将相邻两个或两个以上的有序表合并成一个 新的有序表。
最简单的归并是将相邻两个有序的子表合并成一个有序的表， 即二路归并排序
二路归并算法：
//归并排序
public static void mergeSort(int[] arr,int left,int right) {
//如果数组长度为1，直接返回
if(left==right) return;
//取中间数，进行拆分
int mid=(left+right)/2;
//左边的数不断进行拆分
mergeSort(arr,left,mid);
//右边的数不断进行拆分
mergeSort(arr,mid+1,right);
//合并
merge(arr,left,mid+1,right);
}
//合并数组
private static void merge(int[] arr,int l,int m,int r) {
//左边数组的大小
int[] leftArray = new int[m-l];
//右边数组的大小
int[] rightArray = new int[r-m+1];
//向两个数组里添加元素
for(int i=l;i<m;i++)
leftArray[i-l]=arr[i];
for(int i=m;i<=r;i++)
rightArray[i-m]=arr[i];
int i=0,j=0;
//传入数组arr的第一个元素
int k=l;
//比较这两个数组的值，哪个小，就往数组上放
while(i<leftArray.length && j<rightArray.length) {
//将较小的数放入数组
if(leftArray[i] <= rightArray[j]) {
arr[k] = leftArray[i];
i++; k++;
}else {
arr[k] = rightArray[j];
j++; k++;
}
}
//将左边数组剩余的数放入大数组
while(i<leftArray.length)
arr[k++]=leftArray[i++];
//将右边数组剩余的数放入大数组
while(j<rightArray.length)
arr[k++]=rightArray[j++];
}
二路归并排序的时间复杂度为O(nlog2 n)，空间复杂度为O(n)。
1、基数排序的概念
基数r：对于二进制数r为2，对于十进制数r为10。
2、基数排序的分类
基数排序有两种：最低位优先（LSD）和最高位优先（MSD）。
过程：
(1) 分配：把各个队列置为空队列，然后考察线性表中的每一个节点，将其放入相应队列中。
(2) 收集：按队列的顺序，将各个队列中的节点收尾相接，得到新的节点序列。
由于数据需要放入队列，又要从队列取出来，下需要大量元素移动。所以排序数据和队列均采用链表存储更好。
基数排序是通过”分配”和”收集”过程来实现排序，不需要关键字的比较。
3、基数排序算法
//数组实现
public static void radixSort(int[] arr) {
int max = findMax(arr,0,arr.length-1);
//需要遍历的次数由数组最大值的位数来决定
for(int i=1;max/i>0; i = i* 10){
int[][] buckets = new int[arr.length][10];
//获取每一位数字(个、十、百...)
for(int j=0;j<arr.length;j++) {
int num = (arr[j/i])%10;
//将其放入桶子里
buckets[j][num] = arr[j];
}
//回收桶子里的元素
int k = 0;
//有10个桶子
for(int j=0;j<10;j++) {
//对每个桶子里的元素进行回收
for(int l=0;l<arr.length;l++) {
//如果桶子里面有元素就回收（数据初始化为0）
if(buckets[l][j]!=0) {
arr[k++] = buckets[l][j];
}
}
}
}
}
//找数组中最大元素
public static int findMax(int[] arr,int l,int r) {
//如果该数组只有一个数，那么对打的就是该数组第一个值了
if(l == r) return arr[l];
int a = arr[l];
int b = findMax(arr, l+1, r);//找出整体的最大值
if(a>b) return a;
else return b;
}
基数排序的时间复杂度为O(d(n+r))，空间复杂度为O(r)。
1、按算法平均时间复杂度分类
(1) 平方阶O(n^2)：直接插入、简单选择、冒泡排序
(2) 线性对数阶O(nlog2 n)：快速排序、堆排序。归并排序
(3) 线性阶O(n)：基数排序
2、按算法空间复杂度分类
(1) O(n)：归并排序，基数排序为O(r)
(2) O(log2 n)：快速排序
(3) O(1)：其他排序方法
3、按算法稳定性分类
(1) 不稳定的：希尔排序、快速排序、堆排序、简单选择排序
(2) 稳定的：其他排序包括 冒泡、插入、归并、基数是稳定的
4、如何选择合适的排序算法
因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法应综合考虑下列因素：
- 待排序的元素数目n（问题规模）；
- 元素的大小（每个元素的规模）；
- 关键字的结构及其初始状态；
- 对稳定性的要求；
- 语言工具的条件；
- 排序数据的存储结构；
- 时间和辅助空间复杂度。
详细内容和总结见PPT。