??公司：PDD

??崗位：算法實習(xí)生

??問題：四道編程題：

1）幸運青蛙：T組數(shù)據(jù)，n個石板，‘1’表示有青蛙，，‘0’表示無青蛙。當(dāng)最大相鄰的青蛙數(shù)剛好等于9的時候，輸出‘lucky’，反之輸出‘unlucky’

輸入：

1

10

111111111110

輸出：

lucky

思路：貪心算法

反思：多組輸入輸出不熟練，浪費了很多時間

2）最少顧客糖果兌換卷數(shù)：n個顧客，需要兌換m個糖果，每張兌換卷能夠兌換k個糖果，求最少需要多少兌換卷。其中每個顧客可以選擇任意數(shù)量的兌換糖果數(shù)，其所需的兌換卷數(shù)a=（m/k），a為整數(shù)，結(jié)果取四舍五入。

輸入：

3

300

100

輸出：

2

思路：想到了雞兔同籠問題，首先計算出每個顧客能夠白嫖的最大糖果數(shù)大約Candle=int（0.5*k），然后我們需要的兌換券數(shù)等于（m-Candle)//k。

反思：一開始寫代碼的時候沒有注意到去考慮白嫖的最大糖果數(shù)能否整除的取值問題

3）最大優(yōu)惠金額：n件商品，m件優(yōu)惠券（其中商品價格需要大于a才能使用），每件商品只能用一張優(yōu)惠卷，求最大的優(yōu)惠金額總和。

輸入：

2 2

15 20

20 5

25 8

輸出：

5

思路：雙循環(huán)，第一層循環(huán)遍歷商品，第二層循環(huán)找到每一件商品能夠優(yōu)惠的最大金額，并在列表中刪除該優(yōu)惠券

反思：超時，成功32%的案例，剪枝只能夠提高通過率，自我感覺沒有利用上每次循環(huán)的優(yōu)惠卷選擇信息

4）最大變化數(shù)：給定s1,s2,其中s1的各個位置可以任意調(diào)整，但是不能超過s2，輸出最大的s1.

輸入：

12345

26531

輸出：

25431

反思：時間都花在第三題的剪枝上了，應(yīng)該不難，沒有去嘗試

結(jié)論：感覺可能在計算機科學(xué)學(xué)科中都算最基礎(chǔ)的問題了，老老實實找機械的老本行hhhhh