一 斐波那契數(shù)列
題目描述：
大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個整數(shù)n馒疹，請你輸出斐波那契數(shù)列的第n項。
n<=39
問題分析：
可以肯定的是這一題通過遞歸的方式是肯定能做出來繁成，但是這樣會有一個很大的問題焚辅，那就是遞歸大量的重復(fù)計算會導(dǎo)致內(nèi)存溢出。另外可以使用迭代法誓军，用fn1和fn2保存計算過程中的結(jié)果袱讹，并復(fù)用起來。下面我會把兩個方法示例代碼都給出來并給出兩個方法的運行時間對比昵时。
示例代碼：
采用迭代法：
int Fibonacci(int number) {
if (number <= 0) {
return 0;
}
if (number == 1 || number == 2) {
return 1;
}
int first = 1, second = 1, third = 0;
for (int i = 3; i <= number; i++) {
third = first + second;
first = second;
second = third;
}
return third;
}
采用遞歸：
public int Fibonacci(int n) {
if (n <= 0) {
return 0;
}
if (n == 1||n==2) {
return 1;
}
return Fibonacci(n - 2) + Fibonacci(n - 1);
}
運行時間對比：
假設(shè)n為40我們分別使用迭代法和遞歸法計算捷雕，計算結(jié)果如下：
-
迭代法
迭代法 -
遞歸法
遞歸法
二 跳臺階問題
題目描述：
一只青蛙一次可以跳上1級臺階，也可以跳上2級壹甥。求該青蛙跳上一個n級的臺階總共有多少種跳法救巷。
問題分析：
正常分析法：
a.如果兩種跳法，1階或者2階盹廷，那么假定第一次跳的是一階征绸，那么剩下的是n-1個臺階，跳法是f(n-1);
b.假定第一次跳的是2階俄占，那么剩下的是n-2個臺階管怠，跳法是f(n-2)
c.由a，b假設(shè)可以得出總跳法為: f(n) = f(n-1) + f(n-2)
d.然后通過實際的情況可以得出：只有一階的時候 f(1) = 1 ,只有兩階的時候可以有 f(2) = 2
找規(guī)律分析法：
f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 5缸榄， 可以總結(jié)出f(n) = f(n-1) + f(n-2)的規(guī)律渤弛。
但是為什么會出現(xiàn)這樣的規(guī)律呢？假設(shè)現(xiàn)在6個臺階甚带，我們可以從第5跳一步到6她肯，這樣的話有多少種方案跳到5就有多少種方案跳到6佳头，另外我們也可以從4跳兩步跳到6，跳到4有多少種方案的話晴氨，就有多少種方案跳到6康嘉，其他的不能從3跳到6什么的啦，所以最后就是f(6) = f(5) + f(4)籽前；這樣子也很好理解變態(tài)跳臺階的問題了亭珍。
所以這道題其實就是斐波那契數(shù)列的問題。
代碼只需要在上一題的代碼稍做修改即可枝哄。和上一題唯一不同的就是這一題的初始元素變?yōu)?1 2 3 5 8.....而上一題為1 1 2 3 5 .......肄梨。另外這一題也可以用遞歸做，但是遞歸效率太低挠锥，所以我這里只給出了迭代方式的代碼众羡。
示例代碼：
int jumpFloor(int number) {
if (number <= 0) {
return 0;
}
if (number == 1) {
return 1;
}
if (number == 2) {
return 2;
}
int first = 1, second = 2, third = 0;
for (int i = 3; i <= number; i++) {
third = first + second;
first = second;
second = third;
}
return third;
}
三 變態(tài)跳臺階問題
題目描述：
一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級蓖租。求該青蛙跳上一個n級的臺階總共有多少種跳法粱侣。
問題分析：
假設(shè)n>=2，第一步有n種跳法：跳1級菜秦、跳2級甜害、到跳n級
跳1級，剩下n-1級球昨，則剩下跳法是f(n-1)
跳2級尔店，剩下n-2級，則剩下跳法是f(n-2)
......
跳n-1級主慰，剩下1級嚣州，則剩下跳法是f(1)
跳n級，剩下0級共螺，則剩下跳法是f(0)
所以在n>=2的情況下：
f(n)=f(n-1)+f(n-2)+...+f(1)
因為f(n-1)=f(n-2)+f(n-3)+...+f(1)
所以f(n)=2f(n-1) 又f(1)=1,所以可得f(n)=2^(number-1)*
示例代碼：
int JumpFloorII(int number) {
return 1 << --number;//2^(number-1)用位移操作進(jìn)行该肴，更快
}
補(bǔ)充：
java中有三種移位運算符：
- “<<” : 左移運算符，等同于乘2的n次方
- “>>”: 右移運算符藐不，等同于除2的n次方
- “>>>” 無符號右移運算符匀哄，不管移動前最高位是0還是1，右移后左側(cè)產(chǎn)生的空位部分都以0來填充雏蛮。與>>類似涎嚼。
例：
int a = 16;
int b = a << 2;//左移2，等同于16 * 2的2次方挑秉，也就是16 * 4
int c = a >> 2;//右移2法梯，等同于16 / 2的2次方，也就是16 / 4
四 二維數(shù)組查找
題目描述：
在一個二維數(shù)組中，每一行都按照從左到右遞增的順序排序立哑，每一列都按照從上到下遞增的順序排序夜惭。請完成一個函數(shù)，輸入這樣的一個二維數(shù)組和一個整數(shù)铛绰，判斷數(shù)組中是否含有該整數(shù)诈茧。
問題解析：
這一道題還是比較簡單的，我們需要考慮的是如何做捂掰，效率最快若皱。這里有一種很好理解的思路：
矩陣是有序的，從左下角來看尘颓，向上數(shù)字遞減，向右數(shù)字遞增晦譬，
因此從左下角開始查找疤苹，當(dāng)要查找數(shù)字比左下角數(shù)字大時。右移
要查找數(shù)字比左下角數(shù)字小時敛腌，上移卧土。這樣找的速度最快。
示例代碼：
public boolean Find(int target, int [][] array) {
//基本思路從左下角開始找像樊，這樣速度最快
int row = array.length-1;//行
int column = 0;//列
//當(dāng)行數(shù)大于0尤莺，當(dāng)前列數(shù)小于總列數(shù)時循環(huán)條件成立
while((row >= 0)&& (column< array[0].length)){
if(array[row][column] > target){
row--;
}else if(array[row][column] < target){
column++;
}else{
return true;
}
}
return false;
}
五 替換空格
題目描述：
請實現(xiàn)一個函數(shù)，將一個字符串中的空格替換成“%20”生棍。例如颤霎，當(dāng)字符串為We Are Happy.則經(jīng)過替換之后的字符串為We%20Are%20Happy。
問題分析：
這道題不難涂滴，我們可以通過循環(huán)判斷字符串的字符是否為空格友酱，是的話就利用append()方法添加追加“%20”，否則還是追加原字符柔纵。
或者最簡單的方法就是利用： replaceAll(String regex,String replacement)方法了缔杉，一行代碼就可以解決。
示例代碼：
常規(guī)做法：
public String replaceSpace(StringBuffer str) {
StringBuffer out=new StringBuffer();
for (int i = 0; i < str.toString().length(); i++) {
char b=str.charAt(i);
if(String.valueOf(b).equals(" ")){
out.append("%20");
}else{
out.append(b);
}
}
return out.toString();
}
一行代碼解決：
public String replaceSpace(StringBuffer str) {
//return str.toString().replaceAll(" ", "%20");
//public String replaceAll(String regex,String replacement)
//用給定的替換替換與給定的regular expression匹配的此字符串的每個子字符串搁料。
//\ 轉(zhuǎn)義字符. 如果你要使用 "\" 本身, 則應(yīng)該使用 "\\". String類型中的空格用“\s”表示或详，所以我這里猜測"\\s"就是代表空格的意思
return str.toString().replaceAll("\\s", "%20");
}
六 數(shù)值的整數(shù)次方
題目描述：
給定一個double類型的浮點數(shù)base和int類型的整數(shù)exponent。求base的exponent次方郭计。
問題解析：
這道題算是比較麻煩和難一點的一個了霸琴。我這里采用的是二分冪思想，當(dāng)然也可以采用快速冪拣宏。
更具劍指offer書中細(xì)節(jié)沈贝，該題的解題思路如下：
1.當(dāng)?shù)讛?shù)為0且指數(shù)<0時，會出現(xiàn)對0求倒數(shù)的情況勋乾，需進(jìn)行錯誤處理宋下，設(shè)置一個全局變量嗡善；
2.判斷底數(shù)是否等于0，由于base為double型学歧，所以不能直接用==判斷
3.優(yōu)化求冪函數(shù)（二分冪）罩引。
當(dāng)n為偶數(shù)，a^n =（an/2）*（an/2）枝笨；
當(dāng)n為奇數(shù)袁铐，a^n = a^[(n-1)/2] * a^[(n-1)/2] * a。時間復(fù)雜度O(logn)
時間復(fù)雜度：O(logn)
示例代碼：
public class Solution {
boolean invalidInput=false;
public double Power(double base, int exponent) {
//如果底數(shù)等于0并且指數(shù)小于0
//由于base為double型横浑，不能直接用==判斷
if(equal(base,0.0)&&exponent<0){
invalidInput=true;
return 0.0;
}
int absexponent=exponent;
//如果指數(shù)小于0剔桨，將指數(shù)轉(zhuǎn)正
if(exponent<0)
absexponent=-exponent;
//getPower方法求出base的exponent次方。
double res=getPower(base,absexponent);
//如果指數(shù)小于0徙融，所得結(jié)果為上面求的結(jié)果的倒數(shù)
if(exponent<0)
res=1.0/res;
return res;
}
//比較兩個double型變量是否相等的方法
boolean equal(double num1,double num2){
if(num1-num2>-0.000001&&num1-num2<0.000001)
return true;
else
return false;
}
//求出b的e次方的方法
double getPower(double b,int e){
//如果指數(shù)為0洒缀，返回1
if(e==0)
return 1.0;
//如果指數(shù)為1，返回b
if(e==1)
return b;
//e>>1相等于e/2欺冀，這里就是求a^n =（a^n/2）*（a^n/2）
double result=getPower(b,e>>1);
result*=result;
//如果指數(shù)n為奇數(shù)树绩，則要再乘一次底數(shù)base
if((e&1)==1)
result*=b;
return result;
}
}
當(dāng)然這一題也可以采用笨方法：累乘。不過這種方法的時間復(fù)雜度為O（n）隐轩，這樣沒有前一種方法效率高饺饭。
// 使用累乘
public double powerAnother(double base, int exponent) {
double result = 1.0;
for (int i = 0; i < Math.abs(exponent); i++) {
result *= base;
}
if (exponent >= 0)
return result;
else
return 1 / result;
}
七 調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面
題目描述：
輸入一個整數(shù)數(shù)組，實現(xiàn)一個函數(shù)來調(diào)整該數(shù)組中數(shù)字的順序职车，使得所有的奇數(shù)位于數(shù)組的前半部分瘫俊，所有的偶數(shù)位于位于數(shù)組的后半部分，并保證奇數(shù)和奇數(shù)悴灵，偶數(shù)和偶數(shù)之間的相對位置不變军援。
問題解析：
這道題有挺多種解法的，給大家介紹一種我覺得挺好理解的方法：
我們首先統(tǒng)計奇數(shù)的個數(shù)假設(shè)為n,然后新建一個等長數(shù)組称勋，然后通過循環(huán)判斷原數(shù)組中的元素為偶數(shù)還是奇數(shù)胸哥。如果是則從數(shù)組下標(biāo)0的元素開始，把該奇數(shù)添加到新數(shù)組赡鲜；如果是偶數(shù)則從數(shù)組下標(biāo)為n的元素開始把該偶數(shù)添加到新數(shù)組中空厌。
示例代碼：
時間復(fù)雜度為O（n），空間復(fù)雜度為O（n）的算法
public class Solution {
public void reOrderArray(int [] array) {
//如果數(shù)組長度等于0或者等于1银酬，什么都不做直接返回
if(array.length==0||array.length==1)
return;
//oddCount：保存奇數(shù)個數(shù)
//oddBegin：奇數(shù)從數(shù)組頭部開始添加
int oddCount=0,oddBegin=0;
//新建一個數(shù)組
int[] newArray=new int[array.length];
//計算出（數(shù)組中的奇數(shù)個數(shù)）開始添加元素
for(int i=0;i<array.length;i++){
if((array[i]&1)==1) oddCount++;
}
for(int i=0;i<array.length;i++){
//如果數(shù)為基數(shù)新數(shù)組從頭開始添加元素
//如果為偶數(shù)就從oddCount（數(shù)組中的奇數(shù)個數(shù)）開始添加元素
if((array[i]&1)==1)
newArray[oddBegin++]=array[i];
else newArray[oddCount++]=array[i];
}
for(int i=0;i<array.length;i++){
array[i]=newArray[i];
}
}
}
八 鏈表中倒數(shù)第k個節(jié)點
題目描述：
輸入一個鏈表嘲更，輸出該鏈表中倒數(shù)第k個結(jié)點
問題分析：
一句話概括：
兩個指針一個指針p1先開始跑，指針p1跑到k-1個節(jié)點后揩瞪，另一個節(jié)點p2開始跑赋朦，當(dāng)p1跑到最后時，p2所指的指針就是倒數(shù)第k個節(jié)點。
思想的簡單理解：
前提假設(shè)：鏈表的結(jié)點個數(shù)(長度)為n宠哄。
規(guī)律一：要找到倒數(shù)第k個結(jié)點壹将，需要向前走多少步呢？比如倒數(shù)第一個結(jié)點毛嫉，需要走n步诽俯，那倒數(shù)第二個結(jié)點呢？很明顯是向前走了n-1步承粤，所以可以找到規(guī)律是找到倒數(shù)第k個結(jié)點暴区，需要向前走n-k+1步。
算法開始：
- 設(shè)兩個都指向head的指針p1和p2辛臊，當(dāng)p1走了k-1步的時候仙粱，停下來。p2之前一直不動彻舰。
- p1的下一步是走第k步缰盏，這個時候，p2開始一起動了淹遵。至于為什么p2這個時候動呢？看下面的分析负溪。
- 當(dāng)p1走到鏈表的尾部時透揣，即p1走了n步。由于我們知道p2是在p1走了k-1步才開始動的川抡，也就是說p1和p2永遠(yuǎn)差k-1步辐真。所以當(dāng)p1走了n步時，p2走的應(yīng)該是在n-(k-1)步崖堤。即p2走了n-k+1步侍咱，此時巧妙的是p2正好指向的是規(guī)律一的倒數(shù)第k個結(jié)點處。
這樣是不是很好理解了呢密幔？
考察內(nèi)容：
鏈表+代碼的魯棒性
示例代碼：
/*
//鏈表類
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
//時間復(fù)雜度O(n),一次遍歷即可
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
ListNode pre=null,p=null;
//兩個指針都指向頭結(jié)點
p=head;
pre=head;
//記錄k值
int a=k;
//記錄節(jié)點的個數(shù)
int count=0;
//p指針先跑楔脯，并且記錄節(jié)點數(shù)，當(dāng)p指針跑了k-1個節(jié)點后胯甩，pre指針開始跑昧廷，
//當(dāng)p指針跑到最后時，pre所指指針就是倒數(shù)第k個節(jié)點
while(p!=null){
p=p.next;
count++;
if(k<1){
pre=pre.next;
}
k--;
}
//如果節(jié)點個數(shù)小于所求的倒數(shù)第k個節(jié)點偎箫，則返回空
if(count<a) return null;
return pre;
}
}
九 反轉(zhuǎn)鏈表
題目描述：
輸入一個鏈表木柬，反轉(zhuǎn)鏈表后，輸出鏈表的所有元素淹办。
問題分析：
鏈表的很常規(guī)的一道題眉枕，這一道題思路不算難，但自己實現(xiàn)起來真的可能會感覺無從下手，我是參考了別人的代碼速挑。
思路就是我們根據(jù)鏈表的特點谤牡，前一個節(jié)點指向下一個節(jié)點的特點，把后面的節(jié)點移到前面來梗摇。
就比如下圖：我們把1節(jié)點和2節(jié)點互換位置拓哟，然后再將3節(jié)點指向2節(jié)點，4節(jié)點指向3節(jié)點伶授，這樣以來下面的鏈表就被反轉(zhuǎn)了断序。
考察內(nèi)容：
鏈表+代碼的魯棒性
示例代碼：
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode next = null;
ListNode pre = null;
while (head != null) {
//保存要反轉(zhuǎn)到頭來的那個節(jié)點
next = head.next;
//要反轉(zhuǎn)的那個節(jié)點指向已經(jīng)反轉(zhuǎn)的上一個節(jié)點
head.next = pre;
//上一個已經(jīng)反轉(zhuǎn)到頭部的節(jié)點
pre = head;
//一直向鏈表尾走
head = next;
}
return pre;
}
}
十 合并兩個排序的鏈表
題目描述：
輸入兩個單調(diào)遞增的鏈表，輸出兩個鏈表合成后的鏈表糜烹，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則违诗。
問題分析：
我們可以這樣分析:
- 假設(shè)我們有兩個鏈表 A,B；
- A的頭節(jié)點A1的值與B的頭結(jié)點B1的值比較疮蹦，假設(shè)A1小诸迟，則A1為頭節(jié)點；
- A2再和B1比較愕乎，假設(shè)B1小,則阵苇，A1指向B1；
- A2再和B2比較感论。绅项。。比肄。快耿。。芳绩。
就這樣循環(huán)往復(fù)就行了掀亥，應(yīng)該還算好理解。
考察內(nèi)容：
鏈表+代碼的魯棒性
示例代碼：
非遞歸版本：
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
//list1為空妥色，直接返回list2
if(list1 == null){
return list2;
}
//list2為空搪花，直接返回list1
if(list2 == null){
return list1;
}
ListNode mergeHead = null;
ListNode current = null;
//當(dāng)list1和list2不為空時
while(list1!=null && list2!=null){
//取較小值作頭結(jié)點
if(list1.val <= list2.val){
if(mergeHead == null){
mergeHead = current = list1;
}else{
current.next = list1;
//current節(jié)點保存list1節(jié)點的值因為下一次還要用
current = list1;
}
//list1指向下一個節(jié)點
list1 = list1.next;
}else{
if(mergeHead == null){
mergeHead = current = list2;
}else{
current.next = list2;
//current節(jié)點保存list2節(jié)點的值因為下一次還要用
current = list2;
}
//list2指向下一個節(jié)點
list2 = list2.next;
}
}
if(list1 == null){
current.next = list2;
}else{
current.next = list1;
}
return mergeHead;
}
}
遞歸版本：
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1 == null){
return list2;
}
if(list2 == null){
return list1;
}
if(list1.val <= list2.val){
list1.next = Merge(list1.next, list2);
return list1;
}else{
list2.next = Merge(list1, list2.next);
return list2;
}
}
十一 用兩個棧實現(xiàn)隊列
題目描述：
用兩個棧來實現(xiàn)一個隊列，完成隊列的Push和Pop操作嘹害。 隊列中的元素為int類型鳍侣。
問題分析：
先來回顧一下棧和隊列的基本特點：
棧：后進(jìn)先出（LIFO）
隊列： 先進(jìn)先出
很明顯我們需要根據(jù)JDK給我們提供的棧的一些基本方法來實現(xiàn)。先來看一下Stack類的一些基本方法：
既然題目給了我們兩個棧吼拥，我們可以這樣考慮當(dāng)push的時候?qū)⒃豴ush進(jìn)stack1倚聚，pop的時候我們先把stack1的元素pop到stack2，然后再對stack2執(zhí)行pop操作凿可，這樣就可以保證是先進(jìn)先出的惑折。（負(fù)[pop]負(fù)[pop]得正[先進(jìn)先出]）
考察內(nèi)容：
隊列+棧
示例代碼：
//左程云的《程序員代碼面試指南》的答案
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
//當(dāng)執(zhí)行push操作時授账，將元素添加到stack1
public void push(int node) {
stack1.push(node);
}
public int pop() {
//如果兩個隊列都為空則拋出異常,說明用戶沒有push進(jìn)任何元素
if(stack1.empty()&&stack2.empty()){
throw new RuntimeException("Queue is empty!");
}
//如果stack2不為空直接對stack2執(zhí)行pop操作，
if(stack2.empty()){
while(!stack1.empty()){
//將stack1的元素按后進(jìn)先出push進(jìn)stack2里面
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}
十二 棧的壓入,彈出序列
題目描述：
輸入兩個整數(shù)序列惨驶，第一個序列表示棧的壓入順序白热，請判斷第二個序列是否為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等粗卜。例如序列1,2,3,4,5是某棧的壓入順序屋确，序列4，5,3,2,1是該壓棧序列對應(yīng)的一個彈出序列续扔，但4,3,5,1,2就不可能是該壓棧序列的彈出序列攻臀。（注意：這兩個序列的長度是相等的）
題目分析：
這道題想了半天沒有思路，參考了Alias的答案纱昧，他的思路寫的也很詳細(xì)應(yīng)該很容易看懂刨啸。
作者：Alias
https://www.nowcoder.com/questionTerminal/d77d11405cc7470d82554cb392585106
來源：牛客網(wǎng)
【思路】借用一個輔助的棧识脆，遍歷壓棧順序设联，先講第一個放入棧中，這里是1灼捂，然后判斷棧頂元素是不是出棧順序的第一個元素离例，這里是4，很顯然1≠4悉稠，所以我們繼續(xù)壓棧宫蛆，直到相等以后開始出棧，出棧一個元素偎球，則將出棧順序向后移動一位，直到不相等辑甜，這樣循環(huán)等壓棧順序遍歷完成衰絮，如果輔助棧還不為空，說明彈出序列不是該棧的彈出順序磷醋。
舉例：
入棧1,2,3,4,5
出棧4,5,3,2,1
首先1入輔助棧猫牡，此時棧頂1≠4，繼續(xù)入棧2
此時棧頂2≠4邓线，繼續(xù)入棧3
此時棧頂3≠4淌友，繼續(xù)入棧4
此時棧頂4＝4，出棧4骇陈，彈出序列向后一位震庭，此時為5，,輔助棧里面是1,2,3
此時棧頂3≠5你雌，繼續(xù)入棧5
此時棧頂5=5器联，出棧5,彈出序列向后一位二汛，此時為3，,輔助棧里面是1,2,3
….
依次執(zhí)行拨拓，最后輔助棧為空肴颊。如果不為空說明彈出序列不是該棧的彈出順序。
考察內(nèi)容：
棧
示例代碼：
import java.util.ArrayList;
import java.util.Stack;
//這道題沒想出來渣磷，參考了Alias同學(xué)的答案：https://www.nowcoder.com/questionTerminal/d77d11405cc7470d82554cb392585106
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
if(pushA.length == 0 || popA.length == 0)
return false;
Stack<Integer> s = new Stack<Integer>();
//用于標(biāo)識彈出序列的位置
int popIndex = 0;
for(int i = 0; i< pushA.length;i++){
s.push(pushA[i]);
//如果棧不為空婿着，且棧頂元素等于彈出序列
while(!s.empty() &&s.peek() == popA[popIndex]){
//出棧
s.pop();
//彈出序列向后一位
popIndex++;
}
}
return s.empty();
}
}
