阿里7.24笔试题解

楼主没有参加这场笔试，在牛客网上看到题目，做了一些整理。

1. 吃烧饼。有n个盘子，每个盘子内有w[i]个烧饼。每次选取一个1≤x≤n，可以吃到1-x号盘子里的一个烧饼。若这x个盘子中有空盘时无法进行该操作。

问经过任意多次这种操作后，最多可以吃掉多少烧饼。

分析：不难得知，对每个盘子，最多可吃的数量为：它和它前面的盘子中最少的烧饼数。

用一个变量cur记录到目前盘子为止最少的烧饼数即可。时间复杂度O(n)

def p1(arr):
    cur, ret = arr[0], 0
    for v in arr:
        cur = min(cur, v)
        ret += cur
    return ret

2. 开关灯。N行L列的灯，有L个开关，第i个开关L_i可以控制第i列，打开该开关使得该列灯状态反转。

行之间可以任意交换，问给定初始灯状态s和目标灯状态t，能否从初始变到目标状态，如果能，最少要打开几个开关。

分析：s的第1行s₁一定对应t的某一行t_k。如果已知k，通过对比s₁和t_k各列的灯状态可以得知每一个开关L_i是否需要打开。

由于行之间可以任意交换，我们只需要验证在按照上面确定的开关状态下，两组灯状态的集合{s₁,...,s_N}和{t₁,...,t_N}是否相等。

我们用一个二进制数表示每一行灯的开关状态，如0010表示第三列灯开，其他灯关。验证集合相等可以在Python中用Counter类（哈希表）来实现。

时间复杂度：我们需要对k=1,...,N做搜索。每次搜索需要判断集合是否相等，这可以在O(NL)的时间内完成；总体复杂度O(N²L)。

from collections import Counter

def p2(s, t, L):
    ret = L + 1
    set_s = Counter(s)
    
    for t_k in t:
        flip = s[0] ^ t_k
        nflip = bin(flip).count('1')
        if nflip < ret and set_s == Counter(t_i ^ flip for t_i in t):
            ret = nflip
    
    return ret if ret <= L else -1