最長遞增子序列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]);
}
}
}