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這種比較復雜的很少考。
所以，從算法面試題來看，偏向于用常見的函數解決復雜的邏輯問題，大家復習的時候可以參考這些。
祝大家面試順利！
