最近在準(zhǔn)備一些暑期實習(xí)的筆試和面試，在?？途W(wǎng)上面做了一些題，現(xiàn)在整理出來供大家參考，希望和大家共同學(xué)習(xí)！題目不難，但是要做出來需要考慮時間復(fù)雜度、空間復(fù)雜的等等，同時還需要一些編程思想；

題目來源：牛客網(wǎng) ＊本文所有題目的實現(xiàn)均為java代碼

題目一：二維數(shù)組中的查找

描述：
在一個二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)，輸入這樣的一個二維數(shù)組和一個整數(shù)，判斷數(shù)組中是否含有該整數(shù)。
解題思路： 代碼
將target與二維數(shù)組array第一行最后一個數(shù)做比較,如果target大于該行數(shù),則不考慮第一行,相反不考慮最后一列,相等返回true；

題目二: 替換空格

描述:
請實現(xiàn)一個函數(shù)，將一個字符串中的空格替換成“%20”。例如，當(dāng)字符串為We Are Happy.則經(jīng)過替換之后的字符串為We%20Are%20Happy。
解題思路: 代碼

• 解法一: 遍歷
• 解法二: 直接使用replaceAll函數(shù)

題目三: 從尾到頭打印鏈表

描述:
輸入一個鏈表，從尾到頭打印鏈表每個節(jié)點的值。
解題思路: 代碼

• 解法一: 使用棧的方法解決;
• 解法二: 使用遞歸的方法,但是實質(zhì)還是棧;

題目四: 重建二叉樹

描述
輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回;
解題思路: 代碼

• 取前序遍歷第一個數(shù)字,該數(shù)字是跟節(jié)點;
• 在中序遍歷中找到跟節(jié)點,則該跟節(jié)點左邊是左子數(shù),右邊為右子數(shù);
• 以此遍歷,進行遞歸;

＊注：如果這里兩個序列有重復(fù)數(shù)字又該怎么實現(xiàn)？

題目五: 用棧實現(xiàn)隊列

描述:
用兩個棧來實現(xiàn)一個隊列，完成隊列的Push和Pop操作。 隊列中的元素為int類型。
解題思路: 代碼

• 將所有數(shù)先存入第一個棧中;
• 第一個棧出棧,按照出棧順序存入第二個棧中;
• 再從第二個棧中出棧,即得到隊列;

題目六: 旋轉(zhuǎn)數(shù)組的最小數(shù)字

描述:
把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。輸入一個非遞減序列的一個旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉(zhuǎn)，該數(shù)組的最小值為1;
解題思路: 代碼
＊這里如果不旋轉(zhuǎn)數(shù)組直接使用快排找最小數(shù)字，依然可以編譯通過；

題目七: 斐波那契數(shù)列

描述:
大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個整數(shù)n，請你輸出斐波那契數(shù)列的第n項;
解題思路:代碼

• 這里實現(xiàn)的斐波那契數(shù)列不使用遞歸的算法,遞歸算法重復(fù)計算的次數(shù)很多,當(dāng)輸入n值很大時會出現(xiàn)stackOverflow報錯;
• 所以這里采用的是一個簡單的動態(tài)規(guī)劃(數(shù)組遍歷)

題目八: 跳臺階/ 變態(tài)跳臺階

描述:
1, 一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
2, 如果青蛙一次可以跳上1級臺階, 2級臺階........ n級臺階. 求該青蛙跳上一個n級臺階總共有多少中跳法.
解題思路: 代碼
1, 遞歸,斐波那契數(shù)列
2, 遞歸思路:

• 因為n級臺階，第一步有n種跳法：跳1級、跳2級、到跳n級 * 跳1級，剩下n-1級，則剩下跳法是f(n-1)
• 跳2級，剩下n-2級，則剩下跳法是f(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)=2*f(n-1)

題目八: 矩形覆蓋

描述:
我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形。請問用n個2*1的小矩形無重疊地覆蓋一個2*n的大矩形，總共有多少種方法？
解題思路:代碼
通過分析,這里依舊時斐波那契數(shù)列,不做贅述;

題目九: 二進制中1的個數(shù)

描述: 輸入一個整數(shù)，輸出該數(shù)二進制表示中1的個數(shù)。其中負(fù)數(shù)用補碼表示。
解題思路: 代碼

• 解法一: 這是一個比較討巧的做法,將二進制轉(zhuǎn)換為String,同時將0全部用替換為"",然后返回String長度;
• 解法二: 將n與(n-1)相與,會將n最右邊的1去掉;
  舉例: n=10 1010&1001=1000 --> 1000&0111=0000; 兩次,即10的二進制數(shù)中有兩個1;

題目十: 數(shù)值的整數(shù)次方

描述:
給定一個double類型的浮點數(shù)base和int類型的整數(shù)exponent。求base的exponent次方。
解題思路: 代碼
先判斷指數(shù)的正負(fù)性,然后直接數(shù)學(xué)思路進行數(shù)相乘;
當(dāng)然也可以直接使用Math.power(base,exponent);

劍指Offer筆試題（2）
以上代碼全部托管在 Github