PHP面試之四：邏輯與算法

smartlion 發布于2019-06-28 14:11 / 542人閱讀

摘要：數據結構常見數據結構數組是最簡單而且應用最廣泛的數據結構特征使用連續內存空間來存儲存放相同類型或著衍生類型的元素數組比較特別，可以存放八種數據類型通過下標來訪問集合特征保存不重復的元素字典特征就是關聯數組，以形式存儲棧，與隊列相似特征存儲數

數據結構

常見數據結構

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邏輯與自然語言處理算法面試

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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