PHP近期常见算法面试题 _PHP

文章插图
php近期常见算法面试题
面试的时候会经常问到一些算法题，算法题的考察主要考察的是基础知识的掌握程度和逻辑思考能力以及学习能力的考察，所以什么样的算法题是容易考到的呢？
【PHP近期常见算法面试题】一般常考的算法题中包含如下几种类型：字符串处理、数组处理、实现一个数据结构、排序算法、查找算法，大概也就这几种
通常来讲如果面试初、中级别的工程师的话会经常问到常见的排序算法和查找算法，不过高级开发工程师也可能在一面的时候会问到。高级开发工程师肯定会问到的就是字符串处理、数组处理或者是实现一个数据结构的算法题。
下面我把最近常被问到的这些算法题做一个大概的罗列，供大家参考，希望大家早日找到心仪的工作：
1.快速排序
它的最优时间复杂度为O(nlogn)【以标记元素为中心，正好每次左右都能均匀分配】，最糟糕时间复杂度为O(n^2)【标记元素每次是最大或最小值，使所有数都划分到一边】

<?phpfunction quickSort($arr){$count = count($arr);//统计出数组的长度if ($count <= 1) { // 如果个数为空或者1，则原样返回数组return $arr;}$index = $arr[0]; // 把第一个元素作为标记$left = [];//定义一个左空数组$right = [];//定义一个有空数组for ($i = 1; $i < $count; $i++) {//从数组的第二数开始与第一个标记元素作比较if ($arr[$i] < $index) {//如果小于第一个标记元素则放进left数组$left[] = $arr[$i];} else {//如果大于第一个标记元素则放进right数组$right[] = $arr[$i];}}$left = quickSort($left);//把left数组再看成一个新参数，再递归调用，执行以上的排序$right = quickSort($right);//把right数组再看成一个新参数，再递归调用，执行以上的排序return array_merge($left, [$arr[0]], $right);//最后把每一次的左数组、标记元素、右数组拼接成一个新数组}$arrtest = [12, 43, 54, 33, 23, 14, 44, 53, 10, 3, 56]; //测试数组$res = quickSort($arrtest);var_dump($res);

2.冒泡排序
它的最优时间复杂度为O(n)【正序，数组排好情况下】，最糟糕时间复杂度为O(n^2)【反序：数组排序刚好相反】

<?phpfunction bubbleSort($arr){$count = count($arr);//统计出数组的长度for ($i = 1; $i < $count; $i++) {//控制需要排序的轮数，该例子共需要比较10轮for ($j = 0; $j < $count - $i; $j++) {//控制每一轮需要比较的次数，每轮选出最大的一个值放在最后if ($arr[$j] > $arr[$j + 1]) {$temp = $arr[$j];//通过$temp介质把大的值放在后面$arr[$j] = $arr[$j + 1];$arr[$j + 1] = $temp;}}}return $arr;//返回最终结果}$arrtest = [12, 43, 54, 33, 23, 14, 44, 53, 10, 3, 56]; //测试数组$res = bubbleSort($arrtest);var_dump($res);

3.快速查找
它的最优时间复杂度为O(nlogn)，最糟糕时间复杂度为O(n^2)

<?phpfunction getQuick($arr){$len = count($arr);if ($len <= 1) {return $arr;}$num = $arr[0];$big = array();$small = array();foreach ($arr as $v) {if ($v > $num)$big[] = $v;//把比$num大的数放到一个数组里if ($v < $num)$small[] = $v;//把比$num小的数放到另一个数组里}$big = getQuick($big);$small = getQuick($small);return array_merge($big, array($num), $small);}

4.二分查找
它的最优时间复杂度为O(1)，最糟糕时间复杂度为O(log2n)
递归方式：

<?php$array = [1, 3, 6, 9, 13, 18, 19, 29, 38, 47, 51, 56, 58, 59, 60, 63, 65, 69, 70, 71, 73, 75, 76, 77, 79, 89];$target = 73;$low = 0;$high = count($array) - 1;function bin_search($array, $low, $high, $target){if ($low <= $high) {var_dump($low, $high);echo "n";$mid = intval(($low + $high) / 2);if ($array[$mid] == $target) {return true;} elseif ($target < $array[$mid]) {return bin_search($array, $low, $mid - 1, $target);} else {return bin_search($array, $mid + 1, $high, $target);}}return false;}$find = bin_search($array, $low, $high, $target);var_dump($find);

循环方式：

<?php$array = [1, 3, 6, 9, 13, 18, 19, 29, 38, 47, 51, 56, 58, 59, 60, 63, 65, 69, 70, 71, 73, 75, 76, 77, 79, 89];$target = 73;function bin_search($array, $target){$low = 0;$high = count($array) - 1;$find = false;while (true) {if ($low <= $high) {var_dump($low, $high);echo "n";$mid = intval(($low + $high) / 2);if ($array[$mid] == $target) {$find = true;break;} elseif ($array[$mid] < $target) {$low = $mid + 1;} elseif ($array[$mid] > $target) {$high = $mid - 1;}} else {break;}}return $find;}$find = bin_search($array, $target);var_dump($find);

5.优惠券排序：一个优惠券有面额和到期时间两种属性，按照面额从大到小排列，如果面额相同，按照到期时间的从小到大的顺序排列