PHP算法问题！附答案与思路解析

PHP是最好的编程语言!(开玩笑啦~~)作为一门老牌的编程语言，学习PHP的小伙伴肯定不少吧。今天 浙江优就业 的小U老师为大家带来了PHP算法的面试问题，一起来看一下吧。

1.如何快速寻找一个数组里最小的1000个数

思路：假设最前面的1000个数为最小的，算出这1000个数中最大的数，然后和第1001个数比较，如果这最大的数比这第1001个数小的话跳过，如果要比这第1001个数大则将两个数交换位置，并算出新的1000个数里面的最大数，再和下一个数比较，以此类推。

代码如下：

//寻找最小的k个数//题目描述//输入n个整数，输出其中最小的k个。/*** 获取最小的k个数* @param array $arr* @param int $k [description]* @return array*/function get_min_array($arr, $k){ $n = count($arr); $min_array = array(); for ($i = 0; $i < $n; $i++) { if ($i < $k) { $min_array[$i] = $arr[$i]; } else { if ($i == $k) { $max_pos = get_max_pos($min_array); $max = $min_array[$max_pos]; } if ($arr[$i] < $max) { $min_array[$max_pos] = $arr[$i]; $max_pos = get_max_pos($min_array); $max = $min_array[$max_pos]; } } } return $min_array;}/*** 获取最大的位置* @param array $arr* @return array*/function get_max_pos($arr){ $pos = 0; for ($i = 1; $i < count($arr); $i++) { if ($arr[$i] > $arr[$pos]) { $pos = $i; } } return $pos;}$array = [1, 100, 20, 22, 33, 44, 55, 66, 23, 79, 18, 20, 11, 9, 129, 399, 145, 2469, 58];$min_array = get_min_array($array, 10);print_r($min_array);

2.反转函数的实现

/*** 反转数组* @param array $arr* @return array*/function reverse($arr){ $n = count($arr); $left = 0; $ right = $n – 1; while ($left < $right) { $temp = $arr[$left]; $arr[$left++] = $arr[$right]; $arr[$right–] = $temp; } return $arr;}

3.约瑟夫环问题

相关题目：一群猴子排成一圈，按1,2,…,n依次编号。然后从第1只开始数，数到第m只,把它踢出圈，从它后面再开始数， 再数到第m只，在把它踢出去…，如此不停的进行下去， 直到最后只剩下一只猴子为止，那只猴子就叫做大王。要求编程模拟此过程，输入m、n, 输出最后那个大王的编号。

/*** 获取大王* @param int $n* @param int $m* @return int */function get_king_mokey($n, $m) { $arr = range(1, $n); $i = 0; while (count($arr) > 1) { $i++; $survice = array_shift($arr); if ($i % $m != 0) { array_push($arr, $survice); } } return $arr[0];}

4.两个有序int集合是否有相同元素的最优算法

/*** 寻找两个有序数组里相同的元素* @param array $arr1* @param array $arr2* @return array */function find_common($arr1, $arr2){ $common = array(); $i = $j = 0; $count1 = count($arr1); $count2 = count($arr2); while ($i < $count1 && $j < $count2) { if ($arr1[$i] < $arr2[$j]) { $i++; } elseif ($arr1[$i] > $arr2[$j]) { $j++; } else { $common[] = $arr[$i]; $i++; $j++; } } return array_unique($common);}

5.将一个数组中的元素随机(打乱)

/*** 打乱数组* @param array $arr* @return array */function custom_shuffle($arr){ $n = count($arr); for ($i = 0; $i < $n; $i++) { $rand_pos = mt_rand(0, $n – 1); if ($rand_pos != $i) { $temp = $arr[$i]; $arr[$i] = $arr[$rand_pos]; $arr[$rand_pos] = $temp; } } return $arr;}

6.给一个有数字和字母的字符串，让连着的数字和字母对应

