PHP之数据结构和算法

臭大佬 2020-09-08 13:41:47 228
php 
简介 PHP之数据结构和算法

约瑟夫环问题

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


/**
 * Instructions:约瑟夫环问题
 * Author: vijay <1937832819@qq.com>
 * @param int $n 总数
 * @param int $m 倍数
 * @return int 大王叫我来巡山
 */
function Joseph($n, $m): int
{
    $mokey = range(1, $n);
    $i = 0;
    while (count($mokey) > 1) {
        $i += 1;
        $head = array_shift($mokey);//一个个出列最前面的猴子
        if ($i % $m != 0) {
            array_push($mokey, $head);
        }
    }
    return $mokey[0];
}
$n =8;
$m=10;
echo Joseph($n,$m);
//7

冒泡排序

/**
 * Instructions:冒泡排序
 * Author: vijay <1937832819@qq.com>
 * @param array $arr 要排序的数组
 * @return array
 */
function bubbleSort($arr): array
{
    $count = count($arr);
    $big = $count - 1;
    for ($i = 0; $i <= $big; $i++) {
        for ($j = $big; $j > $i; $j--) {
            if ($arr[$j] < $arr[$j - 1]) {
                $max = $arr[$j - 1];
                $arr[$j - 1] = $arr[$j];
                $arr[$j] = $max;
            }
        }
    }
    return $arr;
}

$b = [6, 3, 8, 2, 9, 1];
print_r(bubbleSort($b));
//Array
//(
//    [0] => 1
//    [1] => 2
//    [2] => 3
//    [3] => 6
//    [4] => 8
//    [5] => 9
//)

递归函数

php递归函数有时可以循环替代,建议当不能用循环替代时再用,因为用循环我们更容易理解,更不容易出错。 php递归函数 php支付递归函数,递归函数就是调用自己本身,这些函数特别适用于浏览动态数据结构,例如树和列表。 几乎没有web应用程序要求使用复杂的数据结构。

/**
 * Instructions:递归遍历,实现无限分类
 * Author: vijay <1937832819@qq.com>
 * @param $arr
 * @param int $pid
 * @param int $level
 * @return array
 */
function tree($arr, $pid = 0, $level = 0):array
{
    static $list = [];
    foreach ($arr as $v) {
        //如果是顶级分类,则将其存到$list中,并以此节点为根节点,遍历其子节点
        if ($v['parent_id'] == $pid) {
            $v['level'] = $level;
            $list[] = $v;
            tree($arr, $v['cat_id'], $level + 1);
        }
    }
    return $list;
}

快速排序

/**
 * Instructions:快速排序
 * Author: vijay <1937832819@qq.com>
 * @param array $arr
 * @return array
 */
function getQuickNum(array $arr = []): array
{
    $arr_left = [];
    $arr_right = [];
    $count = count($arr);
    if ($count <= 1) {
        return $arr;
    }
    $b = $arr[0];
    for ($i = 1; $i < $count; $i++) {
        if ($arr[$i] < $b) {
            $arr_left[] = $arr[$i];
        } else {
            $arr_right[] = $arr[$i];
        }
    }
    $arr_left = getQuickNum($arr_left);
    $arr_right = getQuickNum($arr_right);
    return array_merge($arr_left, array($b), $arr_right);
}

$arr = [3, 4, 7, 1, 8, 2];
$res = getQuickNum($arr);
print_r($res);
//Array
//(
//    [0] => 1
//    [1] => 2
//    [2] => 3
//    [3] => 4
//    [4] => 7
//    [5] => 8
//)

二分查找

必须是个有序数组从小大,取数组中间key 从而通过key获取value(中间值) 与要查找的值做对比。如果要查找的值大于中间值,key加1,反之key减1。如果正好相等返回 这个数组下标。

/**
 * Instructions:二分查找
 * Author: vijay <1937832819@qq.com>
 * @param $arr
 * @param $bengin
 * @param $end
 * @param $val
 * @return float|int
 */
function doValue($arr, $bengin, $end, $val)
{
    if ($bengin <= $end) {
        $key = floor(($bengin + $end) / 2);//9
        if ($arr[$key] == $val) {
            return $key;
        } elseif ($arr[$key] < $val) {//4<5
            return doValue($arr, $key + 1, $end, $val);//4--7
        } else {
            return doValue($arr, $bengin, $key - 1, $val);
        }


    } else {
        return -1;
    }
}
$arr = [1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 165];
$bengin = 0;
$end = count($arr);
$val = 14;
$res = doValue($arr, $bengin, $end, $val);
print_r($res);//12

遍历一个文件夹下的所有文件和子文件夹


/**
 * Instructions:遍历一个文件夹下的所有文件和子文件夹
 * Author: vijay <1937832819@qq.com>
 * @param $dir
 * @return array|bool
 */
function my_scandir($dir)
{
    $files = array();
    if (is_dir($dir)) {
        if ($handle = opendir($dir)) {
            $file = readdir($handle);
            while ($file !== false) {
                if ($file != "." && $file != "..") {
                    if (is_dir($dir . "/" . $file)) {
                        $files[$file] = my_scandir($dir . "/" . $file);
                    } else {
                        $files[] = $dir . "/" . $file;
                    }
                }
            }
            closedir($handle);
            return $files;
        }
    }
    return false;
}