一、棧的壓入與彈出序列：

1、題目：

輸入兩個整數序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否可能為該棧的彈出順序。?假設壓入棧的所有數字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4,5,3,2,1是該壓棧序列對應的一個彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。（注意：這兩個序列的長度是相等的）

2、解題思路：

借用一個輔助的棧，遍歷壓棧順序，先將第一個放入棧中，這里是1，然后判斷棧頂元素是不是出棧順序的第一個元素，這里是4，很顯然1≠4，所以我們繼續壓棧，直到相等以后開始出棧，出棧一個元素，則將出棧順序向后移動一位，直到不相等，這樣循環等壓棧順序遍歷完成，如果輔助棧還不為空，說明彈出序列不是該棧的彈出順序。

舉例：
入棧1,2,3,4,5
出棧4,5,3,2,1
首先1入輔助棧，此時棧頂1≠4，繼續入棧2
此時棧頂2≠4，繼續入棧3
此時棧頂3≠4，繼續入棧4
此時棧頂4＝4，出棧4，彈出序列向后一位，此時為5，,輔助棧里面是1,2,3
此時棧頂3≠5，繼續入棧5
此時棧頂5=5，出棧5,彈出序列向后一位，此時為3，,輔助棧里面是1,2,3
….
依次執行，最后輔助棧為空。如果不為空說明彈出序列不是該棧的彈出順序。

3、代碼實現：

public boolean IsPopOrder(int [] pushA,int [] popA) {if(pushA.length ==0 || popA.length == 0 ){return false;}Stack<Integer> stack= new Stack<Integer>();//用于標識彈出序列的位置Integer popIndex=0;for(int i=0;i<pushA.length;i++){stack.push(pushA[i]);//如果棧不為空，且棧頂元素等于彈出序列while(!stack.empty() && stack.peek()==popA[popIndex]){//彈出序列stack.pop();//彈出序列后向后一位popIndex++;}}return stack.empty();}

?

二、把字符串轉化為整數：

1、題目：

將一個字符串轉換成一個整數(實現Integer.valueOf(string)的功能，但是string不符合數字要求時返回0)，要求不能使用字符串轉換整數的庫函數。 數值為0或者字符串不是一個合法的數值則返回0。

2、代碼實現：

public class Test19 {public static int StrToInt(String str) {if(str.length()==0 || str.equals(""))return 0;char[] a = str.toCharArray();int fuhao=0;if(a[0]== '-')fuhao=1;int sum = 0;for(int i=fuhao;i<a.length;i++){if(a[i]=='+'){continue;}if(a[i]<48 || a[i]>57){return 0;}sum = sum * 10 + a[i]-48;}return fuhao == 0?sum:sum* -1;} }

?

三、撲克牌順子：

1、題目：

LL今天心情特別好,因為他去買了一副撲克牌,發現里面居然有2個大王,2個小王(一副牌原本是54張^_^)...他隨機從中抽出了5張牌,想測測自己的手氣,看看能不能抽到順子,如果抽到的話,他決定去買體育彩票,嘿嘿！！“紅心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是順子.....LL不高興了,他想了想,決定大\小 王可以看成任何數字,并且A看作1,J為11,Q為12,K為13。上面的5張牌就可以變成“1,2,3,4,5”(大小王分別看作2和4),“So Lucky!”。LL決定去買體育彩票啦。 現在,要求你使用這幅牌模擬上面的過程,然后告訴我們LL的運氣如何， 如果牌能組成順子就輸出true，否則就輸出false。為了方便起見,你可以認為大小王是0。

2、解題思路：

題目可以簡化為：給出一副撲克牌+兩張大小王=56張牌。抽出5張牌，判斷是否撲克牌順子：4個大小王看做數字0，大小王可以看成任意數字。

(1)最大最小的數組相差小于5；

(2)數組中不存在相同的數字 。

3、代碼實現：

public class Test20 {public boolean isContinuous(int [] numbers) {if(numbers.length!=5 ) return false;int min=14;int max=-1;for(int i=0;i<numbers.length;i++){int number=numbers[i];if(number==0) continue;if(number>13 || number<0) return false;//排除相同的牌for(int j=i+1;j<numbers.length;j++){if(number==numbers[j]) return false;}if(max<number) max=number;if(min>number) min=number;if(max-min>=5) return false;}return true;} }

?

四、孩子們的游戲（圓圈中最后剩下的數）-- 瑟夫問題：

1、題目：

有個游戲是這樣的:首先,讓小朋友們圍成一個大圈。然后,隨機指定一個數m,讓編號為0的小朋友開始報數。每次喊到m-1的那個小朋友要出列唱首歌,然后可以在禮品箱中任意的挑選禮物,并且不再回到圈中,從他的下一個小朋友開始,繼續0...m-1報數....這樣下去....直到剩下最后一個小朋友,可以不用表演,并且拿到牛客名貴典藏版禮物。請你試著想下,哪個小朋友會得到這份禮品呢？(注：小朋友的編號是從0到n-1)。

2、解題思路：

題目可以轉化為瑟夫問題，瑟夫問題是一個非常著名的趣題，即由n個人坐成一圈，按順時針由0開始給他們編號。然后由第一個人開始報數，數到m-1的人出局?，F在需要求的是最后一個出局的人的編號。
給定兩個int n和m，n代表游戲的人數。請返回最后一個出局的人的編號。保證n和m小于等于1000。

3、代碼實現：

public class Test21 {public int LastRemaining_Solution(int n, int m) {if(n==0 || m==0){return -1;}List<Integer> list = new ArrayList<Integer>();for(int i=0;i<n;i++){list.add(i);}int index=0;while(list.size()>1){index=(index+m-1)%list.size();list.remove(index);}return list.get(0);} }

?

總結

以上是生活随笔為你收集整理的《剑指offer》-- 栈的压入与弹出序列、把字符串转化为整数、扑克牌顺子、孩子们的游戏（圆圈中最后剩下的数）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。