PDD 25.04.09 笔试

📍公司：PDD

👜岗位：算法实习生

📖问题：四道编程题：

1）幸运青蛙：T组数据，n个石板，‘1’表示有青蛙，，‘0’表示无青蛙。当最大相邻的青蛙数刚好等于9的时候，输出‘lucky’，反之输出‘unlucky’

输入：

1

10

111111111110

输出：

lucky

思路：贪心算法

反思：多组输入输出不熟练，浪费了很多时间

2）最少顾客糖果兑换卷数：n个顾客，需要兑换m个糖果，每张兑换卷能够兑换k个糖果，求最少需要多少兑换卷。其中每个顾客可以选择任意数量的兑换糖果数，其所需的兑换卷数a=（m/k），a为整数，结果取四舍五入。

输入：

3

300

100

输出：

2

思路：想到了鸡兔同笼问题，首先计算出每个顾客能够白嫖的最大糖果数大约Candle=int（0.5*k），然后我们需要的兑换券数等于（m-Candle)//k。

反思：一开始写代码的时候没有注意到去考虑白嫖的最大糖果数能否整除的取值问题

3）最大优惠金额：n件商品，m件优惠券（其中商品价格需要大于a才能使用），每件商品只能用一张优惠卷，求最大的优惠金额总和。

输入：

2 2

15 20

20 5

25 8

输出：

5

思路：双循环，第一层循环遍历商品，第二层循环找到每一件商品能够优惠的最大金额，并在列表中删除该优惠券

反思：超时，成功32%的案例，剪枝只能够提高通过率，自我感觉没有利用上每次循环的优惠卷选择信息

4）最大变化数：给定s1,s2,其中s1的各个位置可以任意调整，但是不能超过s2，输出最大的s1.

输入：

12345

26531

输出：

25431

反思：时间都花在第三题的剪枝上了，应该不难，没有去尝试

结论：感觉可能在计算机科学学科中都算最基础的问题了，老老实实找机械的老本行hhhhh