首页 > 阿里7.24笔试题解
头像
tuogy
编辑于 2020-07-25 06:08
+ 关注

阿里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,通过对比s1tk各列的灯状态可以得知每一个开关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





全部评论

(5) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