function number _alphabet($str){ $number = preg_split(‘/[a-z]+/’, $str, -1, PREG_SPLIT_NO_EMPTY); $alphabet = preg_split(‘/d+/’, $str, -1, PREG_SPLIT_NO_EMPTY); $n = count($number); for ($i = 0; $i < $count; $i++) { echo $number[$i] . ‘:’ . $alphabet[$i] . ‘

‘; }}$str = ‘1a3bb44a2ac’;number_alphabet($str);//1:a 3:bb 44:a 2:ac

7.求n以内的质数(质数的定义：在大于1的自然数中，除了1和它本身意外，无法被其他自然数 整除 的数)

思路：

a.(质数筛选定理)n不能够被不大于根号n的任何质数整除，则n是一个质数

b.除了2的偶数都不是质数

代码如下：

/*** 求n内的质数* @param int $n* @return array*/function get_prime($n){ $prime = array(2);//2为质数 for ($i = 3; $i <= $n; $i += 2) {//偶数不是质数，步长可以加大 $sqrt = intval(sqrt($i));//求根号n for ($j = 3; $j <= $sqrt; $j += 2) {//i是奇数，当然不能被偶数整除，步长也可以加大。 if ($i % $j == 0) { break; } } if ($j > $sqrt) { array_push($prime, $i); } } return $prime;}print_r(getPrime(1000));

8.如何在有序的数组中找到一个数的位置(二分查找)

代码如下：

/*** 二分查找* @param array $array 数组* @param int $n 数组数量* @param int $value 要寻找的值* @return int*/function binary_search($array, $n, $value){ $left = 0; $right = $n – 1; while ($left <= $right) { $mid = intval(($left + $right) / 2); if ($value > $array[$mid]) { $right = $mid + 1; } elseif ($value < $array[$mid]) { $left = $mid – 1; } else { return $mid; } } return -1;}

9.找出有序数组中随机3个数和为0的所有情况

思路：动态规划

function three_sum($arr){ $n = count($arr); $return = array(); for ($i=0; $i < $n; $i++) { $left = $i + 1; $right = $n – 1; while ($left <= $right) { $sum = $arr[$i] + $arr[$left] + $arr[$right]; if ($sum < 0) { $left++; } elseif ($sum > 0) { $right–; } else { $numbers = $arr[$i] . ‘,’ . $arr[$left] . ‘,’ . $arr[$right]; if (!in_array($numbers, $return)) { $return[] = $numbers; } $left++; $right–; } } } return $return;}$arr = [-10, -9, -8, -4, -2, 0, 1, 2, 3, 4, 5, 6, 9];var_dump(three_sum($arr));

10.编写一个PHP函数，求任意n个正负整数里面最大的连续和，要求算法时间复杂度尽可能低。

思路：动态规划

/*** 获取最大的连续和* @param array $arr* @return int*/function max_sum_array($arr){ $currSum = 0; $maxSum = 0;//数组元素全为负的情况，返回最大数 $n = count($arr); for ($i = 0; $i < $n; $i++) { if ($currSum >= 0) { $currSum += $arr[$i]; } else { $currSum = $arr[$i]; } } if ($currSum > $maxSum) { $maxSum = $currSum; } return $maxSum;}

11.给定一个有序整数序列，找出绝对值最小的元素

思路：二分查找

/*** 获取绝对值最小的元素* @param array $arr* @return int */function get_min_abs_value($arr){ //如果符号相同，直接返回 if (is_same_sign($arr[0], $arr[$n – 1])) { return $arr[0] >= 0 ? $arr[0] : $arr[$n – 1]; } //二分查找 $n = count($arr); $left = 0; $right = $n – 1; while ($left <= $right) { if ($left + 1 === $right) { return abs($arr[$left]) < abs($arr[$right]) ? $arr[$left] : $arr[$right]; } $mid = intval(($left + $right) / 2); if ($arr[$mid] < 0) { $left = $mid + 1; } else { $right = $mid – 1; } }}/*** 判断符号是否相同* @param int $a* @param int $b* @return boolean */function is_same_sign($a, $b){ if ($a * $b > 0) { return true; } else { return false; }}