PHP面试之常见基础算法（附代码示例）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
<?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 == '.' || $file == '..') continue;  //linux下一切皆文件
                $newDir = $dir . '/' . $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]));