PHP面试高薪宝典系列: 常见基础算法（附完整代码）

前言

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

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

已完成

• 杨辉三角打印
• 斐波那契数列
• 扫描文件夹
• 二分查找
• 冒泡排序
• 快速排序
• LeetCode第一题(数组找定和)
• 两个有序数组求交集
• 找零钱
• 约瑟夫环
• 汉诺塔

TODO

• 堆排序
• 链表翻转
• 动态规划

<?php
class Algorithmic {
  /***
     * 打印杨辉三角， 核心使用二位数组保存数值
     * @param $n
     * @return void
     */
    function printYang($n)
    {
        $arr = [];
        for ($i= 1; $i < $n + 1; $i++) {
            $blank = str_repeat(" " ,$n - $i); //右移空格数量
            echo $blank;
            for ($j = 1; $j < $i + 1; $j++) {
                if ($j == 1 || $j == $i) {    
                    echo $arr[$i][$j] = 1;   //最左边和最右边值为1
                } else {
                    echo $arr[$i][$j] = $arr[$i - 1][$j -1] + $arr[$i-1][$j]; //等于上一排两个数之和
                }
                echo " ";
            }
            echo  PHP_EOL;  //每行换行
        }
    }
    /***
     * 斐波那契数递归法，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 [];
    }

    /***
     * 两有序数组求交集 双指针同向移动比较大小
     * @param $arr1
     * @param $arr2
     * @return array
     */
     function intersection($arr1, $arr2)
     {
          $lens1 = count($arr1);
          $lens2 = count($arr2);
          $i = 0;
          $j = 0;
          $newArr = [];
          //双指针，i指向数组arr1， j指向arr2, 同向移动指针进行追赶，当任意一个数组迭代完则结束
          while ($i < $lens1 && $j < $lens2) {
            //相等则记录，双指针向前移动过
              if ($arr1[$i] == $arr2[$j]) {
                        $newArr[] = $arr1[$i];
              $i++;
              $j++;
              //哪个指针指的小，往前移动一位进行比较
              } elseif ($arr1[$i] < $arr2[$j]) {
                        $i++;
              } else {
                        $j++;
              }
        }
        return $newArr;
    }

    /***
     * 找零钱问题
     * @param $total 商品总价
     * @param $pay 付的钱
     * @return array
     */
     function changeMoney($total, $pay)
     {
        $change = []; //定义一个数组，用于存放找零钱的种类
        $changeMoney = $pay - $total; //计算找零钱的总金额
        $money = [100, 50, 20, 10, 5, 2, 1];
        //循环遍历货币数组
        foreach($money as $value){
        //计算每种货币的数量
        $num = floor($changeMoney/$value);
        //如果数量大于0，则将该种货币的数量和面值存入数组
        if($num > 0){
            $change[$value] = $num;
            //计算剩余的找零钱
            $changeMoney = $changeMoney - $num*$value;
          }
        }
        //返回找零钱的数组
      return $change;
    }

    /***
     * 约瑟夫环问题
     * https://blog.csdn.net/shichunlai18/article/details/127787779 
     * 问题描述：一群猴子排成一圈，按1,2,…,n依次编号。
     * 然后从第1只开始数，数到第m只,把它踢出圈，从它后面再开始数，再数到第m只，在把它踢出去，这样循环到最后一个猴子为猴王
     * @param $n
     * @param $m
     * @return int
     **/
    function josephus($n, $m)
    {
         $arr = range(1, $n); //生成1-n的数组
         $i = 1;
         while (count($arr) > 1){ //个数还剩1的时候结束，就是猴王
              if ($i % $m != 0) {
                 $arr[] = $arr[$i - 1]; //不被踢出则压入数组尾部
              }
              unset($arr[$i - 1]); //然后删除, 注意：数组索引一直在增加， 元素在减少
              $i++;
          }
          return $arr[$i - 1];
    }

    /**
     * 汉诺塔问题   2^n - 1 次数
     * https://zhuanlan.zhihu.com/p/28594231
     * 2*(2^(n-1) - 1) +1 = 2^n - 1 次数
     * @param $n
     * @param $x
     * @param $y
     * @param $z
     * @return void
     */
     function hanTower($n, $x, $y, $z)
     {
          if ($n == 1) {
             echo "移动 1 从" . $x . "到" . $z . PHP_EOL;
          } else {
              $this->hanTower($n - 1, $x, $z, $y);
              echo "移动 $n 从" . $x . "到" . $z . PHP_EOL;
              $this->hanTower($n-1, $y, $x, $z);
          }
    }
}
$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]));

本作品采用《CC 协议》，转载必须注明作者和本文链接