最长递增子序列java

Ⅰ 寻找任意整数数列中之最大递增子数列

java">packagecom;

importjava.util.Stack;

publicclassTest{
	publicstaticvoidmain(String[]args){
		finalint[]a=newint[]{1,2,2,3,1,8,7,5,4};
		finalintsize=a.length;
		
		Stack<Integer>result=newStack<Integer>();
		intre_count=0;
		
		Stack<Integer>st=newStack<Integer>();
		intst_count=0;
		
		intcursor=0;
		while(cursor<size){
			
			st.clear();
			st_count=0;
			
			for(inti=cursor;i<size;i++){
				if(st.isEmpty()){
					st.push(a[i]);
					st_count++;
				}elseif(st.peek()<a[i]){
					st.push(a[i]);
					st_count++;
				}			
			}
			
			if(re_count<st_count){
				result=(Stack<Integer>)st.clone();
				re_count=st_count;
			}
			cursor++;

		}
		
		System.out.println("result:"+result);
	}
	
}

编译过，OK的

用的比较次的方法，但这样一看就懂。
简单说下：st每次循环用到的临时栈。
result结果栈while结束前都会跟st进行一次比较，留下长的那个。
cursor类似游标最开始指向数组第一个元素，并依此移到结尾。

有许多可以优化的，楼主可以自己想想看：
for和while都是可以提前结束的，创建两个栈也是可以优化为一个的（clone的效率不高）...

Ⅱ 设计一个O（n的平方）时间的算法，找出由n个数组成的序列的最长单调递增子序列

用冒泡法 时间复杂度=O(n^2)
以 下是c语言版
#include <stdio.h>
main()
{int a[10];
int i,c,j;
for(i=0;i<10;i++)
{printf("请输入十个数,这是第%d个:",i+1);
scanf("%d",&a[i]);
}
for(i=0;i<10;i++)
{
for(j=10;j>i+1;j--)
{if(a[j-1]<a[j-2])
{c=a[j-1];
a[j-1]=a[j-2];
a[j-2]=c;
}
}
}
printf("从小到大的顺序是:");
for(i=0;i<10;i++)
{printf("\n%d",a[i]);
}
getch();
}

Ⅲ 设计一个O(n2)时间算法,找出由n个数组成的序列的最长单调递增子序列

算法导论15.4-5 请给出一个O(n^2)时间的算法，使之能找出一个n个数的序列中最长的单调递增子序列。

这个题目是在动态规划部分，此处显然是要用到动态规划。

我们知道可以使用动态规划思想的问题的的两个重要的特征是具有最优子结构和重叠子问题。下面就来分析一下这个问题：

对于一个n个元素的序列nums，设其最长单调递增子序列为Sm(n)（m为递增子序列的长度），则对于Sm存在两种情况：

1、如果nums[n]比Sm-1的最后一个元素大，则Sm由Sm-1加nums[n]组成

2、如果nums[n]小于等于Sm-1的最后一个元素，则Sm即为Sm-1

但是这样考虑有问题，因为如果Sm-1的序列有多个，我们则应该每一个都与nums[n]考察，如果nums[n]比所有Sm-1的尾元素都小或相等，而Sm-2的序列中又存在尾元素小于nums[n]的序列，则我们应该如何选择，Sm应该是多少？
Sm-1+nums[n]、Sm-1、Sm-2+nums[n]

所以之前的分析是有问题的，在长度相同的情况下，我们优先选择包含nums[n]的序列作为Sm(n)，因为每一个新加入的元素都可能改变不同长度的递增子序列，因此我们需要维护每一个递增子序列以获取最优。

这里的最优子结构就是n个元素的最长递增子序列是从前n-1个元素结尾的递增子序列中的一个或者再加上nums[n]，这里面自然存在很多重叠子问题。

代码如下：

/************************************************************************/
/* 算法导论15.4-5
* 找出n个数的序列中最长的单调递增子序列
* 利用动态规划思想，时间复杂度为O(n^2)*/
/************************************************************************/
#include<iostream>
using namespace std;
void printSequence(int *b,int* nums,int last);
int main()
{
int n=8;
int nums[9]={0,1,7,8,9,2,3,4,5};
//b存储当前元素所在递增子序列中当前元素的前一个元素序号
//c存储以当前元素结尾的递增子序列长度
//last存储当前元素为止的序列中最长递增子序列的最后一个元素的序号
//maxLen存储当前最长递增子序列的长度
int b[9]={0},c[9]={0},last[9]={0},maxLen=0;
c[1]=1,last[1]=1;
for (int i=1;i<=n;i++)
{
for (int j=1;j<i;j++)
{
if(nums[j]<nums[i] && c[j]+1>c[i])
{
c[i]=c[j]+1;
b[i]=j;
last[i]=i;
maxLen=c[i];
}else if(c[j]>c[i]){
maxLen=c[j];
last[i]=last[j];
}
}
}
cout<<"原序列长度为"<<n<<"，如下："<<endl;
for (int i=1;i<=n;i++)
{
cout<<nums[i]<<" ";
}
cout<<endl<<"最长递增子序列长度为"<<maxLen<<"，如下："<<endl;
printSequence(b,nums,last[n]);
cout<<endl;
return 0;
}

