剑指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