呃....算法栏目

在线解析器

一元即租房

活动“司庆大放送,一元即租房”,司庆当日,对于签约入住的客户,住满 30 天,返还(首月租金 -1 元)额度的租金卡。租金卡的面额遵循了类似人民币的固定面额(1000 元、500 元、100 元、50 元、20 元、10 元、5 元、1 元),请实现一个算法,给客户返还的租金卡张数是最少的。

答案校验

示例:
输入(租金卡金额):54
输出:5
输入(租金卡金额):9879
输出:20
$card = [1000, 500, 100, 50, 20, 10, 5, 1];
$money = 9879;
$reCard = [];
$index = 0;
while ($money) {
    $temp = intval($money / $card[ $index ]);
    $money = $money - ($temp * $card[ $index ]);
    if ($temp) {
        for ($i = 0; $i < $temp; $i++) {
            $reCard[] = $card[ $index ];
        }
    }
    ++$index;
}
return $reCard;

约瑟夫问题

约瑟夫问题是个有名的问题:N个人围成一圈,从第一个开始报数,第M个将被杀掉,最后剩下一个,其余人都将被杀掉。例如N=6,M=5,被杀掉的顺序是:5,4,6,2,3,1。

$n = 41;
$m = 3;
$peoples = range(1, $n);
$i = 0;
while (count($peoples) > 1) {
    //模拟报数
    $i += 1;
    $head = array_shift($peoples);
    //这里不难发现,只要是 $n的倍数的人都会死
    if ($i % $m != 0) array_push($peoples, $head);
}
print_r($peoples);

斐波那契数列

//1、1、2、3、5、8、13、21、34....
$list = [1, 1];
$n = 10;
for ($i = 1; $i < $n - 2; $i++) {
    $sum = $list[0] + $list[1];
    array_shift($list);
    array_push($list,$sum);
}
$sum = $list[0]+$list[1];
echo $sum;

按照每个字符串中字符重复出现的次数从大到小排列 题目地址

按照每个字符串中字符重复出现的次数从大到小排列;如果次数相同,按照出现次数第二多的字符排序,如果仍然一样多,按照数组中字符串默认顺序进排序,例如: 字符串 "abcabccaa" 中出现次数最多的字符是 a , 出现了 4 次;出现次数第二多的是 c , 出现了 3 次;出现次数第三多的是 b , 出现了 2 次 那么 ["yytyts", "abcabccaa", "uuuxyy", "mommentem"] 排序之后的结果是: ["abcabccaa", "mommentem", "yytyts", "uuuxyy"]

解题思路

  • 循环数组,str_split拆解字符串
  • array_count_values函数求出每个值出现的次数,并arsort排序
  • 把当前的字符串、当前字符串拆解出来出现最多次数的值、当前所处位置(便利的$key)放入新的数组
  • array_multisort函数排序新数组,先按照出现次数的数组DESC排序,再按照原来所处位置ASC排序
$beforeStrs = ['yytyts','abcabccaa','uuuxyy', 'mommentem'];
//排序数组
$sortArrayLists = [];
//排序数组1
$sort1 = [];
//排序数组2
$sort2 = [];
foreach ($beforeStrs as $key=>$beforeStr) {
    $_lists['str'] = $beforeStr;
    //统计所有所有字符出现次数
    $valuesCount = array_count_values(str_split($beforeStr));
    //按照 desc 排序
    arsort($valuesCount);
    //取出最大
    $maxValuesCount = current($valuesCount);
    //最大的写入排序数组1
    $sort1[] = $maxValuesCount;
    //把出现最多次数的字符串出现次数和之前数组的key赋值
    $_lists['max_value_cont'] = $maxValuesCount;
    $_lists['before_index'] = $key;
    $sortArrayLists[] = $_lists;
    //之前的key,写入排序数组2
    $sort2[] = $key;
}
array_multisort($sort1, SORT_DESC, $sort2, SORT_ASC, $sortArrayLists);
$afterStrs = array_column($sortArrayLists,'str');
print_r($afterStrs);
array:4 [▼
  0 => "abcabccaa"
  1 => "mommentem"
  2 => "yytyts"
  3 => "uuuxyy"
]

这里用到了array_multisort函数

计算你没买一张彩票亏多少钱李永乐老师讲解

古典概率

M种可能,N中选择 那么你选中概率就是 P=N/M

组合型

n个物种中选m个 P=Cnm

福利彩票33中选6个红球,16个中选1个蓝球

P=C(33,6)C(16,1) = 17721088

那就意味着你一共有17721088种选择

根据中奖等级计算概率

中奖等级 中奖形式 概率表达式 组合方式数量 概率(组合方式数量 / 总共组合方式(P)) 奖金 期望(奖金 * 概率)
6+1 C(6,6)C(1,1) 1 5.64E-8 500w 0.282
6+0 C(6,6)C(15,1) 15 8.46E-7 20w 0.169
5+1 C(6,5)C(27,1)C(1,1) 162 9.14E-6 3000 0.0274
5+0 / 4+1 C(6,5)C(27,1)C(15,1) + C(6,4)C(27,2)C(1,1) 7695 4.34E-4 200 0.0868
4+0 / 3+1 C(6,4)C(27,2)C(15,1) + C(6,3)C(27,3)C(1,1) 137475 7.75E-3 10 0.0775
2+1 / 1+1 / 0+1 C(6,2)C(27,4)C(1,1) + C(6,1)C(27,5)C(1,1) + C(27,6)C(1,1) 1043640 5.88E-2 5 0.294

最后期望总和是0.9367,你长期买彩票的情况下,是亏 1.1的