阿里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个开关Li可以控制第i列，打开该开关使得该列灯状态反转。
行之间可以任意交换，问给定初始灯状态s和目标灯状态t，能否从初始变到目标状态，如果能，最少要打开几个开关。
分析：s的第1行s1一定对应t的某一行tk。如果已知k，通过对比s1和tk各列的灯状态可以得知每一个开关Li是否需要打开。
由于行之间可以任意交换，我们只需要验证在按照上面确定的开关状态下，两组灯状态的集合{s1,...,sN}和{t1,...,tN}是否相等。
我们用一个二进制数表示每一行灯的开关状态，如0010表示第三列灯开，其他灯关。验证集合相等可以在Python中用Counter类（哈希表）来实现。
时间复杂度：我们需要对k=1,...,N做搜索。每次搜索需要判断集合是否相等，这可以在O(NL)的时间内完成；总体复杂度O(N2L)。
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
投递快手等公司10个岗位 >
查看5道真题和解析
