• 欢迎访问IT乐园(o゚▽゚)o
  • 推荐使用最新版火狐浏览器和Chrome浏览器访问本网站。

一些算法及实现

代码 fhy 2年前 (2018-03-19) 886次浏览 0个评论
文章目录[隐藏]

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;
}

持续增加


IT 乐园 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:一些算法及实现
喜欢 (1)
关于作者:
九零后挨踢男
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址