PHP近期常见算法面试题

php近期常见算法面试题

面试的时候会经常问到一些算法题，算法题的考察主要考察的是基础知识的掌握程度和逻辑思考能力以及学习能力的考察，所以什么样的算法题是容易考到的呢？

一般常考的算法题中包含如下几种类型：字符串处理、数组处理、实现一个数据结构、排序算法、查找算法，大概也就这几种

通常来讲如果面试初、中级别的工程师的话会经常问到常见的排序算法和查找算法，不过高级开发工程师也可能在一面的时候会问到。高级开发工程师肯定会问到的就是字符串处理、数组处理或者是实现一个数据结构的算法题。

下面我把最近常被问到的这些算法题做一个大概的罗列，供大家参考，希望大家早日找到心仪的工作：

1.快速排序

它的最优时间复杂度为O(nlogn)【以标记元素为中心，正好每次左右都能均匀分配】，最糟糕时间复杂度为O(n^2)【标记元素每次是最大或最小值，使所有数都划分到一边】

<?php

function 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)【反序：数组排序刚好相反】

<?php
function 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)

<?php
function 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.优惠券排序：一个优惠券有面额和到期时间两种属性，按照面额从大到小排列，如果面额相同，按照到期时间的从小到大的顺序排列

<?php

class Discount
{
    public $money;

    public $time;

    function __construct($money, $time)
    {
        $this->money = $money;
        $this->time = $time;
    }

}

$discounts = [];
for ($i = 0; $i < 10; $i++) {
    $discount = new Discount(rand(1, 10), time() - rand(1111, 9999));
    array_push($discounts, $discount);
}
echo '<pre>';
function quick_sort($ds)
{
    if (count($ds) <= 1) {

        return $ds;
    } else {
        $left = [];
        $right = [];
        $dsCount = count($ds);
        for ($i = 1; $i < $dsCount; $i++) {
            if ($ds[$i]->money > $ds[0]->money) {
                array_push($left, $ds[$i]);
            } else if ($ds[$i]->money < $ds[0]->money) {
                array_push($right, $ds[$i]);
            } else {
                if ($ds[$i]->time <= $ds[0]->time) {
                    array_push($right, $ds[$i]);
                } else {
                    array_push($left, $ds[$i]);
                }
            }
        }
        $left = quick_sort($left);
        $right = quick_sort($right);

        return array_merge($left, [$ds[0]], $right);
    }
}

$result = quick_sort($discounts);
print_r($result);

6.有一个文件，里面每一行都是一个url，写一个算法，读取出现最多的五条，及其出现的次数

<?php
function make_file()
{
    $urls = ['q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p'];
    $num = count($urls);
    $file = fopen('data.txt', "w");
    for ($i = 0; $i < 1000; $i++) {
        fwrite($file, $urls[rand(0, $num - 1)] . "n");
    }
    fclose($file);
}

//make_file();

function get_result($filename, $num)
{
    $arr = [];
    $file = fopen($filename, 'r');
    while (!feof($file)) {
        $key = fgets($file);
        if ($key != "") {
            array_push($arr, $key);
        }
    }
    fclose($file);
    $counts = array_count_values($arr);
    $results = [];
    $keys = array_keys($counts);
    print_r($keys);
    for ($i = 0; $i < $num; $i++) {
        $key = $keys[0];
        foreach ($keys as $k) {
            if ($counts["$k"] > $counts["$key"]) {
                $key = $k;
            }
        }
        $results["$key"] = $counts["$key"];
        unset($counts["$key"]);
    }
    print_r($results);
}

get_result('data.txt', 5);

7.php实现斐波那契数列

斐波那契数列： 1 1 2 3 5 8 13 21 34 55 …

概念： 前两个值都为1，该数列从第三位开始，每一位都是当前位前两位的和 规律公式为： Fn = F(n-1) + F(n+1) F：指当前这个数列 n：指数列的下标

非递归写法：

<?php
function fbnq($n)
{  //传入数列中数字的个数
    if ($n <= 0) {
        return 0;
    }
    $array[1] = $array[2] = 1; //设第一个值和第二个值为1
    for ($i = 3; $i <= $n; $i++) { //从第三个值开始
        $array[$i] = $array[$i - 1] + $array[$i - 2];
//后面的值都是当前值的前一个值加上前两个值的和
    }
    return $array;
}

递归写法：

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

8.php找到字符数组里最左匹配长度的字符（最长公共前缀匹配算法）

输入: ["flower","flow","flight"]

输出: "fl"

示例 2:

输入: ["dog","racecar","car"]

输出: ""

解释: 输入不存在公共前缀。

<?php
$a = ["flower", "flow", "flww", "flight"];

function rep_test($arr)
{
    $return_str = '';
    if (empty($arr))
        return $return_str;

    $tmp_arr = [];  //声明一个临时的数组
    foreach ($arr as $v) {
        $tmp_arr[strlen($v)] = $v;
    }


    $min_str = $tmp_arr[min(array_keys($tmp_arr))]; //找到最短长度的字符串
    $min_len = strlen($min_str); //获取最小长度

    for ($i = 0; $i < $min_len; $i++) {


        foreach ($arr as $v) {
            if ($v[$i] != $min_str[$i]) {
                break 2;
            }

        }

    }
    if ($i > 0) {
        $return_str = substr($min_str, 0, $i);
    }

    return $return_str;
}


echo rep_test($a);
?>

9.PHP获取字符串中出现次数最多的字符

解法一：(最快速的解法)

<?php
$arr = str_split($str);
$arr = array_count_values($arr);
arsort($arr);
print_r($arr);

解法二：

<?php
$arr = str_split($str);
$unique = array_unique($arr);
foreach ($unique as $a) {
    $arr2[$a] = substr_count($str, $a);
}
arsort($arr2);
print_r($arr2);

10.PHP算法之无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"输出: 3解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。示例 2:

输入: "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3:

输入: "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

<?php

class Solution
{
    /**
     * @param String $s
     * @return Integer
     */
    function lengthOfLongestSubstring($s)
    {

        $l = strlen($s); //获取字符串总长度
        $len = 0;   //记录长度
        $find = ''; //保存截取字符串

        for ($i = 0; $i < $l; $i++) {
            $res = strpos($find, $s[$i]); // 查找$find中是否存在

            if ($res !== false) {

                $find .= $s[$i];

                $find = substr($find, $res + 1);

            } else {
                $find .= $s[$i];
            }

            $len = strlen($find) > $len ? strlen($find) : $len;
        }
        return $len;
    }
}

这是当前面试问的相对比较多的算法题，其中涉及到了很多的函数，实现逻辑等等。在此说明：时间复杂度指的是程序执行循环的大概的次数。

其中，数据结构算法题的考察，通常会考察一些比较简单的数据结构算法，比如：堆、栈、队列，这样简单的数据结构算法的实现，像hashtable这种比较复杂的很少考。

所以，从算法面试题来看，偏向于用常见的函数解决复杂的逻辑问题，大家复习的时候可以参考这些。

祝大家面试顺利！