面试的时候会经常问到一些算法题，由此我对近期各大公司面试考察频率比较高的算法题进行了总结，帮助更多同学快速找到心仪工作。算法题的考察主要考察的是基础知识的掌握程度和逻辑思考能力以及学习能力的考察，所以什么样的算法题是容易考到的呢？
一般常考的算法题中包含如下几种类型：字符串处理、数组处理、实现一个数据结构、排序算法、查找算法，大概也就这几种
通常来讲如果面试初、中级别的工程师的话会经常问到常见的排序算法和查找算法，不过高级开发工程师也可能在一面的时候会问到。高级开发工程师肯定会问到的就是字符串处理、数组处理或者是实现一个数据结构的算法题。
下面我把最近常被问到的这些算法题做一个大概的罗列，供大家参考，希望大家早日找到心仪的工作：
1.快速排序
它的最优时间复杂度为O(nlogn)【以标记元素为中心，正好每次左右都能均匀分配】，最糟糕时间复杂度为O(n^2)【标记元素每次是最大或最小值，使所有数都划分到一边】
function quickSort($arr){
$count = count($arr); //统计出数组的长度
if ($count
return $arr;
}
$index = $arr[0]; // 把第一个元素作为标记
$left = []; //定义一个左空数组
$right = []; //定义一个有空数组
for ($i = 1; $i
if ($arr[$i]
$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)【反序：数组排序刚好相反】
function bubbleSort($arr){
$count = count($arr); //统计出数组的长度
for ($i = 1; $i
for ($j = 0; $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)
function getQuick($arr){
$len = count($arr);
if ($len
return $arr;
}
$num = $arr[0];
$big = array();
$small = array();
foreach ($arr as $v) {
if ($v > $num)
$big[] = $v; //把比$num大的数放到一个数组里
if ($v
$small[] = $v; //把比$num小的数放到另一个数组里
}
$big = getQuick($big);
$small = getQuick($small);
return array_merge($big, array($num), $small);
}
4.二分查找
它的最优时间复杂度为O(1)，最糟糕时间复杂度为O(log2n)
递归方式：
$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 var_dump($low, $high); echo "\n"; $mid = intval(($low + $high) / 2); if ($array[$mid] == $target) { return true; } elseif ($target
$find = bin_search($array, $low, $high, $target);var_dump($find);
循环方式：
$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
var_dump($low, $high); echo "\n";
$mid = intval(($low + $high) / 2);
if ($array[$mid] == $target) {
$find = true;
break;
} elseif ($array[$mid]
$low = $mid + 1;
} elseif ($array[$mid] > $target) {
$high = $mid - 1;
}
} else {
break;
}
}
return $find;
}
$find = bin_search($array, $target);
var_dump($find);
5.优惠券排序：一个优惠券有面额和到期时间两种属性，按照面额从大到小排列，如果面额相同，按照到期时间的从小到大的顺序排列
class Discount{ public $money;
public $time;
function __construct($money, $time){ $this->money = $money; $this->time = $time; }
}
$discounts = [];for ($i = 0; $i
return $ds; } else { $left = []; $right = []; $dsCount = count($ds); for ($i = 1; $i money > $ds[0]->money) { array_push($left, $ds[$i]); } else if ($ds[$i]->money money) { array_push($right, $ds[$i]); } else { if ($ds[$i]->time 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，写一个算法，读取出现最多的五条，及其出现的次数
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
//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 $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：指数列的下标
非递归写法：
function fbnq($n){ //传入数列中数字的个数 if ($n return 0; } $array[1] = $array[2] = 1; //设第一个值和第二个值为1 for ($i = 3; $i $array[$i] = $array[$i - 1] + $array[$i - 2];//后面的值都是当前值的前一个值加上前两个值的和 } return $array;}
递归写法：
function fbnq($n){
if($n
if($n == 1 || $n == 2) return 1;
return fbnq($n - 1) + fbnq($n - 2);
}
8.php找到字符数组里最左匹配长度的字符（最长公共前缀匹配算法）
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
$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
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获取字符串中出现次数最多的字符
解法一：(最快速的解法)
$arr = str_split($str);$arr = array_count_values($arr);arsort($arr);print_r($arr);
解法二：
$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" 是一个子序列，不是子串。
class Solution{ /** * @param String $s * @return Integer */ function lengthOfLongestSubstring($s){
$l = strlen($s); //获取字符串总长度 $len = 0; //记录长度 $find = ''; //保存截取字符串
for ($i = 0; $i
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这种比较复杂的很少考。
所以，从算法面试题来看，偏向于用常见的函数解决复杂的逻辑问题，大家复习的时候可以参考这些。
祝大家面试顺利！