void printSequence(int *b,int* nums,int last)
{
if(b[last]>0)
printSequence(b,nums,b[last]);
cout<<nums[last]<<" ";
}

Ⅳ JAVA题目

J2EE Java2平台企业版
string是引用数据类型
如何取得年月日，小时分秒
public static void main(String[] args)
{
ActionListener time = new ActionListener() { // 监听事件,不然实现不了动态改变时间
public void actionPerformed(ActionEvent e) {
//date对象代表当前的系统时间(毫秒)
Date date = new Date();
//format对象是用来以指定的时间格式格式化时间的
SimpleDateFormat from = new SimpleDateFormat(
"yyyy-MM-dd HH:mm:ss"); //这里的格式可以自己设置
//format()方法是用来格式化时间的方法
String times = from.format(date);
System.out.println(times); }
};
Timer tim = new Timer(1000, time); //这里表示1000毫秒更新一下时间
tim.start(); //启动
}

我这个答案肯定正确啊
下面帮你解释你的答案吧
Date //是在java.util.Date;里面
SimpleDateForma //这个是java.text.SimpleDateFormat;用来输出问本格式的
DateFormat //应该是在java.util.*;里面吧..应该是的

你那个错误是编译就没通过啊
public class Test
那你那个编译写的因该是
javac Test.java 编译的应该是类啊而不是javac time.java 请问你的time什么意思呢,所以你报的异常是找不到time类啊
呵呵...你是初学java吧该答的我都答完了拉!还特地帮你每句都写

如何读写文件
StringBuffer sb = new StringBuffer();
//File file = new FileWindow().load();
File file;
file = new File("F:/jtest/from.txt");
TextReader tr = new TextReader(file);
sb.append(tr.readAll());
Out.println(sb.toString());
String [] tags = {"\"", " ", "'"};
String str;
str = sb.toString();
for(String reg: tags) {
Out.println(reg);

str = str.replaceAll(reg, "");
}
Out.println(str);
抽象类和接口的区别
声明方法的存在而不去实现它的类被叫做抽象类（abstract class），它用于要创建一个体现某些基本行为的类，并为该类声明方法，但不能在该类中实现该类的情况。不能创建abstract 类的实例。然而可以创建一个变量，其类型是一个抽象类，并让它指向具体子类的一个实例。不能有抽象构造函数或抽象静态方法。Abstract 类的子类为它们父类中的所有抽象方法提供实现，否则它们也是抽象类为。取而代之，在子类中实现该方法。知道其行为的其它类可以在类中实现这些方法。
接口（interface）是抽象类的变体。在接口中，所有方法都是抽象的。多继承性可通过实现这样的接口而获得。接口中的所有方法都是抽象的，没有一个有程序体。接口只可以定义static final成员变量。接口的实现与子类相似，除了该实现类不能从接口定义中继承行为。当类实现特殊接口时，它定义（即将程序体给予）所有这种接口的方法。然后，它可以在实现了该接口的类的任何对象上调用接口的方法。由于有抽象类，它允许使用接口名作为引用变量的类型。通常的动态联编将生效。引用可以转换到接口类型或从接口类型转换，instanceof 运算符可以用来决定某对象的类是否实现了接口。
主键是确定数据库中的表的记录的唯一标识字段，可以是表中的一个字段，也可以是表中的多个字段组成的。一旦确定为主键，则该字段不可为空也不可以重复。比如学生表中的学号就可以定义成该表的字段
外键的定义是相对于主键而言的，比如另有一张成绩表，表中也出现了学生表中的对应学号字段，则相对于学生表，学号就是成绩表的外键
String和StringBuffer的区别
STRING的长度是不可变的，STRINGBUFFER的长度是可变的。如果你对字符串中的内容经常进行操作，特别是内容要修改时，那么使用StringBuffer，如果最后需要String，那么使用StringBuffer的toString()方法
try{}catch(){}finally{}结构，try{}内出现异常，try{}内剩下尚未执行的代码还执行吗，finally{}内的代码呢？finally{}后面的代码呢
执行 finally{}内的代码最后执行
排序算法

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

分类

在计算机科学所使用的排序算法通常被分类为：

计算的复杂度（最差、平均、和最好表现），依据串行（list）的大小（n）。一般而言，好的表现是O。(n log n)，且坏的行为是Ω(n2)。对于一个排序理想的表现是O(n)。仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要Ω(n log n)。

记忆体使用量（以及其他电脑资源的使用）

稳定度：稳定排序算法会依照相等的关键（换言之就是值）维持纪录的相对次序。也就是一个排序算法是稳定的，就是当有两个有相等关键的纪录R和S，且在原本的串行中R出现在S之前，在排序过的串行中R也将会是在S之前。

一般的方法：插入、交换、选择、合并等等。交换排序包含冒泡排序（bubble sort）和快速排序（quicksort）。选择排序包含shaker排序和堆排序（heapsort）。

当相等的元素是无法分辨的，比如像是整数，稳定度并不是一个问题。然而，假设以下的数对将要以他们的第一个数字来排序。

(4, 1) (3, 1) (3, 7) (5, 6)

