2020网易：安置路灯[python][队列][贪心]

【Python15行】提供另一种思路：考虑使用队列+二进制编码来解，复杂度O(n)。贪心作为常规思路，在文末附上。

首先，枚举每三位可能的情况：

• 取【.】为1、【X】为0， 编成二进制，则点灯和不点等的情况为:

  点灯： 4 5 6 7
  不点： 0 1 2 3

• 构建一个队列，从左往右扫描入列，当队列达到三位时进行判断，若为不点灯的情况直接出列，否则清空队列、点灯计数器加一。

• Tip：编成二进制的做法只是为了方便阅读，可选。

算法核心：

def calc(path):
    compile_bin = lambda li: int(''.join(queue), 2) # 二进制编码转十进制

    cnt, queue = 0, []
    for i in path:
        queue.append('1' if i=='.' else '0')
        if len(queue)==3:
            res = compile_bin(queue)
            if res == 0: # xxx
                queue = [] # 特别的，这种情况可以直接清理三位
            elif res <= 3: # xx.或 x.x 或 x..
                queue.pop(0)
            else:
                cnt += 1
                queue = []

    cnt += (1 if '1' in queue else 0) # 清空剩余需要照亮的点
    return cnt

IO部分：

# 需要照亮的地方用'.'表示, 不需要照亮的障碍物格子用'X'表示，一个路灯可以照亮左右及自身的方格
t = int(input())
for j in range(t):
    n, path = int(input()), [i for i in input()] # Notice: input() for python 3.6
    print(calc(path))

贪心解法

让灯尽量覆盖到更大的地方 —— 即若i处要照亮的话，那么在i+1处放灯可以照得更远。

如果第i个位置为'.'，则计数器加一，i+=3

def calc(path):
    cnt, i = 0, 0
    while i<len(path):
        if path[i]=='.':
            cnt += 1
            i += 3
        else:
            i +=1
    return cnt