您当前的位置:首页 > 电脑百科 > 程序开发 > 语言 > php

PHP近期常见算法面试题

时间:2020-08-10 16:25:36  来源:  作者:
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这种比较复杂的很少考。

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

祝大家面试顺利!



Tags:PHP 算法面试题   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
PHP近期常见算法面试题面试的时候会经常问到一些算法题,算法题的考察主要考察的是基础知识的掌握程度和逻辑思考能力以及学习能力的考察,所以什么样的算法题是容易考到的呢?一...【详细内容】
2020-08-10  Tags: PHP 算法面试题  点击:(231)  评论:(0)  加入收藏
▌简易百科推荐
序言:前段时间织梦因为版权的问题在网上闹得沸沸扬扬,也提醒了众多开发者选择cms上应该谨慎使用,今天给大家展示一款自己搭建的内容管理系统,不用担心版权的问题,而且非常容易维...【详细内容】
2021-11-30  小程序软件开发    Tags:管理系统   点击:(31)  评论:(0)  加入收藏
准备安装包(PHP: Hypertext Preprocessor)下载安装包以及组件wget https://www.php.net/distributions/php-8.0.0.tar.bz2wget https://github.com/phpredis/phpredis/archive...【详细内容】
2021-11-09  mimic96    Tags:PHP   点击:(40)  评论:(0)  加入收藏
golang context 很好用,就使用php实现了github地址 : https://github.com/qq1060656096/php-go-context context使用闭坑指南1. 将一个Context参数作为第一个参数传递给传入和...【详细内容】
2021-11-05  1060656096    Tags:PHP   点击:(41)  评论:(0)  加入收藏
一段数组为例:$list = array:4 [ 0 => array:7 [ "id" => 56 "mer_id" => 7 "order_id" => "wx163265961408769974" "is_postage" => 0 "store_name" => "奇...【详细内容】
2021-09-29  七七小影视    Tags:PHP   点击:(64)  评论:(0)  加入收藏
利用JS的CryptoJS 3.x和PHP的openssl_encrypt,openssl_decrypt实现AES对称加密解密,由于需要两种语言对同一字符串的操作,而CryptoJS 的默认加密方式为“aes-256-cbc”,PHP端也...【详细内容】
2021-09-16  李老师tome    Tags:对称加密   点击:(79)  评论:(0)  加入收藏
1、checkdate()验证格利高里日期即:日期是否存在。checkdate(month,day,year);month必需。一个从 1 到 12 的数字,规定月。day必需。一个从 1 到 31 的数字,规定日。year必需。...【详细内容】
2021-08-31  七七小影视    Tags:时间函数   点击:(80)  评论:(0)  加入收藏
对于各类开发语言来说,整数都有一个最大的位数,如果超过位数就无法显示或者操作了。其实,这也是一种精度越界之后产生的精度丢失问题。在我们的 PHP 代码中,最大的整数非常大,我...【详细内容】
2021-08-26  硬核项目经理    Tags:PHP   点击:(83)  评论:(0)  加入收藏
遵从所有教材以及各类数据结构相关的书书籍,我们先从线性表开始入门。今天这篇文章更偏概念,是关于有线性表的一个知识点的汇总。上文说过,物理结构是用于确定数据以何种方式存...【详细内容】
2021-07-19  硬核项目经理    Tags:线性表   点击:(94)  评论:(0)  加入收藏
一、开启IIS全部功能。二、部署PHP1.官网下载并解压PHP: https://windows.php.net/downloads/releases/2.将php.ini-development文件改为php.ini3.修改php.ini(1)去掉注释,并修...【详细内容】
2021-07-15  炘蓝火诗  今日头条  Tags:PHP环境   点击:(128)  评论:(0)  加入收藏
一、环境说明本文中使用本地VM虚机部署测试。OS:CentOS Linux release 7.8.2003 (Core)虚机配置:2核CPU、4G内存①系统为CentOS 7.8 x64最小化安装,部署前已完成系统初始化、...【详细内容】
2021-06-25  IT运维笔记  今日头条  Tags:PHP8.0.7   点击:(141)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条