在这个状况下，有可能产生两种不同的结果，一个是依照相等的键值维持相对的次序，而另外一个则没有：

(3, 1) (3, 7) (4, 1) (5, 6) (维持次序)

(3, 7) (3, 1) (4, 1) (5, 6) (次序被改变)

不稳定排序算法可能会在相等的键值中改变纪录的相对次序，但是稳定排序算法从来不会如此。不稳定排序算法可以被特别地时作为稳定。作这件事情的一个方式是人工扩充键值的比较，如此在其他方面相同键值的两个物件间之比较，就会被决定使用在原先资料次序中的条目，当作一个同分决赛。然而，要记住这种次序通常牵涉到额外的空间负担。

排列算法列表

在这个表格中，n是要被排序的纪录数量以及k是不同键值的数量。

稳定的

冒泡排序（bubble sort） — O(n2)

鸡尾酒排序 (Cocktail sort, 双向的冒泡排序) — O(n2)

插入排序 （insertion sort）— O(n2)

桶排序 （bucket sort）— O(n); 需要 O(k) 额外 记忆体

计数排序 (counting sort) — O(n+k); 需要 O(n+k) 额外 记忆体

归并排序 （merge sort）— O(n log n); 需要 O(n) 额外记忆体

原地归并排序 — O(n2)

二叉树排序 （Binary tree sort） — O(n log n); 需要 O(n) 额外记忆体

鸽巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 额外记忆体

基数排序 （radix sort）— O(n·k); 需要 O(n) 额外记忆体

Gnome sort — O(n2)

Library sort — O(n log n) with high probability, 需要 (1+ε)n 额外记忆体

不稳定

选择排序 （selection sort）— O(n2)

希尔排序 （shell sort）— O(n log n) 如果使用最佳的现在版本

Comb sort — O(n log n)

堆排序 （heapsort）— O(n log n)

Smoothsort — O(n log n)

快速排序 （quicksort）— O(n log n) 期望时间, O(n2) 最坏情况; 对于大的、乱数串行一般相信是最快的已知排序

Introsort — O(n log n)

Patience sorting — O(n log n + k) 最外情况时间, 需要 额外的 O(n + k) 空间, 也需要找到最长的递增子序列（longest increasing subsequence）

不实用的排序算法

Bogo排序 — O(n × n!) 期望时间, 无穷的最坏情况。

Stupid sort — O(n3); 递回版本需要 O(n2) 额外记忆体

Bead sort — O(n) or O(√n), 但需要特别的硬体

Pancake sorting — O(n), 但需要特别的硬体

排序的算法

排序的算法有很多，对空间的要求及其时间效率也不尽相同。下面列出了一些常见的排序算法。这里面插入排序和冒泡排序又被称作简单排序，他们对空间的要求不高，但是时间效率却不稳定；而后面三种排序相对于简单排序对空间的要求稍高一点，但时间效率却能稳定在很高的水平。基数排序是针对关键字在一个较小范围内的排序算法。

插入排序

冒泡排序

选择排序

快速排序

堆排序

归并排序

基数排序

希尔排序

插入排序

插入排序是这样实现的：

首先新建一个空列表，用于保存已排序的有序数列（我们称之为"有序列表"）。

从原数列中取出一个数，将其插入"有序列表"中，使其仍旧保持有序状态。

重复2号步骤，直至原数列为空。

插入排序的平均时间复杂度为平方级的，效率不高，但是容易实现。它借助了"逐步扩大成果"的思想，使有序列表的长度逐渐增加，直至其长度等于原列表的长度。

冒泡排序

冒泡排序是这样实现的：

首先将所有待排序的数字放入工作列表中。

从列表的第一个数字到倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，则将它与它的下一位交换。

重复2号步骤，直至再也不能交换。

冒泡排序的平均时间复杂度与插入排序相同，也是平方级的，但也是非常容易实现的算法。

选择排序

选择排序是这样实现的：

设数组内存放了n个待排数字，数组下标从1开始，到n结束。

i=1

从数组的第i个元素开始到第n个元素，寻找最小的元素。

将上一步找到的最小元素和第i位元素交换。

如果i=n－1算法结束，否则回到第3步

选择排序的平均时间复杂度也是O(n²)的。

快速排序

现在开始，我们要接触高效排序算法了。实践证明，快速排序是所有排序算法中最高效的一种。它采用了分治的思想：先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序，这样整个列表就有序了。这是一种先进的思想，也是它高效的原因。因为在排序算法中，算法的高效与否与列表中数字间的比较次数有直接的关系，而"保证列表的前半部分都小于后半部分"就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了，大大减少了数字间不必要的比较。但查找数据得另当别论了。

堆排序

堆排序与前面的算法都不同，它是这样的：

首先新建一个空列表，作用与插入排序中的"有序列表"相同。

找到数列中最大的数字，将其加在"有序列表"的末尾，并将其从原数列中删除。

重复2号步骤，直至原数列为空。

堆排序的平均时间复杂度为nlogn,效率高（因为有堆这种数据结构以及它奇妙的特征，使得"找到数列中最大的数字"这样的操作只需要O(1)的时间复杂度，维护需要logn的时间复杂度），但是实现相对复杂（可以说是这里7种算法中比较难实现的）。

