PHP 面试算法排序考察

介绍

算法也是面试必考题的,有简单到复杂的算法排序考察,这里例举常考的算法排序

猴子选大王

一群猴子排成一圈,按1,2,...,n依次编号。然后从第1只开始数,数到第m只,把它踢出圈,从它后面再开始数,再数到第m只,在把它踢出去...,如此不停的进行下去,直到最后只剩下一只猴子为止,那只猴子就叫做大王。要求编程模拟此过程,输入m、n,输出最后那个大王的编号。

function monkey($m,$n){
    $arr=range(1,$m);
    $i=0;
    while(count($arr)>1){
        if(($i+1)%$n==0){
            unset($arr[$i]);
        }else{
            $arr[]=$arr[$i];
            unset($arr[$i]);
        }
        $i++;
    }
    return $arr[$i];
}

写一个快速排序

function quickSort($arr) {
    $len = count($arr);
    if($len <= 1) {
        return $arr;
    }

    $base = $min = $max = [];

    $base_item = $arr[0];

    for($i = 0; $i < $len ; $i++) {
        if($arr[$i] < $base_item) {
            $min[] = $arr[$i];
        }elseif($arr[$i] > $base_item) {
            $max[] = $arr[$i];
        }else {
            $base[] = $arr[$i];
        }
    }

    $min = quickSort($min);
    $max = quickSort($max);
    return array_merge($min,$base,$max);
}

实现斐波那契数列

斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波那契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3,n∈N*)在现代物理、准晶体结构、化学等领域,斐波纳契数列都有直接的应用

function fib($n) {
    if($n <= 0) return 0;
    if ($n <= 2) return 1;
    return fib($n - 1) + fib($n - 2);
} 

function fib2($n) {
    if ($n <= 2) return 1;
    $arr = [0,1,1];
    for ($i = 3; $i <= $n; $i++) {
        $arr[$i] = $arr[$i - 1] + $arr[$i - 2];
    }
    return $arr[$n];
} 

二分查找

二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列


    function binSearch($arr,$search){
        $height=count($arr)-1;
        $low=0;
        while($low<=$height){
            $mid=floor(($low+$height)/2);//获取中间数
            if($arr[$mid]==$search){
                return $mid;
            }elseif($arr[$mid]<$search){//当中间值小于所查值时,则$mid左边的值都小于$search,此时要将$mid赋值给$low
                $low=$mid+1;
            }elseif($arr[$mid]>$search){//中间值大于所查值,则$mid右边的所有值都大于$search,此时要将$mid赋值给$height
                $height=$mid-1;
            }
        }
        return "查找失败";
    }

提示

评论区 (0)

没有记录
支持 markdown,图片截图粘贴拖拽都可以自动上传。
黑白课堂

黑白课堂

混元大罗金仙 站长创业者玉树凌风每天醒来0收入

查看更多

最新视频课程

Laravel 的 PhpSpreadsheet 包入门

wap2App 入门讲解,100%速成,全面为你讲解。

ace.js 打造一款属于你的 Web 编辑器,入门文档。

Laravel Permission 中文文档

解释 OAuth 2.0 认证 和使用场景说明

Laravel 之 horizon 队列管理界面系统

钻级赞助商