基本数据结构算法

本文来自laravel-china

二分查找（数组里查找某个元素）

function bin_sch($array,  $low, $high, $k){   
if ( $low <= $high){   
    $mid =  intval(($low+$high)/2 );   
    if ($array[$mid] ==  $k){   
        return $mid;   
    }elseif ( $k < $array[$mid]){   
        return  bin_sch($array, $low,  $mid-1, $k);   
    }else{   
        return  bin_sch($array, $mid+ 1, $high, $k);   
    }   
}   
return -1;   
}

顺序查找（数组里查找某个元素）

function  seq_sch($array, $n,  $k){   
$array[$n] =  $k;   
for($i=0;  $i<$n; $i++){   
    if( $array[$i]==$k){   
        break;   
    }   
}   
if ($i<$n){   
    return  $i;   
}else{   
    return -1;   
}   
}

线性表的删除（数组中实现）

function delete_array_element($array , $i)  
{  
    $len =  count($array);   
    for ($j= $i; $j<$len; $j ++){  
            $array[$j] = $array [$j+1];  
    }  
    array_pop ($array);  
    return $array ;  
}

冒泡排序（数组排序）

function bubble_sort( $array)  
{  
    $count = count( $array);  
    if ($count <= 0 ) return false;  
    for($i=0 ; $i<$count; $i ++){  
            for($j=$count-1 ; $j>$i; $j--){  
                    if ($array[$j] < $array [$j-1]){  
                             $tmp = $array[$j];  
                             $array[$j] = $array[ $j-1];  
                            $array [$j-1] = $tmp;  
                    }  
            }  
    }  
    return $array;  
}

快速排序（数组排序）

function quick_sort($array ) {  
    if (count($array) <= 1) return  $array;  
    $key = $array [0];  
    $left_arr  = array();  
    $right_arr = array();  
    for ($i= 1; $i<count($array ); $i++){  
            if ($array[ $i] <= $key)  
                    $left_arr [] = $array[$i];  
            else  
                     $right_arr[] = $array[$i ];  
    }  
    $left_arr = quick_sort($left_arr );  
    $right_arr = quick_sort( $right_arr);  
    return array_merge($left_arr , array($key), $right_arr);  
}

字符串长度

function strlen ($str)  
{  
    if ($str == '' ) return 0;  
    $count =  0;  
    while (1){  
            if ( $str[$count] != NULL){  
                     $count++;  
                    continue;  
            }else{  
                    break;  
            }  
    }  
    return $count;  
}

截取子串

function substr($str, $start,  $length=NULL)  
{  
    if ($str== '' || $start>strlen($str )) return;  
    if (($length!=NULL) && ( $start>0) && ($length> strlen($str)-$start)) return;  
    if (( $length!=NULL) && ($start< 0) && ($length>strlen($str )+$start)) return;  
    if ($length ==  NULL) $length = (strlen($str ) - $start);  

    if ($start <  0){  
            for ($i=(strlen( $str)+$start); $i<(strlen ($str)+$start+$length ); $i++) {  
                    $substr .=  $str[$i];  
            }  
    }  
    if ($length  > 0){  
            for ($i= $start; $i<($start+$length ); $i++) {  
                    $substr  .= $str[$i];  
            }  
    }  
    if ( $length < 0){  
            for ($i =$start; $i<(strlen( $str)+$length); $i++) {  
                    $substr .= $str[$i ];  
            }  
    }  
    return $substr;  
}

字符串翻转

function strrev($str)  
{  
    if ($str == '') return 0 ;  
    for ($i=(strlen($str)- 1); $i>=0; $i --){  
            $rev_str .= $str[$i ];  
    }  
    return $rev_str;  
}

字符串比较

function strcmp($s1,  $s2)  
{  
    if (strlen($s1) <  strlen($s2)) return -1 ;  
    if (strlen($s1) > strlen( $s2)) return 1;  
    for ($i =0; $i<strlen($s1 ); $i++){  
            if ($s1[ $i] == $s2[$i]){  
                    continue;  
            }else{  
                    return false;  
            }  
    }  
    return  0;  
}

查找字符串

function  strstr($str, $substr)  
{  
$m = strlen($str);  
$n = strlen($substr );  
if ($m < $n) return false ;  
for ($i=0; $i <=($m-$n+1); $i ++){  
        $sub = substr( $str, $i, $n);  
        if ( strcmp($sub, $substr) ==  0)  return $i;  
}  
return false ;  
}

字符串替换

function str_replace($substr , $newsubstr, $str)  
{  
$m = strlen($str);  
$n = strlen($substr );  
$x = strlen($newsubstr );  
if (strchr($str, $substr ) == false) return false;  
for ( $i=0; $i<=($m- $n+1); $i++){  
         $i = strchr($str,  $substr);  
        $str = str_delete ($str, $i, $n);  
        $str = str_insert($str,  $i, $newstr);  
}  
return $str ;  
}

自实现字符串处理函数

function str_insert($str, $i , $substr)  
{  
    for($j=0 ; $j<$i; $j ++){  
            $startstr .= $str[$j ];  
    }  
    for ($j=$i; $j <strlen($str); $j ++){  
            $laststr .= $str[$j ];  
    }  
    $str = ($startstr . $substr  . $laststr);  
    return $str ;  
}

删除一段字符串

function str_delete($str , $i, $j)  
{  
    for ( $c=0; $c<$i;  $c++){  
            $startstr .= $str [$c];  
    }  
    for ($c=( $i+$j); $c<strlen ($str); $c++){  
            $laststr  .= $str[$c];  
    }  
     $str = ($startstr . $laststr );  
    return $str;  
}

复制字符串

function strcpy($s1, $s2 )  
{  
    if (strlen($s1)==NULL || !isset( $s2)) return;  
    for ($i=0 ; $i<strlen($s1);  $i++){  
            $s2[] = $s1 [$i];  
    }  
    return $s2;  
}

连接字符串

function strcat($s1 , $s2)  
{  
    if (!isset($s1) || !isset( $s2)) return;  
    $newstr = $s1 ;  
    for($i=0; $i <count($s); $i ++){  
            $newstr .= $st[$i ];  
    }  
    return $newsstr;  
}

简单编码函数（与php_decode函数对应）

function php_encode($str)  
{  
if ( $str=='' && strlen( $str)>128) return false;  
for( $i=0; $i<strlen ($str); $i++){  
         $c = ord($str[$i ]);  
        if ($c>31 && $c <107) $c += 20 ;  
        if ($c>106 && $c <127) $c -= 75 ;  
        $word = chr($c );  
        $s .= $word;  
}   
return $s;   
}

简单解码函数（与php_encode函数对应）

