算法函数

1、1234567890 显示 1,234,567,890

//1. 先反转字符串
//2. 3个字符切割数据
//3. 把切割的数组以 “,”拼接为字符串
//4. 再次反转数据

$str = 1234567890;
var_dump( strrev(implode(',',str_split(strrev($str),3))) );

或:
echo number_format('123456789')."<br>";


2、将 "1234567890" 转换成 "0987654321"? 不使用php 字符串内置函数--strrev

//第一种方式
function strrev2($str)
{
    $len = strlen($str);
    $string = '';
    for ($i=$len; $i > 0 ; $i--) { 
        # code...
        $string .= $str[$i-1];
    }
    return $string;
}

var_dump(strrev2('1234567890'));


// 第二种---递归调用
function reverse($str){  
    if(strlen($str)>0){     
        reverse(substr($str,1));  
        echo substr($str,0,1);    
        return;  
    } 
}
$res = reverse("abcdefg");//gfedcba
var_dump($res);



//第三种  abcdefg -> gfedcba
$s = '1234567890';
$o = '';
$i = 0;
while(isset($s[$i]) && $s[$i] != null) {    
    $o = $s[$i++].$o;
}
echo $o;


//第四种  abcdefg -> gfedcba
//将字符串看做数组来处理 [a,b,c,d,e,f,g]
function str_rev($str){    
    for ($i = 0; true; $i++){
        // 判断字符串长度    
        if (!isset($str[$i])){
            break;        
        }   
    }    
    $return = '';    
    for ($j = $i-1; $j >= 0; $j--){       
        $return .= $str[$j];
    }
    return $return;
}
echo str_rev('abcdefg'); // 调用函数


// 第五种方式
//10  9  8  7  6  5  4  3  2  1  0  <-->0  1  2  3  4  5  6  7  8  9  10
function test($n){
    echo $n."  ";
    if($n>0)
        test($n-1);
    else
        echo "<-->";
    echo $n."  ";
}
test(10);


3、反转数组,不使用数组内部函数--array_reverse

/**
 * 反转数组
 * @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;
}


4、给一个有数字和字母的字符串,让连着的数字和字母对应  1a3bb44a2ac  => 1:a 3:bb 44:a 2:ac

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

    var_dump($number);
    var_dump($alphabet);
    $n = count($number);
    for ($i = 0; $i < $n; $i++) {
        echo $number[$i] . ':' . $alphabet[$i] . '</br>';
    }
}
$str = '1a3bb44a2ac';
number_alphabet($str);//1:a 3:bb 44:a 2:ac


5、写一个函数,要求不使用array_merge完成多个数组的合并。

function array_mer()
{
    $return = [];
    $arrays = func_get_args();
    foreach($arrays as $arr)
    {
        if(is_array($arr))
        {
            foreach($arr as $val)
            {
                $return[] = $val; 
            }
        }
    }
    return $return; 
}


6、php实现长数字相加的函数,保留精度

     思路:将数字的字串形式相加,注意小数与整数部分分开运算

     这里以PHP两个大整数相加为例

function big_integer_add($num1, $num2) {
    $str1   = strval($num1);
    $str2   = strval($num2);
    $len    = strlen($num1) > strlen($num2) ? strlen($num1) : strlen($num2);
    $num1s  = strrev($num1);
    $num2s  = strrev($num2);
    $val    = 0;
    $res    = '';
    for($i = 0; $i < $len; $i++) {
        $num1s[$i] = isset($num1s[$i]) ? $num1s[$i] : 0;
        $num2s[$i] = isset($num2s[$i]) ? $num2s[$i] : 0;
        $tmp       = $num1s[$i] + $num2s[$i] + $val;
        $val    = 0;
        if ($tmp >= 10) {
            $val = 1;
            $tmp = $tmp-10;
        }
        $res = (string)$tmp.$res;
    }
    if ($val == 1) {
        $res = $val.$res;
    }
    return (string)$res;
}

$a =                "111111111111555555";
$b = "666666999999999999999999999999999";
$value = big_integer_add($a,$b);
print_r($value);


7、PHP解决多进程同时写一个文件的问题。

function write($str)
{
    $fp = fopen($file, 'a');
    do 
    {
        usleep(100);
    } while (!flock($fp, LOCK_EX));
    fwrite($fp, $str . PHP_EOL);
    flock($fp, LOCK_UN);
    fclose($fp);
}


8、求n以内的质数

        质数的定义:在大于1的自然数中,除了1和它本身意外,无法被其他自然数整除的数

        思路:1.(质数筛选定理)n不能够被不大于根号n的任何质数整除,则n是一个质数

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

/**
 * 求n内的质数
 * @param int $n 
 * @return array
 */
