站长家园(原代码之家)(www.adminjie.com)网站源码,微信源码,游戏源码,商业源码分享平台。
当前位置:网站首页 技术文章 网络编程 正文

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

时间:2022-05-31 [网络编程]作者:fabuyuan 浏览:7 次

本篇文章给大家带来了关于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

转载请注明来源:PHP面试之常见基础算法(附代码示例)

本文永久链接地址:https://www.adminjie.com/post/12996.html

免责声明:
本站所发布的一切资源仅限用于学习和研究目的;不得将上述内容用于商业或者非法用途,否则,一切后果请用户自负。本站信息来自网络,版权争议与本站无关。您必须在下载后的24个小时之内,从您的电脑中彻底删除上述内容。如果您喜欢该程序,请支持正版软件,购买注册,得到更好的正版服务。

附:
二○○二年一月一日《计算机软件保护条例》第十七条规定:为了学习和研究软件内含的设计思想和原理,通过安装、显示、传输或者存储软件等方式使用软件的,可以不经软件著作权人许可,不向其支付报酬!鉴于此,也希望大家按此说明研究软件!

版权声明:
一、本站致力于为软件爱好者提供国内外软件开发技术和软件共享,着力为用户提供优资资源。
二、本站提供的部分源码下载文件为网络共享资源,请于下载后的24小时内删除。如需体验更多乐趣,还请支持正版。
三、我站提供用户下载的所有内容均转自互联网。如有内容侵犯您的版权或其他利益的,若有侵犯你的权益请:提交版权证明文件到邮箱 2225329873#qq.com(#换为@) 站长会进行审查之后,情况属实的会在三个工作日内为您删除。

  • 站长家园(原代码之家)会员升级
  • 最新文章
    • Vue3和Vue2的差异是什么?全方位对比一下!

      Vue3和Vue2的差异是什么?全方位对比一下!

      Vue3和Vue2的差异是什么?下面本篇文章给大家全方位对比Vue3与Vue2,聊聊Vue3与Vue2的区别,希望对大家有所帮助!从Vue3发布以来,我就一直对...

    • 浮动是css3的新特性吗

      浮动是css3的新特性吗

      浮动不是css3的新特性。定义元素在哪个方向浮动的float属性在css1时就已经可以使用了,css的浮动会使元素向左或向右移动,其周围的元素也会重新排列,一个...

    • translate是css3属性吗

      translate是css3属性吗

      translate是css3的一个新的css属性;translate属性用于定义元素的2d平移转换,该属性常与transform属性配合使用,transform...

    • 浅析Angular中的独立组件,看看怎么使用

      浅析Angular中的独立组件,看看怎么使用

      本篇文章带大家了解一下Angular中的独立组件,看看怎么在Angular中创建一个独立组件,怎么在独立组件中导入已有的模块,希望对大家有所帮助!Angular...

    • link是不是css3新增样式规则

      link是不是css3新增样式规则

      link不是css3新增样式规则。“:link”是在css3之前就已经可以使用的选择器,可以用于设置链接的样式,该选择器用于选取未被访问的链接,不会设置已经访问...

    热门文章