function php_decode($str)  
{  
if ( $str=='' && strlen($str )>128) return false;  
for( $i=0; $i<strlen ($str); $i++){  
        $c  = ord($word);  
        if ( $c>106 && $c<127 ) $c = $c-20;  
        if ($c>31 && $c< 107) $c = $c+75 ;  
        $word = chr( $c);  
        $s .= $word ;  
}   
return $s;   
}

简单加密函数（与php_decrypt函数对应）

function php_encrypt($str)  
{  
     $encrypt_key = 'abcdefghijklmnopqrstuvwxyz1234567890';  
     $decrypt_key = 'ngzqtcobmuhelkpdawxfyivrsj2468021359';  
    if ( strlen($str) == 0) return  false;  
    for ($i=0;  $i<strlen($str); $i ++){  
            for ($j=0; $j <strlen($encrypt_key); $j ++){  
                    if ($str[$i] == $encrypt_key [$j]){  
                            $enstr .=  $decrypt_key[$j];  
                            break;  
                    }  
            }  
    }  
    return $enstr;  
}

简单解密函数（与php_encrypt函数对应）

function php_decrypt($str)  
{  
     $encrypt_key = 'abcdefghijklmnopqrstuvwxyz1234567890';  
     $decrypt_key = 'ngzqtcobmuhelkpdawxfyivrsj2468021359';  
    if ( strlen($str) == 0) return  false;  
    for ($i=0;  $i<strlen($str); $i ++){  
            for ($j=0; $j <strlen($decrypt_key); $j ++){  
                    if ($str[$i] == $decrypt_key [$j]){  
                            $enstr .=  $encrypt_key[$j];  
                            break;  
                    }  
            }  
    }  
    return $enstr;  
}

王者编程大赛之四 — 约瑟夫环

约瑟夫环递推实现：https://www.fanhaobai.com/2017/12/2017-ziroom-king-4.html

function josephus($n, $e)
{
    $idx = 0;
    for ($i = 2; $i <= $n; $i ++) {
        $idx = ($idx + $e) % $i;
    }
    return $idx;
}
接收标准输入处理并输出结果：

$input = str_replace(' ', '&', $input);
parse_str($input, $arr);
echo josephus($arr['n'], $arr['e']), PHP_EOL;

阶梯式电费算法

举个栗子，深圳为了推进市民节约用电推出了这样一个用电收费政策，电量使用阶梯式递增的收费计算方式，简单而言、用电越多平均的每度电越贵。(假设用户的每电量为整数，小于1度电则应缴费为0元)
  耗电范围(°) 	电费计算(1元/°)
  1<=x<=10   	        1       
  11<=x<=20 	       1.2       
  21<=x<=50 	       1.4       
51<=x<=100 	       1.8       
101<=x<=300	       2.4       
   301<=x   	        5       

/**
 * 根据用电的度数计算电费
 * @param int $number 用电度数
 * @return float 电费https://learnku.com/articles/24977
 */

function calculate(int $number): float
{
    if ($number <= 0) {
        return 0;
    }
    switch ($number) {
        case 1 <= $number && $number <= 10:
            return $number * 1;
            break;
        case 11 <= $number && $number <= 20:
            return ($number - 10) * 1.2 + calculate(10);
            break;
        case 21 <= $number && $number <= 50:
            return ($number - 20) * 1.4 + calculate(20);
            break;
        case 51 <= $number && $number <= 100:
            return ($number - 50) * 1.8 + calculate(50);
            break;
        case 101 <= $number && $number <= 300:
            return ($number - 100) * 2.2 + calculate(100);
            break;
        default:
            return ($number - 300) * 5 + calculate(300);
            break;
    }
}


function calculate(int $useNum): float
{
    if ($useNum < 1) {
        return 0;
    }
    // 电费价格及其范围的配置定义 | 此梯度可抽出来独立配置
    $degrees = [10, 20, 50, 100, 300];
    $prices  = [1, 1.2, 1.4, 1.8, 2.4, 5];

    // 判断是否达到最贵的价格梯度并计算其价格
    $beyondNum = $useNum - end($degrees);
    $price     = ($beyondNum >= 0 ? $beyondNum : 0) * end($prices);

    // 上一层价格峰值
    $prePeak = 0;
    foreach ($degrees as $key => $value) {
        if ($useNum <= $value) {
            $price += ($useNum - $prePeak) * $prices[$key];
            break;
        }
        $price   += ($value - $prePeak) * $prices[$key];
        $prePeak = $value;
    }
    unset($degrees, $prices, $beyondNum, $prePeak);
    return $price;
}

按照奖品概率分布抽奖

//所有奖品信息
$allPrizes = [
  'jd'    => ['name' => '京东券', 'probability' => 30],
  'film'  => ['name' => '电影票', 'probability' => 10],
  'tb'    => ['name' => '淘宝券', 'probability' => 60],
]
/**
 * 按照概率抽取一个奖品, 返回奖品
 * @param   array      $prizes     所有奖品的probability概率总和应该为100
 * @return  mixed
 */
private function randPrize(array $prizes)
{
    //总概率基数
    $totalProbability = array_sum(array_column(array_values($prizes), 'probability'));
    if (100 !== $totalProbability) {
        throw new Exception('invalid probability config');
    }
    $rand = mt_rand(1, 100);
    $cursor = 0;
    $id = '';
    while(list($key, $item) = each($prizes)) {
        if ($rand > $cursor && $rand <= $cursor + $item['probability']) {
            $id = $key;
            break;
        }
        $cursor += $item['probability'];
    }
    unset($prizes[$id]['probability']);

    return $prizes[$id] + ['id' => $id];
}
https://www.fanhaobai.com/2017/05/draw-by-prob.html

非负元素数组所有元素能组合的最大字符串

[0, 9, 523, 94, 10, 4]，排列组合后值最大数为：9945234100。


/**
 * 比较规则
 * @param   string    $a
 * @param   string    $b
 * @return  int
 */
function cmp($a, $b) {
    if ($a == $b) {
        return 0;
    }
    return $a . $b > $b . $a ? -1 : 1;
}
/**
 * 冒泡排序
 * @param   array    $Arr   待排序数组
 * @return  array
 */
function bubble_sort(array $Arr) {
    $length = count($Arr);
	if ($length < 2) {
        return $Arr;
    }

    for ($i = 1, $change = true; $i <= $length && $change; $i++) {
        $change = false;
        for ($j = $length - 1; $j > $i - 1; $j--) {
            if (cmp($Arr[$j - 1], $Arr[$j]) > 0) {
                $temp = $Arr[$j - 1];
                $Arr[$j - 1] = $Arr[$j];
                $Arr[$j] = $temp;
                $change = true;
            }
        }
    }
    return $Arr;
}

/**
 * 寻找非零元素数组中所有元素排列组合后的最大值
 * @param   array     $Arr        待排序数组
 * @param   string    $method     排序方法
 * @return  mixed
 */