看起来似乎堆排序与插入排序有些相像，但他们其实是本质不同的算法。至少，他们的时间复杂度差了一个数量级，一个是平方级的，一个是对数级的。

平均时间复杂度

插入排序 O(n2)

冒泡排序 O(n2)

选择排序 O(n2)

快速排序 O(n log n)

堆排序 O(n log n)

归并排序 O(n log n)

基数排序 O(n)

希尔排序 O(n1.25)
一、术语session
在我的经验里，session这个词被滥用的程度大概仅次于transaction，更加有趣的是transaction与session在某些语境下的含义是相同的。

session，中文经常翻译为会话，其本来的含义是指有始有终的一系列动作/消息，比如打电话时从拿起电话拨号到挂断电话这中间的一系列过程可以称之为一个session。有时候我们可以看到这样的话“在一个浏览器会话期间，...”，这里的会话一词用的就是其本义，是指从一个浏览器窗口打开到关闭这个期间①。最混乱的是“用户（客户端）在一次会话期间”这样一句话，它可能指用户的一系列动作（一般情况下是同某个具体目的相关的一系列动作，比如从登录到选购商品到结账登出这样一个网上购物的过程，有时候也被称为一个transaction），然而有时候也可能仅仅是指一次连接，也有可能是指含义①，其中的差别只能靠上下文来推断②。

然而当session一词与网络协议相关联时，它又往往隐含了“面向连接”和/或“保持状态”这样两个含义，“面向连接”指的是在通信双方在通信之前要先建立一个通信的渠道，比如打电话，直到对方接了电话通信才能开始，与此相对的是写信，在你把信发出去的时候你并不能确认对方的地址是否正确，通信渠道不一定能建立，但对发信人来说，通信已经开始了。“保持状态”则是指通信的一方能够把一系列的消息关联起来，使得消息之间可以互相依赖，比如一个服务员能够认出再次光临的老顾客并且记得上次这个顾客还欠店里一块钱。这一类的例子有“一个TCP session”或者“一个POP3 session”③。

而到了web服务器蓬勃发展的时代，session在web开发语境下的语义又有了新的扩展，它的含义是指一类用来在客户端与服务器之间保持状态的解决方案④。有时候session也用来指这种解决方案的存储结构，如“把xxx保存在session里”⑤。由于各种用于web开发的语言在一定程度上都提供了对这种解决方案的支持，所以在某种特定语言的语境下，session也被用来指代该语言的解决方案，比如经常把Java里提供的javax.servlet.http.HttpSession简称为session⑥。

鉴于这种混乱已不可改变，本文中session一词的运用也会根据上下文有不同的含义，请大家注意分辨。
在本文中，使用中文“浏览器会话期间”来表达含义①，使用“session机制”来表达含义④，使用“session”表达含义⑤，使用具体的“HttpSession”来表达含义⑥

二、HTTP协议与状态保持
HTTP协议本身是无状态的，这与HTTP协议本来的目的是相符的，客户端只需要简单的向服务器请求下载某些文件，无论是客户端还是服务器都没有必要纪录彼此过去的行为，每一次请求之间都是独立的，好比一个顾客和一个自动售货机或者一个普通的（非会员制）大卖场之间的关系一样。

然而聪明（或者贪心？）的人们很快发现如果能够提供一些按需生成的动态信息会使web变得更加有用，就像给有线电视加上点播功能一样。这种需求一方面迫使HTML逐步添加了表单、脚本、DOM等客户端行为，另一方面在服务器端则出现了CGI规范以响应客户端的动态请求，作为传输载体的HTTP协议也添加了文件上载、cookie这些特性。其中cookie的作用就是为了解决HTTP协议无状态的缺陷所作出的努力。至于后来出现的session机制则是又一种在客户端与服务器之间保持状态的解决方案。

让我们用几个例子来描述一下cookie和session机制之间的区别与联系。笔者曾经常去的一家咖啡店有喝5杯咖啡免费赠一杯咖啡的优惠，然而一次性消费5杯咖啡的机会微乎其微，这时就需要某种方式来纪录某位顾客的消费数量。想象一下其实也无外乎下面的几种方案：
1、该店的店员很厉害，能记住每位顾客的消费数量，只要顾客一走进咖啡店，店员就知道该怎么对待了。这种做法就是协议本身支持状态。
2、发给顾客一张卡片，上面记录着消费的数量，一般还有个有效期限。每次消费时，如果顾客出示这张卡片，则此次消费就会与以前或以后的消费相联系起来。这种做法就是在客户端保持状态。
3、发给顾客一张会员卡，除了卡号之外什么信息也不纪录，每次消费时，如果顾客出示该卡片，则店员在店里的纪录本上找到这个卡号对应的纪录添加一些消费信息。这种做法就是在服务器端保持状态。

由于HTTP协议是无状态的，而出于种种考虑也不希望使之成为有状态的，因此，后面两种方案就成为现实的选择。具体来说cookie机制采用的是在客户端保持状态的方案，而session机制采用的是在服务器端保持状态的方案。同时我们也看到，由于采用服务器端保持状态的方案在客户端也需要保存一个标识，所以session机制可能需要借助于cookie机制来达到保存标识的目的，但实际上它还有其他选择。

