PHP面试之四：逻辑与算法

smartlion 发布于2019-06-28 14:11 / 532人阅读

摘要：数据结构常见数据结构数组是最简单而且应用最广泛的数据结构特征使用连续内存空间来存储存放相同类型或着衍生类型的元素数组比较特别，可以存放八种数据类型通过下标来访问集合特征保存不重复的元素字典特征就是关联数组，以形式存储栈，与队列相似特征存储数

数据结构

常见数据结构

Array 数组是 最简单 而且 应用最广泛 的数据结构

特征：
1、使用连续内存空间来存储
2、存放相同类型或着衍生类型的元素（PHP数组比较特别，可以存放八种数据类型）
3、通过下标来访问

Set 集合

特征：
1、保存不重复的元素

Map 字典

特征：
1、就是PHP关联数组，以Key/Value形式存储

Stack 栈，与队列相似

特征：
1、存储数据是先进先出，栈只有一个出口，只能从栈顶部添加和删除元素

Heap 堆，与二叉树的数据结构相似

特性：
1、子节点的键值和索引总小于他的父节点

list 线性表，由零个或多个数据元素组成的有序序列

特性：
1、线性表是一个序列，在PHP中就是索引数组

Queue 队列

特性：
1、先进先出，并发中使用，可以安全地将对象从一个任务传给另一个任务，可以使用PHP数组模拟

如何模拟双向链表？

使用数组Array来实现
array_shift() / array_unshift()
array_pop() / array_push()

其它逻辑算法

重点：找出算法的规律，再用代码来实现

模拟PHP内置函数来实现某些功能

不使用PHP内置函数的前提下，实现字符串翻转

function str_rev($str){

    for($i=0;true;$i++){
        if(!isset($str[$i])){
            break;
        }
    }
    $return = "";
    for($j=$i-1;$j>=0;$j--){
        $return .= $str[$j];
    }
    return $return;
}

常见算法考点

算法是什么？

是一种解决问题的计算方法，一个问题有多种算法来解决，每种算法效率都不同，根据需求选择最优算法

时间复杂度和空间复杂度

作用：用于评定 某算法 是否合适？是否高效？

时间复杂度：执行算法所需要的时间
空间复杂度：执行算法所需要的内存空间

常见时间复杂度 例如：常数阶O(1)、线性阶O(n)、平方阶O(n^2)、立方阶O(n^3)、对数阶O(log2n)、nlog2n阶O(nlog2n)、指数阶O(n^n)

效率从大到小：O(1) > O(log2n) > O(n) > O(nlog2n) > O(n^2) > O(n^3) > O(2^n) > O(n!) > O(n^n)

时间复杂度计算方式：得出算法的计算次数（空间复杂度与之类似）
用1来取代说有确定次数的加法

常见排序算法

冒泡排序、直接插入排序、希尔排序、选择排序、快速排序、归并排序、堆排序

冒泡排序
               最坏情况        平均情况
时间复杂度      O(n^2)         O(n^2)
空间复杂度      O(1)

直接插入排序
               最坏情况        平均情况
时间复杂度      O(n^2)         O(n^2)
空间复杂度      O(1)

希尔排序
               最坏情况        平均情况
时间复杂度      O(n^2)         O(nlog2n)
空间复杂度      O(1)

选择排序
               最坏情况        平均情况
时间复杂度      O(n^2)         O(n^2)
空间复杂度      O(1)

快速排序
               最坏情况        平均情况
时间复杂度      O(n^2)         O(nlog2n)
空间复杂度      O(n)           O(log2n)

归并排序
               最坏情况        平均情况
时间复杂度      O(nlog2n)         O(nlog2n)
空间复杂度      O(n)

堆排序
               最坏情况        平均情况
时间复杂度      O(nlog2n)      O(nlog2n)
空间复杂度      O(1)

常见查找算法

二分查找、顺序查找

二分查找        最坏情况        平均情况
时间复杂度      O(log2n)       O(log2n)
空间复杂度      迭代O(1)       递归O(log2n)

顺序查找        最坏情况        平均情况
时间复杂度      O(n)           O(n)
空间复杂度      O(1)

GPU云服务器云服务器 java逻辑面试逻辑与 python逻辑与自然语言处理算法面试

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/26032.html

Codeigniter 4.0-dev 版源码学习笔记之四——详细路由过程

摘要：行，判断如果为空，那么返回默认路由。行，把处理完毕后找到的返回。方法该方法是自动按着约定规则去目录去找路由的过程。此文可以转载，但转载前需要发邮件到进行沟通，未沟通的均视作侵权。前言我个人觉得在当前 MVC 流行的架构下，要想去了解一个框架，或者是一个基于此架构下的应用程序，最好的入手方式就是先看路由，虽然路由不是 MVC 里的任何一个，但是知道了路由的来龙去脉就知道了整个框架或者...

NSFish 2019-06-27 16:28 评论0 收藏0
【面试系列】之四：关于原生dom操作

摘要：指向后一个同辈元素的元素版。复制后返回的节点副本属于文档所有，但并没有为它指定父节点。生成结束秒钟后，将个颠倒过来，内容也就变成了。之四：关于原生dom操作下周被内推了百度糯米的面试，决定趁这个周末恶补下原生的js基础，感觉自己被jQuery惯坏了吧！前两天听首页部同组的大牛师兄说：其实还是js基础重要，不要盲目追求新技术，基础练好了就像把自己的内功修炼好，内功扎实才能修炼好武功秘...

hatlonely 2019-08-20 10:23 评论0 收藏0
PHP面试常考之设计模式——策略模式

摘要：策略模式介绍策略模式定义了一系列的算法，并将每一个算法封装起来，而且使它们还可以相互替换。策略模式让算法独立于使用它的客户而独立变化。使用策略模式的好处策略模式提供了管理相关的算法族的办法。使用策略模式可以避免使用多重条件转移语句。你好，是我琉忆，PHP程序员面试笔试系列图书的作者。本周（2019.3.11至3.15）的一三五更新的文章如下：周一：PHP面试常考之设计模式——工...

Drinkey 2019-07-01 12:35 评论0 收藏0
前端周报：前端面试题及答案总结；JavaScript参数传递的深入理解

摘要：前端面试题及答案总结掘金技术征文金三银四，金九银十，用来形容求职最好的几个月。因为的存在，至少在被标准化的那一刻起，就支持异步编程了。然而异步编程真正发展壮大，的流行功不可没。 showImg(https://segmentfault.com/img/bVVQOH?w=640&h=319); 1、2017前端面试题及答案总结 |掘金技术征文金三银四，金九银十，用来形容求职最好的几个月...

ermaoL 2019-08-21 16:46 评论0 收藏0