剑指offer试题（PHP篇一）
1.二維數(shù)組中的查找
題目描述
在一個二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)，輸入這樣的一個二維數(shù)組和一個整數(shù)，判斷數(shù)組中是否含有該整數(shù)。 時間限制：1秒 ? 空間限制：32768K <?phpfunction Find($target, $array) {// write code hereforeach($array as $k=>$v){if(in_array($target,$v)){return "true";}}return "false"; }
運行時間：281ms ??占用內(nèi)存：4252k
感悟：
這道題用PHP寫起來比較簡單，只要懂得二維數(shù)組的遍歷，以及in_array()函數(shù)的使用，不要搞錯參數(shù)位置，參數(shù)一為要查找的字符串，參數(shù)二為數(shù)組。
?
2.替換空格
題目描述
請實現(xiàn)一個函數(shù)，將一個字符串中的空格替換成“%20”。例如，當(dāng)字符串為We Are Happy.則經(jīng)過替換之后的字符串為We%20Are%20Happy。 時間限制：1秒 ? 空間限制：32768K <?php function replaceSpace($str) {// write code herereturn str_replace(" ","%20",$str); }運行時間：9ms ??占用內(nèi)存：2428k
感悟：
要熟悉str_replace()函數(shù)，參數(shù)一為要查找的值，參數(shù)二為替換的值，參數(shù)三為被搜索的字符串。
如果搜索的字符串是數(shù)組，那么它將返回數(shù)組，對數(shù)組中的每個元素進(jìn)行查找和替換。注意，在數(shù)組替換中，如果需要執(zhí)行替換的元素少于查找到的元素的數(shù)量，那么多余元素將用空字符串進(jìn)行替換。
?
3.從尾到頭打印鏈表
題目描述
輸入一個鏈表，從尾到頭打印鏈表每個節(jié)點的值。 時間限制：1秒 ? 空間限制：32768K <?php/*class ListNode{var $val;var $next = NULL;function __construct($x){$this->val = $x;} }*/ function printListFromTailToHead($head) {// write code here$list = array();while($head!=null){$list[]=$head->val;$head=$head->next;}return array_reverse($list); }運行時間：18ms ??占用內(nèi)存：2432k
感悟：
本題的思路為先將鏈表的值順序裝入一個空數(shù)組中，然后使用array_reverse()函數(shù)以相反的元素順序返回數(shù)組。
?
4.重建二叉樹
題目描述
輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回。 時間限制：1秒 ? 空間限制：32768K <?php/*class TreeNode{var $val;var $left = NULL;var $right = NULL;function __construct($val){$this->val = $val;} }*/ function reConstructBinaryTree($pre, $vin) {// write code hereif($pre && $vin){$treeRoot = new TreeNode($pre[0]);$index = array_search($pre[0],$vin);$treeRoot->left = reConstructBinaryTree(array_slice($pre,1,$index),array_slice($vin,0,$index));$treeRoot->right = reConstructBinaryTree(array_slice($pre,$index+1),array_slice($vin,$index+1));return $treeRoot;} }運行時間：35ms ??占用內(nèi)存：4204k
感悟：
本題的思路為遞歸調(diào)用reConstructBinaryTree方法來分別執(zhí)行左子樹和右子樹的遍歷查找，每次都查找出根節(jié)點并進(jìn)行保存。
題中使用到的函數(shù)：array_search()，在數(shù)組（參數(shù)二）中搜索某個鍵值（參數(shù)一），并返回對應(yīng)的鍵名，若沒有找到，則返回false。
array_slice()，在數(shù)組中根據(jù)條件取出一段值，并返回，參數(shù)一為數(shù)組，參數(shù)二為取值的起始位置（相當(dāng)于數(shù)組下標(biāo)），參數(shù)三為選取的長度（可選，若不填，則取到數(shù)組結(jié)尾）。
?
5.用兩個棧實現(xiàn)隊列
題目描述
用兩個棧來實現(xiàn)一個隊列，完成隊列的Push和Pop操作。 隊列中的元素為int類型。 時間限制：1秒 ? ?空間限制：32768K <?php $stack = array(); function mypush($node) {// write code hereglobal $stack;return $stack[]=$node; } function mypop() {global $stack;if($stack){return array_shift($stack);}// write code herereturn $stack; }運行時間：14ms ??占用內(nèi)存：3688k
感悟：
首先要清楚隊列的Push和Pop操作的含義：push(x)：將x壓入隊列的末端，pop()：彈出隊列的第一個元素。
本題要點為定義全局?jǐn)?shù)組$stack，其次為array_shift()函數(shù)：刪除數(shù)組中的第一個元素，并返回被刪除元素的值。
?
6.旋轉(zhuǎn)數(shù)組的最小數(shù)字
題目描述
把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。 輸入一個非遞減排序的數(shù)組的一個旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。 例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉(zhuǎn)，該數(shù)組的最小值為1。 NOTE：給出的所有元素都大于0，若數(shù)組大小為0，請返回0。 時間限制：3秒 ? 空間限制：32768K <?phpfunction minNumberInRotateArray($rotateArray) {// write code here/*if(count($rotateArray) == 0){return 0;}$min = min($rotateArray);foreach($rotateArray as $k=>$v){if($v == $min){$arrLeft[] = array_slice($rotateaArray,0,$k+1);$arrRight[] = array_slice($rotateArray,$k+1);}}弄了半天不是讓輸出翻轉(zhuǎn)后的數(shù)組。。。。*/if(count($rotateArray)){return min($rotateArray);}else{return 0;} }運行時間：985ms ??占用內(nèi)存：5156k
感悟：
這道題告訴我一定要審題審題審題= ?=|，本來自己在一味的求解反轉(zhuǎn)后的數(shù)組，結(jié)果不知什么時候一看，發(fā)現(xiàn)只是讓求最小數(shù)，對于php而言太簡單了。。。不過對于這道題，還是要提醒大家細(xì)心（汗）。
?
7.斐波那契數(shù)列
題目描述
大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個整數(shù)n，請你輸出斐波那契數(shù)列的第n項。n<=39
時間限制：1秒 ? 空間限制：32768K
<?phpfunction Fibonacci($n) {// write code hereif($n < 0 || $n > 39)return false;$ret = [];for($i = 0; $i <= $n; $i++){if($i == 0){$ret[$i] = 0;continue;}elseif($i == 1){$ret[$i] = 1;continue;}$ret[$i] = $ret[$i-1]+$ret[$i-2];}return $ret[$n]; }運行時間：15ms ??占用內(nèi)存：2316k
感悟：
這道題，只要理解斐波那契數(shù)列，知道用遞歸來實現(xiàn)就完全ok，再說思路，首先，排除掉不成立的情況，其次，將0和1的特殊情況拿出來單獨賦值，最后，就是一般情況的循環(huán)遞歸。
?
8.跳臺階
題目描述
一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法。 時間限制：1秒 ? 空間限制：32768K <?phpfunction jumpFloor($number) {// write code here$arr = [];for($i=1;$i<=$number;$i++){if($i==1){$arr[1]=1;continue;}if($i==2){$arr[2]=2;continue;}$arr[$i]=$arr[$i-1]+$arr[$i-2];}return $arr[$number]; }運行時間：9ms ??占用內(nèi)存：2316k
感悟：
唯一的感受。。竟然撞題了= =，不廢話，這道題按照一般的思路有些難解，但換種想法，比較傾向于找規(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)跳臺階的問題了，看到這里，你就會驚喜的發(fā)現(xiàn)！沒錯，就是斐波那契數(shù)列的問題，不過是少了0那種情況。
?
9.變態(tài)跳臺階
題目描述
一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法。 時間限制：1秒 ? 空間限制：32768K <?phpfunction jumpFloorII($number) {// write code hereif($number == 1) return 1;return pow(2,($number - 1)); }運行時間：24ms ??占用內(nèi)存：2936k
感悟：
因為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)
所以，f(n)=2的n-1次方。
當(dāng)然，還要知道php的pow(x,y)函數(shù)，返回 x 的 y 次方。
?
10.矩形覆蓋
題目描述
我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形。請問用n個2*1的小矩形無重疊地覆蓋一個2*n的大矩形，總共有多少種方法？ 時間限制：1秒 ? 空間限制：32768K <?phpfunction rectCover($number) {// write code hereif($number==0){return 0;}$arr = [];for($i=1;$i<=$number;$i++){if($i==1){$arr[1]=1;continue;}if($i==2){$arr[2]=2;continue;}$arr[$i]=$arr[$i-1]+$arr[$i-2];}return $arr[$number]; }運行時間：29ms ??占用內(nèi)存：2928k
感悟： 走過的彎路：開始只是簡單地將 n 分成奇、偶討論，并將 2*2 作為基本單元。測試后通不過，代碼就不貼出來獻(xiàn)丑了。 思路分析：痛定思痛，還是不能夠貪小便宜。用歸納法歸納如下， （1）當(dāng) n < 1時，顯然不需要用2*1塊覆蓋，按照題目提示應(yīng)該返回?0。 （2）當(dāng)?n =?1時，只存在一種情況。 ? （3）當(dāng) n = 2時，存在兩種情況。 ? （4）當(dāng) n = 3時，明顯感覺到如果沒有章法，思維難度比之前提升挺多的。 ? ... 嘗試歸納，本質(zhì)上?n?覆蓋方法種類都是對 n - 1 時的擴(kuò)展。 可以明確，n?時必定有 n-1時原來方式與2*1的方塊結(jié)合。也就是說, f(n) = f(n-1) + ?(暫時無法判斷)。 （4）如果我們現(xiàn)在歸納 n = 4，應(yīng)該是什么形式？ 4.1）保持原來n = 3時內(nèi)容，并擴(kuò)展一個 2*1 方塊，形式分別為?“|?|?|?|”、“= |?|”、“| =?|” 4.2）新增加的2*1 方塊與臨近的2*1方塊組成 2*2結(jié)構(gòu)，然后可以變形成?“=”。于是?n = 4在原來n = 3基礎(chǔ)上增加了"|?| ="、“= =”。 再自己看看這多出來的兩種形式，是不是只比n = 2多了“=”。其實這就是關(guān)鍵點所在...因為，只要2*1或1*2有相同的兩個時，就會組成2*2形式，于是就又可以變形了。 所以，自然而然可以得出規(guī)律： f(n) = f(n-1) + f(n-2)， (n > 2)。 然后這個時候，你就會驚喜的發(fā)現(xiàn)，又回到斐波那契數(shù)列了。。。思路不再細(xì)說，有需要的朋友可以看7題和8題。?
注：以上均為個人理解，如有錯誤，請?zhí)岢?#xff0c;必改正。
posted on 2018-02-14 19:17 zlnevsto 閱讀(...) 評論(...) 編輯 收藏轉(zhuǎn)載于:https://www.cnblogs.com/zlnevsto/p/8448732.html
總結(jié)
以上是生活随笔為你收集整理的剑指offer试题（PHP篇一）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 2.12日递推专题第一题
- 下一篇： owaspbwa tickets