三、理解cookie机制
cookie机制的基本原理就如上面的例子一样简单，但是还有几个问题需要解决：“会员卡”如何分发；“会员卡”的内容；以及客户如何使用“会员卡”。

正统的cookie分发是通过扩展HTTP协议来实现的，服务器通过在HTTP的响应头中加上一行特殊的指示以提示浏览器按照指示生成相应的cookie。然而纯粹的客户端脚本如JavaScript或者VBScript也可以生成cookie。

而cookie的使用是由浏览器按照一定的原则在后台自动发送给服务器的。浏览器检查所有存储的cookie，如果某个cookie所声明的作用范围大于等于将要请求的资源所在的位置，则把该cookie附在请求资源的HTTP请求头上发送给服务器。意思是麦当劳的会员卡只能在麦当劳的店里出示，如果某家分店还发行了自己的会员卡，那么进这家店的时候除了要出示麦当劳的会员卡，还要出示这家店的会员卡。

cookie的内容主要包括：名字，值，过期时间，路径和域。
其中域可以指定某一个域比如.google.com，相当于总店招牌，比如宝洁公司，也可以指定一个域下的具体某台机器比如www.google.com或者froogle.google.com，可以用飘柔来做比。
路径就是跟在域名后面的URL路径，比如/或者/foo等等，可以用某飘柔专柜做比。
路径与域合在一起就构成了cookie的作用范围。
如果不设置过期时间，则表示这个cookie的生命期为浏览器会话期间，只要关闭浏览器窗口，cookie就消失了。这种生命期为浏览器会话期的cookie被称为会话cookie。会话cookie一般不存储在硬盘上而是保存在内存里，当然这种行为并不是规范规定的。如果设置了过期时间，浏览器就会把cookie保存到硬盘上，关闭后再次打开浏览器，这些cookie仍然有效直到超过设定的过期时间。

存储在硬盘上的cookie可以在不同的浏览器进程间共享，比如两个IE窗口。而对于保存在内存里的cookie，不同的浏览器有不同的处理方式。对于IE，在一个打开的窗口上按Ctrl-N（或者从文件菜单）打开的窗口可以与原窗口共享，而使用其他方式新开的IE进程则不能共享已经打开的窗口的内存cookie；对于Mozilla Firefox0.8，所有的进程和标签页都可以共享同样的cookie。一般来说是用javascript的window.open打开的窗口会与原窗口共享内存cookie。浏览器对于会话cookie的这种只认cookie不认人的处理方式经常给采用session机制的web应用程序开发者造成很大的困扰。

下面就是一个goolge设置cookie的响应头的例子
HTTP/1.1 302 Found
Location: http://www.google.com/intl/zh-CN/
Set-Cookie: PREF=ID=0565f77e132de138:NW=1:TM=1098082649:LM=1098082649:S=KaeaCFPo49RiA_d8; expires=Sun, 17-Jan-2038 19:14:07 GMT; path=/; domain=.google.com
Content-Type: text/html

这是使用HTTPLook这个HTTP Sniffer软件来俘获的HTTP通讯纪录的一部分

浏览器在再次访问goolge的资源时自动向外发送cookie

使用Firefox可以很容易的观察现有的cookie的值
使用HTTPLook配合Firefox可以很容易的理解cookie的工作原理。

IE也可以设置在接受cookie前询问

这是一个询问接受cookie的对话框。

四、理解session机制
session机制是一种服务器端的机制，服务器使用一种类似于散列表的结构（也可能就是使用散列表）来保存信息。

当程序需要为某个客户端的请求创建一个session的时候，服务器首先检查这个客户端的请求里是否已包含了一个session标识 - 称为session id，如果已包含一个session id则说明以前已经为此客户端创建过session，服务器就按照session id把这个session检索出来使用（如果检索不到，可能会新建一个），如果客户端请求不包含session id，则为此客户端创建一个session并且生成一个与此session相关联的session id，session id的值应该是一个既不会重复，又不容易被找到规律以仿造的字符串，这个session id将被在本次响应中返回给客户端保存。

保存这个session id的方式可以采用cookie，这样在交互过程中浏览器可以自动的按照规则把这个标识发挥给服务器。一般这个cookie的名字都是类似于SEEESIONID，而。比如weblogic对于web应用程序生成的cookie，JSESSIONID=!-145788764，它的名字就是JSESSIONID。

由于cookie可以被人为的禁止，必须有其他机制以便在cookie被禁止时仍然能够把session id传递回服务器。经常被使用的一种技术叫做URL重写，就是把session id直接附加在URL路径的后面，附加方式也有两种，一种是作为URL路径的附加信息，表现形式为http://...../xxx;jsessionid=!-145788764
另一种是作为查询字符串附加在URL后面，表现形式为http://...../xxx?jsessionid=!-145788764
这两种方式对于用户来说是没有区别的，只是服务器在解析的时候处理的方式不同，采用第一种方式也有利于把session id的信息和正常程序参数区分开来。
为了在整个交互过程中始终保持状态，就必须在每个客户端可能请求的路径后面都包含这个session id。

