2018.9.27 小米笔试

发表于 |

总结：共两道题，全部AC，出题人抄的leetcode原题，这个出题水平有待提高呀

1. 厨艺大赛奖金（AC）

小米食堂每年都会举办一次厨艺大赛，假设参赛的厨师一共有n位(n < 1000)，比赛结束后没有公布评分，但是每位厨师只能看到与自己相邻的厨师里评分比自己低的评分。
比赛结束后发奖金，每位厨师最少会得到1K的奖金，另外，如果一个厨师发现自己的奖金数量没有高于比自己评分低的厨师的奖金，就会不满意。作为比赛组织法，小米食堂至少需要发放多少奖金才能让所有厨师满意。

输入描述：
每行n+1个整数
第一个整数代表厨师的总人数
后n个整数分别代表每个厨师的得分

输出描述：
一个数字
代表至少需要发放的奖金数量（K为单位）

样例输入：
10 60 76 66 76 85 55 61 71 84 62

样例输出：
20

解释：__位厨师实际发放奖金为：
1 2 1 2 3 1 2 3 4 1

思路分析：
这是leetcode上的一道原题，candy problem
https://leetcode.com/problems/candy/description/
最初我做这道题的时候用的one pass solution，虽然通过了，但是我自己写的代码太丑了，情况考虑得太复杂，其实很多可以合并。
这里采用更加标准的贪心思想来解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
data = list(map(int, input().split()))
nums = data[1:]
def candy(ratings):
    n = len(ratings)
    candy = [1] * n
    for i in range(1,n):
        if ratings[i] > ratings[i-1]:
            candy[i] = candy[i-1] + 1
    
    for i in range(n-2,-1,-1):
        if ratings[i] > ratings[i+1] and candy[i] <= candy[i+1]:
            candy[i] = candy[i+1] + 1

    return sum(candy)
print(candy(nums))

2. 扑克牌四则运算(AC)

现在有一幅扑克牌，去掉大小王。随机选出4张牌，可以任意改变扑克牌的顺序，并填入+-*/四个运算符，(除法按整除计算)。计算过程中不会出现浮点数，问是否能求值得到给定的数m。

输入描述：
一共两行
第一行四个数字，空格分割，代表扑克牌的数字（J,Q,K分别为11,12,13）
第二行一个数字，代表m

输出描述：
可以输出1
否则输出0

样例输入：
13 13 13 13
24

样例输出：
0

思路分析：
这又是leetcode上的原题，24点游戏，只不过leetcode上固定求值为24
因为只有4个数字，显然可以暴力计算所有的结果，这里使用了python种Itertools库中的一个函数，直接获得所有运算符可能的组合方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import itertools
read = lambda : list(map(int,input().split()))

class Solution(object):
    def solve(self, nums, m):
        Ops = list(itertools.product(['+','-','*','//'], repeat=3))
        for ns in set(itertools.permutations(nums)):
            for ops in Ops:
                result = str(ns[0]) + ops[0] + str(ns[1]) + ops[1] + str(ns[2]) + ops[2] + str(ns[3])
                if eval(result) == m: return True
        return False

nums = read()
m = int(input())
p = Solution()
print(int(p.solve(nums, m)))