剑指offer试题(PHP篇二)
6.旋转数组的最小数字
题目描述
<?php function 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); } } 弄了半天不是让输出翻转后的数组。。。。 */ if(count($rotateArray)){ return min($rotateArray); }else{ return 0; } }
运行时间:985ms 占用内存:5156k
感悟:
这道题告诉我一定要审题审题审题= =|,本来自己在一味的求解反转后的数组,结果不知什么时候一看,发现只是让求最小数,对于php而言太简单了。。。不过对于这道题,还是要提醒大家细心(汗)。
7.斐波那契数列
题目描述
n<=39
时间限制:1秒 空间限制:32768K
<?php function Fibonacci($n) { // write code here if($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 占用内存:2316k
感悟:
这道题,只要理解斐波那契数列,知道用递归来实现就完全ok,再说思路,首先,排除掉不成立的情况,其次,将0和1的特殊情况拿出来单独赋值,最后,就是一般情况的循环递归。
8.跳台阶
题目描述
<?php function 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 占用内存:2316k
感悟:
唯一的感受。。竟然撞题了= =,不废话,这道题按照一般的思路有些难解,但换种想法,比较倾向于找规律的解法,f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 5, 可以总结出f(n) = f(n-1) + f(n-2)的规律,但是为什么会出现这样的规律呢?假设现在6个台阶,我们可以从第5跳一步到6,这样的话有多少种方案跳到5就有多少种方案跳到6,另外我们也可以从4跳两步跳到6,跳到4有多少种方案的话,就有多少种方案跳到6,其他的不能从3跳到6什么的啦,所以最后就是f(6) = f(5) + f(4);这样子也很好理解变态跳台阶的问题了,看到这里,你就会惊喜的发现!没错,就是斐波那契数列的问题,不过是少了0那种情况。
9.变态跳台阶
题目描述
<?php function jumpFloorII($number) { // write code here if($number == 1) return 1; return pow(2,($number - 1)); }
运行时间:24ms 占用内存: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次方。
当然,还要知道php的pow(x,y)函数,返回 x 的 y 次方。
10.矩形覆盖
题目描述
<?php function rectCover($number) { // write code here if($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 占用内存:2928k