另一种技术叫做表单隐藏字段。就是服务器会自动修改表单，添加一个隐藏字段，以便在表单提交时能够把session id传递回服务器。比如下面的表单
<form name="testform" action="/xxx">
<input type="text">
</form>
在被传递给客户端之前将被改写成
<form name="testform" action="/xxx">
<input type="hidden" name="jsessionid" value="!-145788764">
<input type="text">
</form>
这种技术现在已较少应用，笔者接触过的很古老的iPlanet6(SunONE应用服务器的前身)就使用了这种技术。
实际上这种技术可以简单的用对action应用URL重写来代替。

在谈论session机制的时候，常常听到这样一种误解“只要关闭浏览器，session就消失了”。其实可以想象一下会员卡的例子，除非顾客主动对店家提出销卡，否则店家绝对不会轻易删除顾客的资料。对session来说也是一样的，除非程序通知服务器删除一个session，否则服务器会一直保留，程序一般都是在用户做log off的时候发个指令去删除session。然而浏览器从来不会主动在关闭之前通知服务器它将要关闭，因此服务器根本不会有机会知道浏览器已经关闭，之所以会有这种错觉，是大部分session机制都使用会话cookie来保存session id，而关闭浏览器后这个session id就消失了，再次连接服务器时也就无法找到原来的session。如果服务器设置的cookie被保存到硬盘上，或者使用某种手段改写浏览器发出的HTTP请求头，把原来的session id发送给服务器，则再次打开浏览器仍然能够找到原来的session。

恰恰是由于关闭浏览器不会导致session被删除，迫使服务器为seesion设置了一个失效时间，当距离客户端上一次使用session的时间超过这个失效时间时，服务器就可以认为客户端已经停止了活动，才会把session删除以节省存储空间。

五、理解javax.servlet.http.HttpSession
HttpSession是Java平台对session机制的实现规范，因为它仅仅是个接口，具体到每个web应用服务器的提供商，除了对规范支持之外，仍然会有一些规范里没有规定的细微差异。这里我们以BEA的Weblogic Server8.1作为例子来演示。

首先，Weblogic Server提供了一系列的参数来控制它的HttpSession的实现，包括使用cookie的开关选项，使用URL重写的开关选项，session持久化的设置，session失效时间的设置，以及针对cookie的各种设置，比如设置cookie的名字、路径、域，cookie的生存时间等。

一般情况下，session都是存储在内存里，当服务器进程被停止或者重启的时候，内存里的session也会被清空，如果设置了session的持久化特性，服务器就会把session保存到硬盘上，当服务器进程重新启动或这些信息将能够被再次使用，Weblogic Server支持的持久性方式包括文件、数据库、客户端cookie保存和复制。

复制严格说来不算持久化保存，因为session实际上还是保存在内存里，不过同样的信息被复制到各个cluster内的服务器进程中，这样即使某个服务器进程停止工作也仍然可以从其他进程中取得session。

cookie生存时间的设置则会影响浏览器生成的cookie是否是一个会话cookie。默认是使用会话cookie。有兴趣的可以用它来试验我们在第四节里提到的那个误解。

cookie的路径对于web应用程序来说是一个非常重要的选项，Weblogic Server对这个选项的默认处理方式使得它与其他服务器有明显的区别。后面我们会专题讨论。

关于session的设置参考[5] http://e-docs.bea.com/wls/docs70/webapp/weblogic_xml.html#1036869

~~我要200分~~

Ⅳ 用java求，给定一个字符串,求其中最大连续递增的数字子串(如"acb125vf13679dD4562789ABCDEF"中的"13679")

importjava.util.regex.Matcher;
importjava.util.regex.Pattern;
publicclassNumber{
	publicstaticvoidmain(String[]args){
		StringBuilderstb=newStringBuilder("0,0");//容器!
		Stringstr="acb125vf13679dD4562789ABCDEF";//原串!
		Matchermatcher=Pattern.compile("\d+").matcher(str);//匹配!
		for(intcount=0;matcher.find();){//挑选!
			str=matcher.group();
			for(inti=0;i<str.length()-1;i++){//查看指定规则次数:
				if(str.charAt(i)<str.charAt(i+1))
					count++;
				else
					break;
			}//如果,重新获取的比以前存入的次数更多,就放弃原来存入新的!
			if(Integer.parseInt(stb.substring(0,stb.lastIndexOf(",")))<count){
				stb.delete(0,stb.length());
				stb.append(count+","+str);
			}//每次查看,为了查看,这个可有可无!
			System.out.println(str+"	递增次数:	"+count);
			count=0;//计数器归零!
		}//最后容器里面存入的就是最大的,取出来即可!
		System.out.println("最多的是:"+stb.substring(stb.lastIndexOf(",")+1)+"	次数是:	"+stb.substring(0,stb.lastIndexOf(",")));
	}
}

Ⅵ JAVA动态规划，最长递增子序列的代码太难理解，求大神帮我讲解一下！

