PHP 인터뷰를 위한 일반적인 기본 알고리즘(코드 예제 포함)

이 글은 PHP에 대한 관련 지식을 제공합니다. 주로 피보나치 수 재귀 방법, 파일 디렉터리 검색, 이진 검색 및 기타 문제를 포함한 일반적인 기본 알고리즘에 대한 관련 내용을 소개합니다. 코드가 모든 사람에게 도움이 되기를 바랍니다.

추천 학습: "PHP 비디오 튜토리얼"

머리말

PHP는 한때 PHPer에서는 알고리즘이 중복된다고 생각되었으며, 종종 약간의 검토가 이루어집니다. , 대부분의 인터뷰 상황에서 모든 사람이 버블 정렬을 작성하라는 요청을 받을 것이라고 생각하지만, 심지어 저처럼 버블 정렬을 작성하는 데 반나절을 소비하는 PHP 사용자도 있습니다.

일반적으로 다음 알고리즘으로 충분합니다. 인터뷰! ! ! 틀린 부분이 있으면 댓글로 지적해주시고 수정해주시면 감사하겠습니다!

완료

• 피보나치 수열

• 폴더 스캔

• 이진 검색

• 버블 정렬

• 빠른 정렬

• LeetCode 첫 번째 질문

TODO

• 힙 정렬

• 선택 정렬

• 링크된 목록 뒤집기

• 동적 프로그래밍

<?php
class Algorithmic {
    /***
     * 斐波那契数递归法，f(n) = f(n-1) + f(n-2) 递归层级太多，调用栈爆满，100层
     */
    function fib($n) {
        if ($n < 2) {
            return 1;
        } else {
            return $this->fib($n - 1) + $this->fib($n - 2);
        }
    }
    /***
     * 使用数组存储每一个fib(n)的数值，空间复杂度增加
     * @param $dir
     * @return array
     */
    function fib2($n) {
        if ($n < 2) {
            return 1;
        } else {
            $arr = [1, 1];
            for ($i = 2; $i <= $n; $i++) {
                $arr[$i] = $arr[$i - 1] + $arr[$i - 2];
            }
        }
        return $arr[$n];
    }
    /***
     * 使用两个临时变量存储前两个值fib(n)的数值，空间复杂度增加比数组降低
     * @param $dir
     * @return array
     */
    function fib3($n) {
        if ($n < 2) {
            return 1;
        } else {
            $last = 1;  //等式第二项
            $lastLast = 1;  //等式第一项
            for ($i = 2; $i <= $n; $i++) {
                $current = $last + $lastLast;
                $lastLast = $last;
                $last = $current;
            }
            return $current;
        }
    }
    /***
     * 扫描文件目录
     * @param $dir
     * @return array
     */
    function scanFile($dir) {
        $fileList = [];
        if (is_dir($dir)) {
            $dh = opendir($dir);
            while ($file = readdir($dh)) {
                if ($file == &#39;.&#39; || $file == &#39;..&#39;) continue;  //linux下一切皆文件
                $newDir = $dir . &#39;/&#39; . $file;
                if (is_dir($newDir)) {
                    $fileList[][$file] = $this->scanFile($newDir);
                } else {
                    $fileList[] = $file;
                }
            }
            closedir($dh);
        }
        return $fileList;
    }
    /***
     * 二分查找
     */
    function binarySort($arr, $target) {
        if (!is_array($arr) || count($arr) < 2) {
            return $arr;
        }
        $len = count($arr);
        $start = 0;
        $end = $len - 1;
        while ($start <= $end) {
            $middle = floor(($start + $end) / 2) ;
            if ($arr[$middle] == $target) {
                return $middle;
            } elseif ($arr[$middle] < $target) {
                $start = $middle + 1;
            } else {
                $end = $middle - 1;
            }
        }
        return false;
    }
    /***
     * 冒泡排序
     */
    function bubbleSort($arr) {
        for ($i = count($arr) - 1; $i > 0; $i--) {
            for ($j = 0; $j < $i; $j++) {
                if ($arr[$j+1] < $arr[$j]) {
                    $temp = $arr[$j];
                    $arr[$j] = $arr[$j+1];
                    $arr[$j+1] = $temp;
                }
            }
        }
        return $arr;
    }
    /***
     * 快排序
     */
    function quickSort($arr) {
        if (!is_array($arr) || count($arr) < 2) {
            return $arr;
        }
        $base = $arr[0];
        $left = [];
        $right = [];
        for ($i = 1; $i <= count($arr) - 1; $i++) {
            if ($arr[$i] < $base) {
                $left[] = $arr[$i];
            } else {
                $right[] = $arr[$i];
            }
        }
        return array_merge(array_merge($this->quickSort($left),[$base]), $this->quickSort($right));
    }
    /***
     * 两数之和， LeetCode第一题
     * @param $arr
     */
    function twoSum($arr, $sum = 8){
        $tempArr = [];
        foreach ($arr as $k => $v) {
            if (isset($tempArr[$v])) {
                return [$k, $tempArr[$v]];
            }
            $tempArr[$sum-$v] = $k;
        }
        return [];
    }
}
$algorithmic = new Algorithmic();
//var_dump($algorithmic->scanFile("./"));
//var_dump($algorithmic->twoSum([4,5,3,4,5,67,787]));
//var_dump($algorithmic->fib3(4));  // 1 1 2 3 5
//var_dump($algorithmic->binarySort([1,3, 4, 5,7,9], 3));  //
var_dump($algorithmic->quickSort([14,5,13,114,4,3,167,87,14]));

추천 학습: 《 PHP 비디오 튜토리얼》

위 내용은 PHP 인터뷰를 위한 일반적인 기본 알고리즘(코드 예제 포함)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!