function getPrime($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;
}

var_dump(getPrime(20));


9、斐波那契数列的递推、递归实现

/**
*    斐波那契数列:1 1 2 3 5 8 13 21 ...
*    
*    需求:求指定位置的数列的值
*    规律:第一个和第二个为1,从第三个开始为前两个数之和.
*/

//递推思想(把要求位置之前的所有值列出来,那么要求的数就可以通过前两个数之和计算出来【使用数组存储】)
function my_recursive($des){
    //判断:如果第一个或者第二个
    if($des == 1 || $des == 2)    return 1;

    //开始计算
    $f[1] = 1;
    $f[2] = 1;//如果想要第一个或者第二个结果,那么刻意直接给出

    for ($i = 3; $i <= $des; $i++) { 
        $f[$i] = $f[$i-1] + $f[$i-2]; 
    }

    //返回最后一个位置的结果
    return $f[$des];
}
echo my_recursive(15);


//递归思想(函数调用自己)
function recursion($n){
    //递归出口
    if($n == 1 || $n == 2)    return 1;

    //递归点:求N的值,与求N-1的值一模一样
    return recursion($n - 1) + recursion($n - 2);
}
echo recursion(15);


10、约瑟夫环问题--猴子找大王

        相关题目:一群猴子排成一圈,按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];
}
var_dump(get_king_mokey(10, 2));


function monkey($m,$n){
    $arr=range(1,$m);
    $i=0;
    while(count($arr)>1){
        if(($i+1)%$n==0){
            unset($arr[$i]);
        }else{
            $arr[]=$arr[$i];
            unset($arr[$i]);
        }
        $i++;
    }
    return $arr[$i];
}
var_dump(monkey(10,4));//5


11、如何快速寻找一个数组里最小的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;
}

$arr = array(1,2,2,6,20,14,32,15,12,20,39,49,95,85,83,1);
var_dump( get_min_array($arr, 5) );


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

/**
 * 二分查找
 * @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($array[$mid] == $value)
        {
            return $mid;
        }
        elseif($array[$mid] > $value)
        {
            $right = $mid - 1;
        }
        else
        {
            $left = $mid + 1;
        }
    }
    return -1;
}
$array = array(1,2,3,4,5,6,7,8,9,10);
var_dump(binary_search($array, count($array), 4));


13、给定一个有序整数序列,找出绝对值最小的元素(二分查找)

        思路:二分查找

/**
 * 获取绝对值最小的元素
 * @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;
        }
    }
    return $arr[$mid];
}

/**
 * 判断符号是否相同
 * @param  int  $a
 * @param  int  $b
 * @return boolean
 */
function is_same_sign($a, $b)
{
    if ($a * $b > 0) {
        return true;
    } else {
        return false;
    }
}
//$array = array(1,2,3,4,5,6,7,8,9,10);
//$array = array(-10,-9,-8,-7,-6,-5,-4,-3,-2,-1);
$array = array(-1,0,2,3,4,6,7,9,10);
var_dump(get_min_abs_value($array));


14、找出有序数组中随机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));


15、编写一个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;
}
$arr = array(-1, 0, 1, 2, 3, 4, -2, 5, 1, 2);
var_dump(max_sum_array($arr));


16、php 统计出两个数组(长度10000)中同时出现过的,并且总出现次数最多的单词 

$arr1 = array(1, "hello", 1, "world", "hello",2,2);
$arr2 = array(1, "hello", 11, "world1", "hello1",2,2);
$arr_count1=array_count_values($arr1);
$arr_count2=array_count_values($arr2);
$arr=array_intersect($arr1,$arr2);

$arr_result=array();
foreach ($arr as $v){
    $arr_result[$v]=$arr_count1[$v]+$arr_count2[$v];
}

asort($arr_result);
var_dump($arr_result);


17、PHP计算两个坐标之间的距离