第一层的 if 逻辑表示 如果新的一个数A[i]对于 B[]中的数来说是递增的，则len加1，这是记录递增数列长度的主要逻辑。else中的逻辑保证B[]中的数列是最新的递增数列。
举个例子，如果A数组为[1,2,3,4,5, 3.1, 3.2, 3.3, 3.4]
当i=4时 len=4 B=[x,1,2,3,4,x] 循环结束后 len=5 B=[x,1,2,3,4,5] 第一层判断走if
当i=5时 len=5 B=[x,1,2,3,4,5] 循环结束后 len=5 B=[x,1,2,3,3.1,5] 第一层判断走else
当i=6时 len=5 B=[x,1,2,3,3.1,5] 循环结束后 len=5 B=[x,1,2,3,3.1,3.2] 第一层判断走else
当i=7时 len=5 B=[x,1,2,3,3.1,3.2] 循环结束后 len=6 B=[x,1,2,3,3.1,3.2,3.3] 第一层判断走else
...
其中第一层的else中做的工作就是把B从[x,1,2,3,4,5] 一步步变成 [x,1,2,3,3.1,3.2],最终B[]的最后一个元素变成3.2, 在下一次A[i]=3.3的时候，就又会走第一次if的逻辑（len加1）了。

Ⅶ 如何求一个（正数）无序数组中最长有序子数组的长度

据题目的要求，求一维数组中的最长递增子序列，也就是找一个标号的序列b[0],b[1],…,b[m](0 <= b[0] < b[1] < … < b[m] < N)，使得array[b[0]]<array[b[1]]<…<array[b[m]]。

根据无后效性的定义我们知道，将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态来说，它以前各阶段的状态无法直接影响它未来的决策，而只能间接地通过当前的这个状态来影响。换句话说，每个状态都是历史的一个完整总结。
同样的，仍以序列1，-1，2，-3，4，-5，6，-7为例，我们在找到4之后，并不关心4之前的两个值具体是怎样，因为它对找到6没有直接影响。因此，这个问题满足无后效性，可以通过使用动态规划来解决。
可以通过数字的规律来分析目标串：1，-1，2，-3，4，-5，6，-7。
使用i来表示当前遍历的位置
当i=1时，显然，最长的递增序列为（1），序列长度为1.
当i=2是，由于-1<1。因此，必须丢弃第一个值后重新建立串。当前的递增序列为（-1），长度为1。
当i=3时，由于2>1,2>-1。因此，最长的递增序列为（1,2）,(-1,2),长度为2。在这里，2前面是1还是-1对求出后面的递增序列没有直接影响。（但是在其它情况下可能有影响）
依此类推之后，我们得出如下的结论。
假设在目标数组array[]的前i个元素中，最长递增子序列的长度为LIS[i]。那么，
LIS[i+1]=max{1,LIS[k]+1}, array[i+1]>array[k], for any k <= i
即如果array[i+1]大于array[k],那么第i+1个元素可以接在LIS[k]长的子序列后面构成一个更长的子序列。于此同时array[i+1]本身至少可以构成一个长度为1的子序列。
根据上面的分析，就可以得到代码清单：
C++代码：

代码如下:

int Max(int *a, int n)
{
int max = a[0];
for(int i = 1; i < n; i++)
if(max < a[i])
max = a[i];
return max;
}
int LIS(vector<int> &array)
{
int *a = new int[array.size()];
for(int i = 0; i < array.size(); i++)
{
a[i] = 1;//初始化默认的长度
for(int j = 0; j < i; j++) //前面最长的序列
{
if(array [i] > array [j] && a[j] + 1 > a[i]) //当前数字比第j个大，且标记数组需要更新
{
a[i] = a[j] + 1;
}
}
}
return Max(a, array.size());
}

这种方法的时间复杂度为O(N2 + N) = O(N2)

Ⅷ 给定一个顺序存储的线性表,请设计一个算法,查找该线性表中最长递增子序列

解法1：

很明显用动态规划的算法，选取下面的阶段（这种选法极为常见），可使阶段间的关系具有无后效性。
阶段：在所有以元素k结尾的子数组中，选出其中的最长递增子序列，k=1,2...n。
状态：以元素k结尾的最长递增子序列中只有一个最长的递增子序列。
决策：决定元素k结尾的最长递增子序列有k-1种获取的途径，前面以任何一个元素结尾的最长递增子序列都可能成为其的一部分。
这样的时间复杂度为O(n^2)，空间复杂度为O(n)

#include<iostream>
#include<algorithm>
usingnamespacestd;

#defineMAXN1003
intA[MAXN];
intdp[MAXN];

//动态规划思想O(n^2)
intmain()
{
intn,i,j,k;
cin>>n;
for(i=1;i<=n;i++)
cin>>A[i];
dp[1]=1;
//有n个阶段
for(i=2;i<=n;i++)
{
dp[i]=1;//每个阶段只有1个状态
//每个状态有i种决策,以得出以元素i结尾的最长递归子序列的长度
for(j=i-1;j>=0;j--)
{
if(A[i]>A[j])
dp[i]=max(dp[i],dp[j]+1);
}
}
intmaximum=dp[1];
for(i=2;i<=n;i++)
maximum=max(maximum,dp[i]);
cout<<maximum;
}

解法2：
动态规划的时间复杂度一般与空间复杂度相同，因为决定下一个阶段的所有条件我们已存储到dp中，在处理过程中我们可以对已得到的这些条件进行处理来降低时间复杂度。而这里时间复杂度竟比空间复杂度高了O(n)，说明还有可以继续优化的空间。

