[数据结构与算法]美团笔试3.12— —只要你够贪心

完整题目参见：牛客3.12 美团笔试题解

题目一：

n个房间（0<n<=10)，初始的时候A在第一个房间，现在有一个游戏，游戏时长为m（0<m<=10000)秒，给出m
秒每秒的炸弹所在的房间，A需要在每秒避开这些炸弹，也就是A不能在有炸弹的房间。A可以在每秒后选择移动到n个房间中的一个，但是需要消耗1个能量，当然也可以不移动，问A最少需要消耗多少能量。
样例输入：n=2, m=4, bursts=[2,1,1,2]；样例输出：2

解题思路：

有人说dp但我同门想出了贪心，只需遍历一次。
贪心体现在：

1. 在炸弹💣爆炸的最后一刻再换房间
2. 换到下一次能撑最久的那个房间🚪

这个贪心的正确性直觉上稍加推导一下差不多就能感觉出来。

coding：

因为题目规定了第一个房间为房间1，因此先找到第一个房间爆炸时刻，然后以该点为起始点，向后找下一个要跳的房间，规则是换到下一次能撑最久的那个房间。可以循环向后找，当剩余房间刚好在这一段全部爆炸的时候停下，那么停下的房间能撑最久的那个房间。具体的实现方式可以是每次找的时候都重新初始化一个visit集合，每爆炸一个房间就把该房间放入集合，如果爆炸房间已经出现在集合中，flag不变，否则加一，来记录已经爆炸的不同房间数，直到刚好房间全部爆完，那么加入的最后一个房间就是我们要找的房间（以上是同门的做法）。（我的做法是）直接用一个二进制state记录爆炸情况，当所有房间都爆炸时state==(1<<n)-1，利用该条件来判断是否该停下换房间了。每次停下就说明要换房间，次数加一即可。
时间复杂度o(n)
空间复杂度o(1<<n 二进制)

def solutions(n, m, brusts):
    room = 1
    step = 1
    ans = 0
    ## 移到第一个房间爆炸的时间点
    while step < m:
        if room == brusts[step]:
            break
        step += 1
    ## 
    while step < m:
        ans += 1
        state = 1<<(room-1)
        ##  往后找最后一个房间第一次出现的时间点，选择该房间
        while state != (1<<n)-1:
            step += 1
            ## 可以撑到最后，退出
            if step == m:
                return ans
            state |= 1<<(brusts[step]-1)
        room = brusts[step]
            
    return ans
    
n = 2
m = 4
brusts = [2,1,1,2]
print(solutions(n, m, brusts))    

————————————————————————————————————————————
参考：牛客3.12 美团笔试题解