/**
* 计算两点之间的距离
* @param $lng1 经度1
* @param $lat1 纬度1
* @param $lng2 经度2
* @param $lat2 纬度2
* @param int $unit m,km
* @param int $decimal 位数
* @return float
*/
function getDistance($lng1, $lat1, $lng2, $lat2, $unit = 2, $decimal = 2)
{
    $EARTH_RADIUS = 6370.996; // 地球半径系数
    $PI           = 3.1415926535898;
    $radLat1 = $lat1 * $PI / 180.0;
    $radLat2 = $lat2 * $PI / 180.0;
    $radLng1 = $lng1 * $PI / 180.0;
    $radLng2 = $lng2 * $PI / 180.0;
    $a = $radLat1 - $radLat2;
    $b = $radLng1 - $radLng2;
    $distance = 2 * asin(sqrt(pow(sin($a / 2), 2) + cos($radLat1) * cos($radLat2) * pow(sin($b / 2), 2)));
    $distance = $distance * $EARTH_RADIUS * 1000;
    if ($unit === 2) {
        $distance /= 1000;
    }
    return round($distance, $decimal);
}
// 起点坐标
$lng1 = 118.34593200683594;
$lat1 = 33.9527587890625;

// 终点坐标
$lng2 = 118.301612;
$lat2 = 33.936781;

$distance = getDistance($lng1, $lat1, $lng2, $lat2, 1);
echo $distance . 'm' . PHP_EOL; // 4457.64m
$distance = getDistance($lng1, $lat1, $lng2, $lat2);
echo $distance . 'km' . PHP_EOL; // 4.46km


18、两个有序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);
}


19、给一个有数字和字母的字符串,让连着的数字和字母对应

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


20、PHP实现无限极分类的方式

$array = array(
    array('id' => 1, 'pid' => 0, 'name' => '1级'),
    array('id' => 2, 'pid' => 0, 'name' => '1级'),
    array('id' => 3, 'pid' => 1, 'name' => '2级'),
    array('id' => 4, 'pid' => 2, 'name' => '2级'),
    array('id' => 5, 'pid' => 2, 'name' => '2级'),
    array('id' => 6, 'pid' => 4, 'name' => '3级'),
    array('id' => 7, 'pid' => 4, 'name' => '3级'),
    array('id' => 8, 'pid' => 3, 'name' => '3级'),
    array('id' => 9, 'pid' => 1, 'name' => '2级'),
    array('id' => 10, 'pid' => 8, 'name' => '4级'),
    array('id' => 11, 'pid' => 10, 'name' => '5级'),
    array('id' => 12, 'pid' => 11, 'name' => '6级'),
    //...
);


//递归算法
function getTree($array, $pid =0, $level = 0){
    //声明静态数组,避免递归调用时,多次声明导致数组覆盖
    static $list = [];
    foreach ($array as $key => $value){
        //第一次遍历,找到父节点为根节点的节点 也就是pid=0的节点
        if ($value['pid'] == $pid){
            //父节点为根节点的节点,级别为0,也就是第一级
            $value['level'] = $level;
            //把数组放到list中
            $list[] = $value;
            //把这个节点从数组中移除,减少后续递归消耗
            unset($array[$key]);
            //开始递归,查找父ID为该节点ID的节点,级别则为原级别+1
            getTree($array, $value['id'], $level+1);
        }
    }
    return $list;
}
/**************    调用递归方法后遍历新数组   ****************/
$tree1 = getTree($array);
foreach($tree1 as $val){
    echo str_repeat('--', $val['level']).$val['name'].'<br />';
}


//引用算法
function generateTree($array){
    //第一步 构造数据
    $items = array();
    foreach($array as $value){
        $items[$value['id']] = $value;
    }
    //第二步 遍历数据 生成树状结构
    $tree = array();
    foreach($items as $key => $value){
        if(isset($items[$value['pid']])){
            //存在父级
            /**************    引用了$items[$value['pid']] 所以$items[$value['pid']]改变,$tree的关联的键元素也会发生改变      ****************/
            /**************    看不懂这一步的建议去了解一下引用的原理     ****************/
            $items[$value['pid']]['children'][] = &$items[$key];
        }else{
            //不存在父级的顶级元素才会走到这一步
            /**************    看不懂这一步的建议去了解一下引用的原理     ****************/
            $tree[] = &$items[$key];
        }
    }
    return $tree;
}



$tree2 = generateTree($array);
function ergoTree($arr,$level=0){
    foreach ($arr as $item){
        if(isset($item['children'])){
            echo str_repeat('--', $level).$item['name']."<br>";
            ergoTree($item['children'],$level+1);
        }else{
            echo str_repeat('--', $level).$item['name']."<br>";
        }
    }
}
ergoTree($tree2);




冷暖自知一抹茶ck
请先登录后发表评论
  • 最新评论
  • 总共0条评论