php经典面试题

1.["a"=>200,"d"=>100,"c"=>100,"b"=>100,"e"=>99], 写一个自定义排序函数，按值降序，如果值一样，按键排序。要求排序后的结果为：["a"=>200,"b"=>100,"c"=>100,"d"=>100,"e"=>99]

思路：冒泡排序，把数组的key抽出来一个独立数组ks: [a,d,c,b,e],数组的值抽出来一个独立数组aa:[200,100,100,100,99],对数组ks进行冒泡排序，

$arr = ["a"=>200,"d"=>100,"c"=>100,"b"=>100,"e"=>99,"f"=>300];

function arr_sort_by_valdesc_keyasc(array $a):array
{
    #数组先降序排序
    arsort($a);
    $ks = array_keys($a);
    $aa = [];
    foreach ($a as $key => $value) {
        $aa[] = $value;
    }
    $l = count($aa);

    #冒泡排序
    for($i=0;$i<$l;$i++)
    {
        for($j=0;$j<$l-1-$i;$j++)
        {
            #值相等的时候交换key的位置
            if($aa[$j] == $aa[$j+1])
            {
                if(strcasecmp($ks[$j],$ks[$j+1]) > 0 )
                {
                    $tem = $ks[$j];
                    #echo $ks[$j].'-'.$ks[$j+1]."\n";
                    $ks[$j] = $ks[$j+1];
                    $ks[$j+1] = $tem;
                    #echo $ks[$j].'-'.$ks[$j+1]."\n";
                }
            }
        }
    }
    $cc = [];
    for($i=0;$i<$l;$i++)
    {
        $cc[$ks[$i]] = $aa[$i];
    }

    return $cc;
}
$cc = arr_sort_by_valdesc_keyasc($arr);
print_r($cc);

2.得瑟约夫问题

概述：约瑟夫问题是个有名的问题，N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉

$arr = [1,2,3,4,5,6,7,8,9,10];//假如有10个人
$n = 3;//数到第三个kill掉一个人

function sigleLink($arr,$n)
{
    $count = count($arr);//获取总人数
    $k = $n;//记录步数
    while ($count > 1) { //如过只剩一个人就跳出循环
        
        foreach ($arr as $key => $val) {
          // 因为数组下标是从0开始，所以要$n-1
            if($key == ($n-1))
            {
                $temp = $arr[$key];
                unset($arr[$key]);
                echo $temp."出局: ".implode(',',$arr)." \n";
                $n += $k; //继续往下数$k个
                continue;
            }else
            {
                array_push($arr,$arr[$key]);//把前面的元素追加数组末尾，形成单链表
                unset($arr[$key]);
            }
        }
        $count = count($arr);//更新人数
    }
    print_r($arr);//打印最后剩下的
}
sigleLink($arr,$n);

3.PHP实现求两个字符串最长公共子串

https://www.jb51.net/article/128449.htm

<?php
$a = 'abceee12345309878';
$b = 'abceeew2345i09878fsfsfsfabceeewsfsdfsfsabceeew';
$c = array();
$lenht1 = strlen($a);
$lenth2 = strlen($b);
$startTime = microtime(true);
for ($i=0;$i<$lenht1;$i++) {
  for ($j=0;$j<$lenth2;$j++) {
    $n = ($i-1>=0 && $j-1>=0)?$c[$i-1][$j-1]:0;
    $n = ($a[$i] == $b[$j]) ? $n+1:0;
    $c[$i][$j] = $n;
  }
}
foreach ($c as $key=>$val) {
  $max = max($val);
  foreach ($val as $key1 =>$val1) {
    if ($val1 == $max && $max>0) {
      $cdStr[$max] = substr($b,$key1-$max+1,$max);
    }
  }
}
ksort($cdStr);
$endTime = microtime(true);
echo "Totle time is " . ($endTime - $startTime) . " s"."<br/>";
print_r(end($cdStr));
exit;