文章目录[隐藏]
1.反转函数的实现
/**
* 反转数组
* @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;
}
2.两个有序 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);
}
3.将一个数组中的元素随机（打乱）
/**
* 打乱数组
* @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;
}
4.给一个有数字和字母的字符串，让连着的数字和字母对应
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] . '</br>';
}
}
$str = '1a3bb44a2ac';
number_alphabet($str);//1:a 3:bb 44:a 2:ac
5.求 n 以内的质数
（质数的定义：在大于 1 的自然数中，除了 1 和它本身意外，无法被其他自然数整除的数）
思路：
1.（质数筛选定理）n 不能够被不大于根号 n 的任何质数整除，则 n 是一个质数
2.除了 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));
6.约瑟夫环问题
相关题目：一群猴子排成一圈，按 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];
}
7.如何快速寻找一个数组里最小的 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);
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.给定一个有序整数序列，找出绝对值最小的元素
/**
* 获取绝对值最小的元素
* @param array $arr
* @return int
*/
function get_min_abs_value($arr)
{
$n = count($arr);
//如果符号相同，直接返回
if (is_same_sign($arr[0], $arr[$n - 1])) {
return $arr[0] >= 0 ? $arr[0] : $arr[$n - 1];
}
//二分查找
$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;
}
}
10.找出有序数组中随机 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));
11.求任意 n 个正负整数里面最大的连续和
编写一个 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;
}