function array_form_max_str(array $Arr, $method = 'bubble') {
    //参数校验
    if (!is_array($Arr)) return false;
    foreach ($Arr as $value) {
        if ($value < 0) return false;
    }
    //排序算法
    switch ($method) {
        case 'quick' :
            usort($Arr, "cmp");           //快速排序
            break;
        case 'bubble' :
            $Arr = bubble_sort($Arr);     //冒泡排序
            break;
        default : break;
    }
    //拼接
    return implode('', $Arr);
}
$Arr = [20,913,223,91,20,3];
echo '数组为[', implode(',', $Arr), ']', PHP_EOL;
echo '最大排列组合为：', array_form_max_str($Arr), PHP_EOL;

https://www.fanhaobai.com/2017/04/array-form-max-string.html

PHP生成随机红包算法

原文：比如要把 1 个红包分给 N 个人，实际上就是相当于要得到 N 个百分比数据 条件是这 N 个百分比之和 = 100/100。这 N 个百分比的平均值是 1/N。 并且这 N 个百分比数据符合一种正态分布（多数值比较靠近平均值）。
解读：比如我有 1000 块钱，发 50 个红包，就先随机出 50 个数，然后算出这 50 个数的均值 avg，用 avg/(1/N)，就得到了一个基数 mixrand ，然后用随机出的那 50 个数分别去除以 mixrand ，得到每个数相对基数的百分比 randVal ，然后用 randVal 乘以 1000 块钱，就可以得到每个红包的具体金额了。
https://www.fanhaobai.com/2017/02/reward.html
class Reward
{
    public $rewardMoney;        #红包金额、单位元
    public $rewardNum;          #红包数量

    #执行红包生成算法
    public function splitReward($rewardMoney, $rewardNum, $max, $min)
    {
        #传入红包金额和数量，因为小数在计算过程中会出现很大误差，所以我们直接把金额放大100倍，后面的计算全部用整数进行
        $min = $min * 100;
        $max = $max * 100;
        #预留出一部分钱作为误差补偿，保证每个红包至少有一个最小值
        $this->rewardMoney = $rewardMoney * 100 - $rewardNum * $min;
        $this->rewardNum = $rewardNum;
        #计算出发出红包的平均概率值、精确到小数4位。
        $avgRand = 1 / $this->rewardNum;
        $randArr = array();
        #定义生成的数据总合sum
        $sum = 0;
        $t_count = 0;
        while ($t_count < $rewardNum) {
            #随机产出四个区间的额度
            $c = rand(1, 100);
            if ($c < 15) {
                $t = round(sqrt(mt_rand(1, 1500)));
            } else if ($c < 65) {
                $t = round(sqrt(mt_rand(1500, 6500)));
            } else if ($c < 95) {
                $t = round(sqrt(mt_rand(6500, 9500)));
            } else {
                $t = round(sqrt(mt_rand(9500, 10000)));
            }
            ++$t_count;
            $sum += $t;
            $randArr[] = $t;
        }

        #计算当前生成的随机数的平均值，保留4位小数
        $randAll = round($sum / $rewardNum, 4);

        #为将生成的随机数的平均值变成我们要的1/N，计算一下每个随机数要除以的总基数mixrand。此处可以约等处理，产生的误差后边会找齐
        #总基数 = 均值/平均概率
        $mixrand = round($randAll / $avgRand, 4);

        #对每一个随机数进行处理，并乘以总金额数来得出这个红包的金额。
        $rewardArr = array();
        foreach ($randArr as $key => $randVal) {
            #单个红包所占比例randVal
            $randVal = round($randVal / $mixrand, 4);
            #算出单个红包金额
            $single = floor($this->rewardMoney * $randVal);
            #小于最小值直接给最小值
            if ($single < $min) {
                $single += $min;
            }
            #大于最大值直接给最大值
            if ($single > $max) {
                $single = $max;
            }
            #将红包放入结果数组
            $rewardArr[] = $single;
        }

        #对比红包总数的差异、将差值放在第一个红包上
        $rewardAll = array_sum($rewardArr);
        #此处应使用真正的总金额rewardMoney，$rewardArr[0]可能小于0
        $rewardArr[0] = $rewardMoney * 100 - ($rewardAll - $rewardArr[0]);
        #第一个红包小于0时,做修正
        if ($rewardArr[0] < 0) {
            rsort($rewardArr);
            $this->add($rewardArr, $min);
        }

        rsort($rewardArr);
        #随机生成的最大值大于指定最大值
        if ($rewardArr[0] > $max) {
            #差额
            $diff = 0;
            foreach ($rewardArr as $k => &$v) {
                if ($v > $max) {
                    $diff += $v - $max;
                    $v = $max;
                } else {
                    break;
                }
            }
            $transfer = round($diff / ($this->rewardNum - $k + 1));
            $this->diff($diff, $rewardArr, $max, $min, $transfer, $k);
        }
        return $rewardArr;
    }

    #处理所有超过最大值的红包
    public function diff($diff, &$rewardArr, $max, $min, $transfer, $k)
    {
        #将多余的钱均摊给小于最大值的红包
        for ($i = $k; $i < $this->rewardNum; $i++) {
            #造随机值
            if ($transfer > $min * 20) {
                $aa = rand($min, $min * 20);
                if ($i % 2) {
                    $transfer += $aa;
                } else {
                    $transfer -= $aa;
                }
            }
            if ($rewardArr[$i] + $transfer > $max) continue;
            if ($diff - $transfer < 0) {
                $rewardArr[$i] += $diff;
                $diff = 0;
                break;
            }
            $rewardArr[$i] += $transfer;
            $diff -= $transfer;
        }
        if ($diff > 0) {
            $i++;
            $this->diff($diff, $rewardArr, $max, $min, $transfer, $k);
        }
    }

    #第一个红包小于0,从大红包上往下减
    public function add(&$rewardArr, $min)
    {
        foreach ($rewardArr as &$re) {
            $dev = floor($re / $min);
            if ($dev > 2) {
                $transfer = $min * floor($dev / 2);
                $re -= $transfer;
                $rewardArr[$this->rewardNum - 1] += $transfer;
            } elseif ($dev == 2) {
                $re -= $min;
                $rewardArr[$this->rewardNum - 1] += $min;
            } else {
                break;
            }
        }
        if ($rewardArr[$this->rewardNum - 1] > $min || $rewardArr[$this->rewardNum - 1] == $min) {
            return;
        } else {
            $this->add($rewardArr, $min);
        }
    }
}
//https://github.com/xxlufei/reward

复杂度

sum = n*(n+1)/2;        //时间复杂度O(1)

for(int i = 0; i < n; i++){
    printf("%d ",i);
}                       
//时间复杂度O(n)

for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
        printf("%d ",i);
    }
}               
//时间复杂度O(n^2)