我们可以统计前面所有阶段的最长递增子序列的长度，将长度相同的最长递增子序列分到同一组中，并只记录它们最大元素的最小值MaxV[长度值]，如果阶段k的元素大于长度为i最长递增子序列的这个最小值MaxV[i]，那么阶段k的最长递增子序列的长度至少为i+1。

而我们发现统计出的MaxV数组具有很好的递增关系（动态规划都是用来解决最优化问题，我们总能通过优化关系对之前统计出的结果进行排序），即如果i<j，那么有MaxV[i]<MaxV[j]，最后用二分查找法来阶段k的元素在MaxV数组中的位置即可。
证明：反证法，假设当i<j<=k，有MaxV[i]>=MaxV[j]，那么存在一个长度为i的递增序列a1a2...ai，且ai是计算到阶段k时所有长度为i的递增序列中最大元素的最小值，以及长度为j的序列b1b2...bj且ai>=bj，由于i<j长度j的序列b1b2...bj包含一个子序列b1b2...bi，且bi<bj<=ai，即长度为i的递增子序列最大元素的最小值不是ai，矛盾。

#include<iostream>
#include<algorithm>

usingnamespacestd;

#defineMAXN1003
intA[MAXN];
intMaxV[MAXN];

//动态规划算法O(nlogn)
intmain()
{
intn,i,j,k;
cin>>n;
for(i=1;i<=n;i++)
cin>>A[i];
MaxV[1]=A[1];
intnmaxv=1;//目前找到的最长递增子序列的长度
//有n个阶段，每个阶段有1个状态
for(i=2;i<=n;i++)
{
//每个状态有nmaxv种决策，以得出以元素i结尾的最长递归子序列的长度
intu=1,v=nmaxv;
while(u<=v)
{
intmid=(u+v)>>1;
if(MaxV[mid]<A[i])
u=mid+1;
else
v=mid-1;
}

//每个元素都会对数组MaxV中的某个元素产生影响
//使用二分搜索确定其在第v+1个位置
nmaxv=max(nmaxv,v+1);
MaxV[v+1]=A[i];
}
cout<<nmaxv;
}

Ⅸ 用Java编写 求一个字符串s的最大连续递增数字子串。

packagetest;

importjava.util.Collections;
importjava.util.Comparator;
importjava.util.LinkedList;
importjava.util.regex.Matcher;
importjava.util.regex.Pattern;

publicclassTester
{
	privatestaticbooleanisASC(Stringgroup)
	{
		if(group.isEmpty())
		{
			returnfalse;
		}
		elseif(group.length()==1)
		{
			returntrue;
		}
		else
		{
			inta=Integer.parseInt(group.charAt(0)+"");
			intb=Integer.parseInt(group.charAt(1)+"");
			if(b-a!=1)
			{
				returnfalse;
			}
			else
			{
				returnisASC(group.substring(1));
			}
		}
	}

	publicstaticvoidmain(String[]args)
	{
		Stringinput="abcd5678bbw1357f123";
		Stringregex="\d+";
		Patternpattern=Pattern.compile(regex);
		Matchermatcher=pattern.matcher(input);
		LinkedList<String>result=newLinkedList<String>();
		while(matcher.find())
		{
			Stringgroup=matcher.group();
			if(isASC(group))
			{
				result.add(group);
			}
		}
		Collections.sort(result,newComparator<String>()
		{
			@Override
			publicintcompare(Stringo1,Stringo2)
			{
				if(o1.length()>o2.length())
				{
					return-1;
				}
				elseif(o1.length()<o2.length())
				{
					return1;
				}
				else
				{
					return0;
				}
			}
		});
		for(Stringstring:result)
		{
			if(string.length()==result.get(0).length())
			{
				System.out.println(string);
			}
		}
	}
}

Ⅹ Java中冒泡排序和选择排序有什么不同

冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。
public class Paixu {
public static void main(String[] args) {
int [] a = {2,6,4,5,1,7,3};
int i = 0;
int j = 0;
int n = 0;
for(i= 0;i<a.length-1;i++){
for(j=0;j<a.length-i-1;j++){
if(a[j]>a[j+1]){
n = a[j];
a[j] = a[j+1];
a[j+1] = n;
}
}
}
for ( i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
}
直接选择排序(Straight Select Sorting) 也是一种简单的排序方法，它的基本思想是：第一次从R[0]~R[n-1]中选取最小值，与R[0]交换，第二次从R{1}~R[n-1]中选取最小值，与R[1]交换，....， 第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，.....，第n-1次从R[n-2]~R[n-1]中选取最小值，与R[n-2]交换,总共通过n-1次,得到一个按排序码从小到大排列的有序序列.
public class Paixu {
public static void main(String[] args) {
int [] a = {2,6,4,5,1,7,3};
int i = 0;
int j = 0;
int n = 0;
for(i= 0;i<a.length;i++){
for(j=i+1;j<a.length;j++){
if(a[i]>a[j]){
n = a[i];
a[j] = a[i];
a[i] = n;
}
}
}
for ( i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
}