作者信息

长期闲置

长风破浪会有时,直挂云帆济沧海。

最近文章
ajax请求时post和get的区别是什么808
ajax默认是异步请求吗295
cors和ajax的区别是什么572
视频教程分类
推荐视频教程
  • php程序员小白到大牛三个月集训php程序员小白到大牛三个月集训
  • Laravel 9 学习正当时—保姆级教程,想学不会都难!Laravel 9 学习正当时—保姆级教程,想学不会都难!
  • 千万级数据并发解决方案(理论+实战)千万级数据并发解决方案(理论+实战)
  • Laravel基础与实战(模块化)Laravel基础与实战(模块化)
  • 首页 >后端开发 >php教程 > 正文

    PHP面试之常见基础算法(附代码示例)

    转载2022-05-31 10:10:452662 关注公众号:每天精选资源文章推送
    本篇文章给大家带来了关于PHP的相关知识,其中主要介绍了关于常见基础算法的相关内容,包括了斐波那契数递归法、扫描文件目录、二分查找等问题,下面根据实际代码一起来看一下,希望对大家有帮助。

    推荐学习:《PHP视频教程

    前言

    PHP 是世界上最好的语言,一度认为算法对于 PHPer 是多余的存在,而往往面试来讲也有略微的考察,相信大家在大多数面试情况下都会被要求写冒泡排序,然而也有部分 PHPer 连冒泡排序都写半天(比如我)

    一般面试以下几种算法足以应对!!!如有错误请评论修订,谢谢!

    已完成

    • 斐波那契数列

    • 扫描文件夹

    • 二分查找

    • 冒泡排序

    • 快速排序

    • LeetCode 第一题

    TODO

    • 堆排序

    • 选择排序

    • 链表翻转

    • 动态规划

    <?php
    class Algorithmic {
        /***
         * 斐波那契数递归法,f(n) = f(n-1) + f(n-2) 递归层级太多,调用栈爆满,100层
         */
        function fib($n) {
            if ($n < 2) {
                return 1;
            } else {
                return $this->fib($n - 1) + $this->fib($n - 2);
            }
        }
        /***
         * 使用数组存储每一个fib(n)的数值,空间复杂度增加
         * @param $dir
         * @return array
         */
        function fib2($n) {
            if ($n < 2) {
                return 1;
            } else {
                $arr = [1, 1];
                for ($i = 2; $i <= $n; $i++) {
                    $arr[$i] = $arr[$i - 1] + $arr[$i - 2];
                }
            }
            return $arr[$n];
        }
        /***
         * 使用两个临时变量存储前两个值fib(n)的数值,空间复杂度增加比数组降低
         * @param $dir
         * @return array
         */
        function fib3($n) {
            if ($n < 2) {
                return 1;
            } else {
                $last = 1;  //等式第二项
                $lastLast = 1;  //等式第一项
                for ($i = 2; $i <= $n; $i++) {
                    $current = $last + $lastLast;
                    $lastLast = $last;
                    $last = $current;
                }
                return $current;
            }
        }
        /***
         * 扫描文件目录
         * @param $dir
         * @return array
         */
        function scanFile($dir) {
            $fileList = [];
            if (is_dir($dir)) {
                $dh = opendir($dir);
                while ($file = readdir($dh)) {
                    if ($file == '.' || $file == '..') continue;  //linux下一切皆文件
                    $newDir = $dir . '/' . $file;
                    if (is_dir($newDir)) {
                        $fileList[][$file] = $this->scanFile($newDir);
                    } else {
                        $fileList[] = $file;
                    }
                }
                closedir($dh);
            }
            return $fileList;
        }
        /***
         * 二分查找
         */
        function binarySort($arr, $target) {
            if (!is_array($arr) || count($arr) < 2) {
                return $arr;
            }
            $len = count($arr);
            $start = 0;
            $end = $len - 1;
            while ($start <= $end) {
                $middle = floor(($start + $end) / 2) ;
                if ($arr[$middle] == $target) {
                    return $middle;
                } elseif ($arr[$middle] < $target) {
                    $start = $middle + 1;
                } else {
                    $end = $middle - 1;
                }
            }
            return false;
        }
        /***
         * 冒泡排序
         */
        function bubbleSort($arr) {
            for ($i = count($arr) - 1; $i > 0; $i--) {
                for ($j = 0; $j < $i; $j++) {
                    if ($arr[$j+1] < $arr[$j]) {
                        $temp = $arr[$j];
                        $arr[$j] = $arr[$j+1];
                        $arr[$j+1] = $temp;
                    }
                }
            }
            return $arr;
        }
        /***
         * 快排序
         */
        function quickSort($arr) {
            if (!is_array($arr) || count($arr) < 2) {
                return $arr;
            }
            $base = $arr[0];
            $left = [];
            $right = [];
            for ($i = 1; $i <= count($arr) - 1; $i++) {
                if ($arr[$i] < $base) {
                    $left[] = $arr[$i];
                } else {
                    $right[] = $arr[$i];
                }
            }
            return array_merge(array_merge($this->quickSort($left),[$base]), $this->quickSort($right));
        }
        /***
         * 两数之和, LeetCode第一题
         * @param $arr
         */
        function twoSum($arr, $sum = 8){
            $tempArr = [];
            foreach ($arr as $k => $v) {
                if (isset($tempArr[$v])) {
                    return [$k, $tempArr[$v]];
                }
                $tempArr[$sum-$v] = $k;
            }
            return [];
        }
    }
    $algorithmic = new Algorithmic();
    //var_dump($algorithmic->scanFile("./"));
    //var_dump($algorithmic->twoSum([4,5,3,4,5,67,787]));
    //var_dump($algorithmic->fib3(4));  // 1 1 2 3 5
    //var_dump($algorithmic->binarySort([1,3, 4, 5,7,9], 3));  //
    var_dump($algorithmic->quickSort([14,5,13,114,4,3,167,87,14]));

    推荐学习:《PHP视频教程

    以上就是PHP面试之常见基础算法(附代码示例)的详细内容,更多请关注php中文网其它相关文章!

    20期PHP线上班

    声明:本文转载于:learnku,如有侵犯,请联系admin@php.cn删除

  • 相关标签:php
  • 推荐:PHP从基础到实战教程视频

    相关文章

    相关视频


    专题推荐