for(int i = 0; i < n; i++){
    for(int j = i; j < n; j++){
        printf("%d ",i);
    }
}   
//运行次数为(1+n)*n/2
//时间复杂度O(n^2)
int i = 0, n = 100;
while(i < n){
    i = i * 2;
}
//设执行次数为x. 2^x = n 即x = log2n
//时间复杂度O(log2n)
常用排序算法的时间复杂度https://learnku.com/articles/25297

算法	最差时间分析	平均时间复杂度	稳定度	空间复杂度
冒泡排序	O(n2)	O(n2)	稳定	O(1)
快速排序	O(n2)	O(n*log2n)	不稳定	O(log2n)~O(n)
选择排序	O(n2)	O(n2)	稳定	O(1)
二叉树排序	O(n2)	O(n*log2n)	不稳定	O(n)
插入排序	O(n2)	O(n2)	稳定	O(1)
堆排序	O(n*log2n)	O(n*log2n)	不稳定	O(1)
希尔排序	O	O	不稳定	O(1)

快速排序

public static function quick($arr){
        if(count($arr)<=1){ //如果数组根本就一个元素就直接返回 不用在排序咯https://learnku.com/articles/25865
            return $arr;
        }

        $k=$arr[0];//定义一个初始要排序的值 默认为数组第一个
        $x=array();//定义比要排序的值 小的数组块
        $y=array();//定义比要排序的值 大的数组块
        $_size=count($arr);//统计数组的大小
        for($i=1;$i<$_size;$i++){//循环数组 记住这边要从索引1 开始
            if($arr[$i]<=$k){//如果当前的值小于 要排序的值
                $x[]=$arr[$i];//就把小于的值放到 小的数组块中
            }elseif($arr[$i]>$k){//如果当前的值大于 要排序的值
                $y[]=$arr[$i];//就把大于的值放到 大的数组块中
            }
        }
        $x=Sort::quick($x);//依次递归执行 这样就会得到小的数组块
        $y=Sort::quick($y);//依次递归执行 这样就会得到大的数组块
        return array_merge($x,array($k),$y);//最后在合并下 小的模块+中间的模块【初始要排序的值】+大的模块 就ok~
    }
    // print_r(Sort::quick($arr));

雪花算法

最高位是符号位，始终为0，不可用
接下来的41位为毫秒级时间(41位的长度可以使用69年)
然后是5位datacenterId和5位workerId(10位的长度最多支持部署1024个节点）
最后12位是毫秒内的计数（12位的计数顺序号支持每个节点每毫秒产生4096个ID序号）
一共加起来刚好64位，为一个Long型。(转换成字符串后长度最多19)

snowflake生成的ID整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞（由datacenter和workerId作区分），并且效率较高。经测试snowflake每秒能够产生26万个ID。
class SnowFlake{
    public function createID(){
        //假设一个机器idhttps://ctexthuang.com/archives/6/
        $machineId = 1234567890;

        //41bit timestamp(毫秒)
        $time = floor(microtime(true) * 1000);

        //0bit 未使用
        $suffix = 0;

        //datacenterId  添加数据的时间
        $base = decbin(pow(2,40) - 1 + $time);

        //workerId  机器ID
        $machineid = decbin(pow(2,9) - 1 + $machineId);

        //毫秒类的计数
        $random = mt_rand(1, pow(2,11)-1);

        $random = decbin(pow(2,11)-1 + $random);         
        //拼装所有数据
        $base64 = $suffix.$base.$machineid.$random;
        //将二进制转换int
        $base64 = bindec($base64);

        $id = sprintf('%.0f', $base64);

        return $id;
    }
}

namespace EasySwoole\Core\Utility;

/**
 * 雪花算法生成器
 * Class SnowFlake
 * @author : evalor <master@evalor.cn>
 * @package EasySwoole\Core\Utility
 */
class SnowFlake
{
    private static $lastTimestamp = 0;
    private static $lastSequence  = 0;
    private static $sequenceMask  = 4095;
    private static $twepoch       = 1508945092000;

    /**
     * 生成基于雪花算法的随机编号
     * @author : evalor <master@evalor.cn>
     * @param int $dataCenterID 数据中心ID 0-31
     * @param int $workerID 任务进程ID 0-31
     * @return int 分布式ID
     */
    static function make($dataCenterID = 0, $workerID = 0)
    {
        // 41bit timestamp + 5bit dataCenter + 5bit worker + 12bit

        $timestamp = self::timeGen();

        if (self::$lastTimestamp == $timestamp) {
            self::$lastSequence = (self::$lastSequence + 1) & self::$sequenceMask;
            if (self::$lastSequence == 0) $timestamp = self::tilNextMillis(self::$lastTimestamp);
        } else {
            self::$lastSequence = 0;
        }
        self::$lastTimestamp = $timestamp;

        $snowFlakeId = (($timestamp - self::$twepoch) << 22) | ($dataCenterID << 17) | ($workerID << 12) | self::$lastSequence;
        return $snowFlakeId;
    }

    /**
     * 反向解析雪花算法生成的编号
     * @author : evalor <master@evalor.cn>
     * @param int|float $snowFlakeId
     * @return \stdClass
     */
    static function unmake($snowFlakeId)
    {
        $Binary               = str_pad(decbin($snowFlakeId), 64, '0', STR_PAD_LEFT);
        $Object               = new \stdClass;
        $Object->timestamp    = bindec(substr($Binary, 0, 41)) + self::$twepoch;
        $Object->dataCenterID = bindec(substr($Binary, 42, 5));
        $Object->workerID     = bindec(substr($Binary, 47, 5));
        $Object->sequence     = bindec(substr($Binary, -12));
        return $Object;
    }

    /**
     * 等待下一毫秒的时间戳
     * @author : evalor <master@evalor.cn>
     * @param $lastTimestamp
     * @return float
     */
    private static function tilNextMillis($lastTimestamp)
    {
        $timestamp = self::timeGen();
        while ($timestamp <= $lastTimestamp) {
            $timestamp = self::timeGen();
        }
        return $timestamp;
    }

    /**
     * 获取毫秒级时间戳https://www.libenfu.com/index.php/archives/302/
     * @author : evalor <master@evalor.cn>
     * @return float
     */
    private static function timeGen()
    {
        return (float)sprintf('%.0f', microtime(true) * 1000);
    }
}
1bit正负标识位 - 41bits毫秒级时间戳 - 5bits数据中心id - 5bits机器id -12bits毫秒内顺序id
composer require wantp/snowflake
https://github.com/wantp/snowflake
 /**
     * 分布式 id 生成类     组成: <毫秒级时间戳+机器id+序列号>
     * 默认情况下41bit的时间戳可以支持该算法使用到2082年，10bit的工作机器id可以支持1023台机器，
      *序列号支持1毫秒产生4095个自增序列id
     * @author zhangqi
     */
    class IdCreate
    {
      const EPOCH = 1479533469598; //开始时间,固定一个小于当前时间的毫秒数\
      const max12bit = 4095;
      const max41bit = 1099511627775;

      static $machineId = null; // 机器id

      public static function machineId($mId = 0)
      {
             self::$machineId = $mId;
      }
      public static function createOnlyId()
     {
         // 时间戳 42字节
         $time = floor(microtime(true) * 1000);
          // 当前时间 与 开始时间 差值
        $time -= self::EPOCH;
        // 二进制的 毫秒级时间戳
        $base = decbin(self::max41bit + $time);
        // 机器id  10 字节
           if (!self::$machineId) {
                   $machineid = self::$machineId;
             } else {
                    $machineid = str_pad(decbin(self::$machineId), 10, "0", STR_PAD_LEFT);\
              }
             // 序列数 12字节
              $random = str_pad(decbin(mt_rand(0, self::max12bit)), 12, "0", STR_PAD_LEFT);\
              // 拼接
              $base = $base . $machineid . $random;
              // 转化为 十进制 返回
              return bindec($base);
             }
    }

    调用  IdCreate::createOnlyId(1);
           返回的值   // 2219944901359
           返回的值 // 2220004015923
           返回的值 // 2220062766757
           返回的值     // 2220119764908

时间复杂度

//https://learnku.com/laravel/t/28462
执行次数 T (n) 是关于问题规模 n 的函数
常数阶

复杂度为 O (1)

线性阶

int i;
for(i = 0 ; i < n ; i++){
    //代码
}
复杂度为 O (n)

对数阶

int count = 1;
while(count < n){
  count = count * 2;
  //代码  
}
数学公式：2x = n --> x = log2n

因此这个循环的时间复杂度为 O (logn)

平方阶

类型 1：n*n

int i;
for(i = 0 ; i < n ; i++){
   for(j = 0 ; j < n ; j++){
    //代码   
   }    
}
时间复杂度为 O (n^2^)。

类型 2：n*m

如果内层循环改成了 m 次，时间复杂度就为 O (n*m)


int i;
for(i = 0 ; i < n ; i++){
   for(j = 0 ; j < m ; j++){
    /*时间复杂度为O(1)的程序*/  
    }    
}
类型 3：特殊 n*n

再来看一段程序，当内层循环 j = i 时

int i;
for(i = 0 ; i < n ; i++){
   for(j = i ; j < n ; j++){
    /*时间复杂度为O(1)的程序*/  
    }    
}
i = 0 时，内层循环执行了 n 次，

i = 1 时，执行了 n-1 次，

i = n-1 时，执行了 1 次，所以总的执行次数为：

n+(n-1)+(n-1)+...+1 = n(n+1)/2 = n^2^/2 + n/2

根据大 O 推导方法，保留最高阶项，n^2^/2 ，然后去掉这个项相乘的常数，1/2

因此，这段代码的时间复杂度为 O (n^2^)

类型 4：斐波那契数列

long aFunc(int n) {
    if (n <= 1) {
        return 1;
    } else {
        return aFunc(n - 1) + aFunc(n - 2);
    }
}
显然运行次数，T (0) = T (1) = 1，同时 T (n) = T (n - 1) + T (n - 2) + 1，这里的 1 是其中的加法算一次执行。

通过归纳证明法可以证明，当 n >= 1 时 T (n) < (5/3)^n^，同时当 n > 4 时 T (n) >= (3/2)^n。

简化后为 O (2^n^)

常见的时间复杂度

执行次数函数	阶	术语描述
12	O(1)	常数阶
2n+3	O(n)	线性阶
3n^2^+2n+1	O(n^2^)	平方阶
5log2^n^+20	O(log2^n^)	对数阶
2n+3nlog2^n^+19	O(nlogn)	nlog2^n^ 阶
6n^3^+2n^2^+3n+4	O(n3)	立方阶
2n	O(2n)	指数阶
时间复杂度所耗费的时间是：

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2^) < O(n^3^) <O(2^n^) < O(n!) <O(n^n^)

排序

//测试调用
public function aa(){
    $ad = [12,5,644,64,6546,54,54,897,321,231,54,321,56];
    $res = $this->InsertSort($ad);
    return $res;
}

/**
 *@func 插入排序
 * @describe 算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。
 * 插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，
 * 但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。
 * 在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
 *
 * @author vio
 **/
private function InsertSort(array $arr=[]){
    $count = count($arr);
    for($i=1;$i<$count;$i++){
        $t = $arr[$i];
        $j = $i-1;
        while ($j>=0 && $arr[$j]>$t){
            $arr[$j+1] = $arr[$j];
            $j--;
        }
        if ($i!=$j+1){
            $arr[$j+1] = $t;
        }
    }
    return $arr;
}

/**
 *@func 选择排序
 * @O    O(n^2)
 * @describe 遍历数组，将数组中最小的值换到第一个，然后再遍历数组，将第二小的值换到数组的第二个位置，以此类推
 * @author vio
 **/
private function SelectSort(array $arr=[]){
    $count = count($arr);
    for($i=0;$i<$count;$i++){
        $k = $i;
        for($j=$i+1;$j<$count;$j++){
            if ($arr[$j]<$arr[$k]){
                $k = $j;
            }
        }
        if ($k!=$i){
            $t = $arr[$k];
            $arr[$k] = $arr[$i];
            $arr[$i] = $t;
        }
    }
    return $arr;
}

/**
 *@func 冒泡排序
 * @describe 将数组的每一个数与其后的每一个数比较，如果这个数大于他后面的数，则交换位置
 * @author vio
 **/
private function BubbleSort(array $arr=[]){
    $count = count($arr);
    for($i=0;$i<$count-1;$i++){
        for ($j=$i;$j<$count;$j++){
            if($arr[$i]>$arr[$j]){
                $t = $arr[$i];
                $arr[$i] = $arr[$j];
                $arr[$j] = $t;
            }
        }
    }
    return $arr;
}

/**
 *@func 快速排序
 * @O    O(nlogn) 最糟 O(n^2)
 * @describe 从数组中选一个基准点，遍历数组，大于基准点的放到一个数组，其余放到另一个数组。
 *      递归的对子数组排序
 * @author vio
**/
private function QuickSort(array $arr=[]){
    $count = count($arr);
    if ($count<=1){
        return $arr;
    }
    $pivot = $arr[0];
    $left = $right = [];
    for($i=1;$i<$count;$i++){
        if($arr[$i]<$pivot){
            array_push($left,$arr[$i]);
        }else{
            array_push($right,$arr[$i]);
        }
    }
    $left = $this->QuickSort($left);
    $right = $this->QuickSort($right);
    return array_merge($left,[$pivot],$right);
}

两数之和

给定 $nums = [2, 7, 11, 15], $target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
function twoSum($nums, $target) {
    foreach($nums as $k=>$v){
        $an = $target - $nums[$k];
        unset($nums[$k]);
        $res = array_search($an,$nums);
            if($res !== false){
                return [$k,$res];
            }
    }
}
$arr = twoSum($nums,$target);
print_r($arr);
 function twoSum($nums, $target) {
        $res = [];
        foreach($nums as $k => $v) {
            $diff = $target - $v;
            if(in_array($diff, $nums)) {
                $diff_key = array_search($diff, $nums);
                if($diff_key !== $k) {
                    $res = [$k, $diff_key];
                    break;
                }
            }
        }
        return $res;
    }
    
    function twosum（$nums，$target）{
    $count=count（$nums）；
    for（$K=0；k<$count；$k++）{
    for（$i=0；$i<$count；$i++）{
    if（$k<$i&&$nums[$i]+$nums[$k]==$target）{
    return[$k，$i]；
    }}
    return[]；
    
    function twosum（$nums，$target）{
    $numsMatches=[]；
    foreach（$nums as $k=>$v）{
    $numsMatches[$target-$v]=$k;
    }
    foreach（$nums as k=>$v）{
    if（isset（$numsMatches[$v]）&& $K!=$numsMatches[$v]）{
    return[$k，$numsMatches[$v]]；
    }
    return[]；
    
    https://learnku.com/articles/31920 https://learnku.com/php/tweets/31775

索引顺序查找

class Index{
    public $key;//索引块表中的最大值
    public $start;//索引块表中的起始地址
}

function cmp(Index $a,Index $b)
{
    if ($a->key==$b->start){
        return 0;
    }
    return $a->key>$b->key?1:-1;
}
/**
从索引表中检索，再从数据集合里检索数据
**/
function search($key,$data=[],$index=[]):int
{
    $i=0;
    while($i<3&&$key>$index[$i]->key){//索引表中检索获取某块
        $i++;
    }
    if ($i>=3){
        return -1;
    }
    $startValue = $index[$i]->start;//获取某块起始地址
    while($startValue<=$startValue+5&&$data[$startValue]!=$key){//从查找表指定范围检索
        $startValue++;
    }
    if ($startValue>$startValue+5){
        return -1;
    }
    return $startValue;
}

(function(){

    //查找表【数据集合】
    $data = [54,53,52,51,50,55, 44,46,48,49,43,41, 84,83,65,74,98,100];
    //索引块表
    $index = [];
    $j=-1;
    $indexObj = new Index();
    for($i=0;$i<3;$i++){//数据分块处理
        $obj = clone $indexObj;
        $obj->start=$j+1;
        $j+=6;
        $index[$i] = $obj;
        for ($k=$index[$i]->start;$k<=$j;$k++)
        {
            if ($index[$i]->key<$data[$k]){
                $index[$i]->key = $data[$k];
            }
        }
    }
    usort($index,'cmp');
    $key = fgets(STDIN,10);
    $location = search(intval($key),$data,$index);
    if ($location>=0){
        fwrite(STDOUT,"ok find elem ".$location);
    }else{
        fwrite(STDERR,"not found!");
    }

})();
https://learnku.com/articles/31876

数据结构栈和队列排队算法

栈也是一种特殊的线性表结构，数据只能在某一端进行操作，能操作数据的那一端为栈顶，对应的为栈底，数据入栈的过程就是入栈【压栈，进栈】，数据出栈的过程就是【弹栈，出栈】，遵循先进后出原则 FIRST IN LAST OUT 即 FILO 结构，基于连续的内存单元则是顺序栈表，一种是使用分散的内存单元存储为链式结构即链栈结构。
/**
 * 队列+栈数据结构的停车排队管理系统
 */
define("MAXSIZE",3);
$station   = [];//停车场栈
$parkTop   = 0;
$road      = [];//便道队列
$roadFront = $roadNear = 0;//队列游标

class Car
{
    public $carNumber;
    public $arriveTime;
}

/**
 * 压栈
 * @param $station
 * @param $parkTop
 * @param Car $car
 * @return int
 */
function push(&$station,&$parkTop,Car $car)
{
    if ($parkTop>=MAXSIZE){
        echo "停车场没有位置了哦".PHP_EOL;
        return -1;
    }
    $station[$parkTop] = $car;
    echo "车牌号为:".$car->carNumber."的车主停车位为：".($parkTop+1).PHP_EOL;
    $parkTop++;
    return 1;
}

/**
 * 出栈
 * @param $station
 * @param $parkTop
 * @param $carNumber
 * @return Car
 */
function pop(&$station,&$parkTop,$carNumber)
{
    $location        = -1;
    $tempStation     = [];//临时栈
    $tempLocation    = 0;
    $car             = new Car();
    $car->carNumber  = -1;
    $car->arriveTime = -1;
    for($i=0;$i<$parkTop;$i++){
        if ($station[$i]->carNumber==$carNumber){
            $location=$i;
            break;
        }
    }
    if ($location==-1){
        echo "停车场没有这车";
    }else{
        while($parkTop>$location+1){
            $parkTop--;
            $tempStation[$tempLocation] = $station[$parkTop];
            $tempLocation++;
        }
        $parkTop--;
        $car = $station[$parkTop];
        while($tempLocation>0){
            $tempLocation--;
            $station[$parkTop] = $tempStation[$tempLocation];
            $parkTop++;
        }
    }
    return $car;
}
echo "欢迎使用停车位管理系统".PHP_EOL;
echo date("Y年-m月-d日 H时:i分:s秒").PHP_EOL;
while(1){

    echo "停车(A;离开(D;是否有空位(E;停车场车辆列表(L;退出#".PHP_EOL;
    $cmd = fread(STDIN,1);
    if ($cmd=='#'){
        echo "欢迎下次再来".PHP_EOL;
        break;
    }
    switch (trim($cmd)){
        case 'L':
            if ($parkTop>0){
                echo "|---车牌号---|---停车时间---|---车 位---|---区域---|".PHP_EOL;
                for($j=$parkTop-1;$j>=0;$j--){
                    echo "|---".$station[$j]->carNumber."---|---".$station[$j]->arriveTime.":00:00---|---".($j+1).' 号---|---车场---|'.PHP_EOL;
                }
            }
            if ($roadFront!=$roadNear){
                for($j=$roadFront;$j<$roadNear;$j++){
                    echo "|---".$road[$j]->carNumber."---|---".$road[$j]->arriveTime.":00:00---|---".($j+1).' 号---|---便道---|'.PHP_EOL;
                }
            }

            break;
        case "A":
            echo "请输入车牌号和到达时间".PHP_EOL;
            $input = trim(fread(STDIN,10));
            fflush(STDIN);
            if (strpos($input,":")<-1){
                echo "输入错误".PHP_EOL;
                break;
            }
            $input = explode(":",$input);
            if (count($input)<2){
                echo "车牌号和时间输入错误".PHP_EOL;
                break;
            }

            $carNumber = $input[0];
            $arriveTime= (integer)$input[1];
            if (empty($arriveTime)){
                echo "时间输入错误".PHP_EOL;
                break;
            }
            $car = new Car();
            $car->carNumber = $carNumber;
            $car->arriveTime = $arriveTime;
            $result = push($station,$parkTop,$car);
            if ($result==-1){
                $road[$roadNear] = $car;
                $roadNear++;
                echo "车牌为号：".$car->carNumber."的车停在了便道上的:".$roadNear."，位置上了".PHP_EOL;
            }
            break;
        case "E":
            if ($parkTop>=MAXSIZE){
                echo "目前没有空位了，进来只能停在便道上了".PHP_EOL;
            }else{
                echo "有空位，停车费一个小时20美金".PHP_EOL;
            }
            break;
        case "D":
            echo "请输入要离开的车牌号和离开时间".PHP_EOL;
            $input = trim(fread(STDIN,10));
            fflush(STDIN);
            if (strpos($input,":")<-1){
                echo "输入错误".PHP_EOL;
                break;
            }
            $input = explode(":",$input);
            if (count($input)<2){
                echo "输入错误".PHP_EOL;
                break;
            }
            $carNumber = $input[0];
            $arriveTime = $input[1];
            if (empty($arriveTime)){
                echo "输入错误".PHP_EOL;
                break;
            }
            /** @var Car $car */
            $car = pop($station,$parkTop,$carNumber);
            if ($car->carNumber==-1){
                echo "停车场没有你要找的车".PHP_EOL;
            }else{
                $time = $arriveTime-$car->arriveTime;
                echo "车牌号为:".$car->carNumber."的停车时间为：".$time."H,需要缴纳:".($time*20)."美金停车费用".PHP_EOL;
                echo "车牌号为:".$car->carNumber."的车已经出来，停在便道上的车将进场".PHP_EOL;
                if ($roadFront!=$roadNear){
                    $car = $road[$roadFront];
                    echo "车牌号为：".$car->carNumber."的车请输入到达时间".PHP_EOL;
                    $arriveTime = trim(fread(STDIN,5));
                    $car->arriveTime = $arriveTime;
                    $station[$parkTop] = $car;
                    $parkTop++;
                    $roadFront++;
                    echo "停在便道上的车牌为：".$car->carNumber."已经进入停车场了".PHP_EOL;
                }

            }
            break;
        default:
            break;
    }
}https://learnku.com/articles/30492

队列数据结构

define('MAXSIZE',5);//队列空间大小
/**
 * @param $queue 队列存储空间
 * @param $front 队列队头游标
 * @param $near  队列队尾游标
 * @param $data  进队的数据
 * @return int
 */
function enQueue(&$queue,$front,$near,$data)
{
    if (($near+1)%MAXSIZE==$front){
        throw new RuntimeException("队空间已满");
    }
    $queue[$near%MAXSIZE] = $data;
    $near+=1;
    return $near;
}

/**
 * 出队操作
 * @param $queue
 * @param $front
 * @param $near
 * @return int
 */
function deQueue(&$queue,$front,$near)
{
    if ($front==$near%MAXSIZE){
        throw new RuntimeException("空队列");
    }
    $data = $queue[$front];
    echo "出队元素：".$data.PHP_EOL;
    $front = ($front+1)%MAXSIZE;
    return $front;
}
$a = [];//队列 使用数组模拟
$front = $near = 0;//游标初始化
$near = enQueue($a,$front,$near,1);
$near = enQueue($a,$front,$near,2);
$near = enQueue($a,$front,$near,3);

$front = deQueue($a,$front,$near);
$front = deQueue($a,$front,$near);
$front = deQueue($a,$front,$near);
//$front = deQueue($a,$front,$near);

$near = enQueue($a,$front,$near,100);
$front = deQueue($a,$front,$near);

$near = enQueue($a,$front,$near,1);
$near = enQueue($a,$front,$near,2);
$near = enQueue($a,$front,$near,3);
$near = enQueue($a,$front,$near,4);
$front = deQueue($a,$front,$near);
$front = deQueue($a,$front,$near);
$front = deQueue($a,$front,$near);
$front = deQueue($a,$front,$near);
https://learnku.com/articles/30430

二分查找

class Elem{
    public $key;
}

class Table
{
    public $data = [];
    public $lenght;
}
function createTable(Table &$table,$length)
{
    $table->lenght = $length;
    $obj = new Elem();
    fwrite(STDOUT,"请输入数据：\n");
    for($i=1;$i<=$table->lenght;$i++){
        $elem = clone $obj;
        $elem->key = fgets(STDIN,10);
        $table->data[$i] = $elem;
    }
}

function searchBin(Table $table,$key):int
{
    $low = 1;
    $height = $table->lenght;
    while($low<=$height){
        $mid = floor(($low+intval($height))/2);
        if ($table->data[$mid]->key==$key){
            return $mid;
        }else if($table->data[$mid]->key>$key){
            $height=$mid-1;
        }else{
            $low = $mid+1;
        }
    }
    return 0;
}
(function(){
    $table = new Table();
    fwrite(STDOUT,"请输入数据元素个数：\n");
    $length = fgets(STDIN,10);
    createTable($table,$length);
    fwrite(STDOUT,"请输入要查找的数据元素：\n");
    $key = (integer)fgets(STDIN,10);
    $location = searchBin($table,$key);
    if ($location){
        fwrite(STDOUT,"查找到的数据索引为：$location\n");
    }else{
        fwrite(STDERR,"查找不到指定的内容\n");
    }
})();https://learnku.com/articles/31829

约瑟夫环

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

    function king($n, $m){
        //创建1到n数组
        $monkeys = range(1, $n);
        $i=0;
        //循环条件为猴子数量大于1
        while (count($monkeys)>1) {
            //$i为数组下标;$i+1为猴子标号
            if(($i+1)%$m==0) {
                //余数等于0表示正好第m个，删除，用unset删除保持下标关系
                unset($monkeys[$i]);
            } else {
                //如果余数不等于0，则把数组下标为$i的放最后，形成一个圆形结构
                array_push($monkeys,$monkeys[$i]);

                unset($monkeys[$i]);
            }
            //$i 循环+1，不断把猴子删除，或 push到数组
            $i++;
        }
        //猴子数量等于1时输出猴子标号，得出猴王
        return current($monkeys);
    }
    echo king(6,3);
range(m,n) 创建一个包含从 "m" 到 "n" 之间的元素范围的数组
range(1, 5);
// [0=>1, 1=>2, 2=>3, 3=>4, 4=>5];
unset(...$str) 销毁给定的变量
$array=[1,2,3,4,5];
unset($array[2]);
// [0=>1, 1=>2, 3=>4, 4=>5];
array_push($array, ...$str) 向数组尾部插入变量
$array=[1, 2];
array_push($array, 3, 4);
// [1, 2, 3, 4 ];
current() 输出数组中的当前元素的值
end() - 将内部指针指向数组中的最后一个元素，并输出
next() - 将内部指针指向数组中的下一个元素，并输出
prev() - 将内部指针指向数组中的上一个元素，并输出
reset() - 将内部指针指向数组中的第一个元素，并输出
each() - 返回当前元素的键名和键值，并将内部指针向前移动 
https://learnku.com/articles/33253

TwoSum

func TwoSum1(nums []int, target int) []int {
    len := len(nums)

    for i := 0; i < len; i++ {
        for j := i + 1; j < len; j++ {
            if target == nums[i]+nums[j] {
                return []int{i, j}
            }
        }
    }
    return nil
}
a + b = target 转换成 b = target - a，将值与下标的关系存入map中
func TwoSum2(nums []int, target int) []int {
    aMap := make(map[int]int, len(nums))

    //循环nums 获取 key and value
    for k, v := range nums {
        aMap[v] = k

        if j, ok := aMap[target-v]; ok {
            //从值与键的映射中查询 成功查询说明 j 之前 有值 满足条件  注意：此时 j<k  先建映射再进行查询
            return []int{j, k}
        }
    }

    return nil
}
https://dalebao.github.io/2019/04/13/LeetCode-001-TwoSum/

二分查找

function binarySerach($data, $res)
{
        $left  = 0;
        $right = count($data) - 1;
        while ($left <= $right) {
            $middle = $left + (($right - $left) >> 1);
            if ($data[$middle] == $res) return $middle;
            else if ($data[$middle] > $res) $right = $middle - 1;
            else $left = $middle + 1;
        }
        return -1;
 }
 题目让我们找出重复的数，给定的数组的值都在 1-n 之间，数组总数是 n+1, 那么必然有数字是重复的，让我们来找出这个重复的数。
 这道题可以有更好的解法 (我这里强行把它当做二分的场景)，二分的解题思路就是取 n 的中位数，遍历数组，统计不大于中位数的个数，如果不大于中位数的个数比中位数还大，说明重复的数在中位数的左边 (注意包括中位数自己，理解一下这一句)，否则的话重复的数肯定出现在中位数的右边，而且肯定不包括中位数。好了下面看代码再细讲。
 
 /**
     * @param Integer[] $nums
     * @return Integer
     */
    function findDuplicate($nums) {
        $left = 1;
        $right = count($nums) - 1;
        while ($left < $right) {  // <
            $middle = ($left + $right) >> 1;
            $sum = 0;
            for ($j = 0; $j < count($nums); $j++) {
                if ($nums[$j] <= $middle) {
                    $sum++;
                }
            }
            if ($sum <= $middle) {  //排除掉中位数
                $left = $middle + 1;
            } else {   //不能排除中位数
                 $right = $middle;
            }
        }
        //相返回left还是right都可以  因为必然存在left==right
        return $left;
    }

二分查找法

所谓二分查找，针对的是一个有序的数据集合（这点很重要），查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。注意到二分查找针对的必须是已经排序过的有序数组，否则不能使用该算法。
function binary_search($nums, $num)
    {
        return binary_search_internal($nums, $num, 0, count($nums) - 1);
    }

    function binary_search_internal($nums, $num, $low, $high)
    {
        if ($low > $high) {
            return -1;
        }

        $mid = floor(($low + $high) / 2);
        if ($num > $nums[$mid]) {
            return binary_search_internal($nums, $num, $mid + 1, $high);
        } elseif ($num < $nums[$mid]) {
            return binary_search_internal($nums, $num, $low, $mid - 1);
        } else {
            return $mid;
        }
    }

    $nums = [1, 2, 3, 4, 5, 6];
    $index = binary_search($nums, 5);
    print $index;
    https://learnku.com/articles/37822
    使用二分查找需要注意一个前提，那就是针对有序数组，换言之，二分查找适用于变动不是很频繁的静态序列集，如果序列集变动很频繁，经常进行插入删除操作，那么就要不断维护这个序列集的排序，这个成本也很高，因此，这种情况下就不适用二分查找了，比如我们的数据库查询，增删改查很频繁，显然不是通过二分查找来进行查询的。

对称括号

function isValid($s) {
        $s = str_replace(['()', '[]', '{}'], '', $s, $count);
        if($count == 0){
            return strlen($s)==0;
        }else{
            return $this->isValid($s);
        }
    }
    https://www.debuginn.cn/5081.html  https://github.com/debuginn/Learning-Code-Algorithm

无限级菜单

CREATE TABLE `SuperUserMenus` (
  `id` int(11) NOT NULL AUTO_INCREMENT COMMENT 'ID',
  `pid` int(11) NOT NULL COMMENT '父级ID',
  `order` int(11) NOT NULL DEFAULT '0' COMMENT '菜单排序',
  `title` varchar(100) NOT NULL COMMENT '菜单标题',
  `controller` varchar(100) DEFAULT NULL COMMENT '控制器名称',
  `method` varchar(100) DEFAULT NULL COMMENT '方法名称',
  `ishidden` int(1) NOT NULL DEFAULT '0' COMMENT '是否隐藏：0正常显示，1隐藏',
  `status` int(1) NOT NULL DEFAULT '0' COMMENT '状态：0正常，1禁用',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
public function index()
{
    $Super_id = 1;
    $menus = false;
    $role = Db::table('SuperUser')->where('Super_id', $Super_id)->select();
    $role = $role[0];
    if ($role) {
        $role['rights'] = (isset($role['rights']) && $role['rights']) ? json_decode($role['rights'], true) : [];
    }
    if ($role['rights']) {
        $menus = Db::query('select * from SuperUserMenus where id in(' . implode(',', $role['rights']) . ') and ishidden=0 and status=0');
        $menus = $this->_array_column($menus, null, 'id');
        $menus && $menus = $this->gettreeitems($menus);
    }
    return json_encode($menus);
}
private function gettreeitems($items)
    {
        $tree = array();
        foreach ($items as $item) {
            if (isset($items[$item['pid']])) {
                $items[$item['pid']]['children'][] = &$items[$item['id']];
            } else {
                $tree[] = &$items[$item['id']];
            }
        }
        return $tree;
    }
    https://www.debuginn.cn/4549.html

LeetCode_PHP

二叉树的遍历

两数之和

PHP 排序算法之选择排序

算法图解3 - 递归，快排

LeetCode-Algorithms 算法题 PHP 实现

尝试 leetcode 题目

PHP生成随机红包算法

什么是B-树

数据结构的基本概念

JavaScript排序算法及性能比较

十大经典排序算法

Leetcode 数据库题目

后端架构师技术图谱

算法之排序

二叉树的遍历算法

TCP/IP 协议低层驱动原理

leetcode题解

LeetCode 的题目印成一本书使用这个小工具：

数据结构入门

数据结构与算法分析