百度3月7笔试题求解

就是黑白魔法这题,输入一个n代表n次魔法,之后输入n个非零数字代表每次释放的魔法,其中对于一段连续释放魔法累乘结果若为负数就是一次黑魔法,反之是一次白魔法,问最后一共能释放多少种不同的黑魔法以及白魔法,不同指的就是不同段连续释放组成的结果。这题难道不是就对每一个子串求一次累乘就行了嘛,还有啥特殊情况呢,只过了27%。

以下是核心代码块,m就是那一组释放的魔法的一个list,a代表黑魔法的次数,b代表白魔法的次数。

for i in range(len(m)):
    t = 1
    for j in range(i, len(m)):
        t *= m[j]
        if t < 0:
            a += 1
        else:
            b += 1

#笔试##百度#
全部评论
我AC了,就整个长度n的列表,每位记录以当前位为end的白魔法和黑魔法数。假设list[n] = [white,black],那我们读到n+1位的时候,如果是正数,那黑魔法的方案数会多list[n][1]种,白魔法的方案数会多list[n][0]+1种(因为会多只有第n+1本身的这种情况),是负数的话反过来,遍历一次以后把列表每个元素的[0]和[1]相加输出就ok啦,dp问题
3 回复 分享
发布于 2023-03-07 23:14 日本
可以看下我的题解
2 回复 分享
发布于 2023-03-07 22:03 安徽
我用的回溯,只有82%
2 回复 分享
发布于 2023-03-07 21:03 四川
n = int(input()) num = list(map(int, input().split())) l = len(num) count = [0, 0] # 存储白,黑的个数 if num[0] > 0: count[0] = 1 else: count[1] = 1 res_0, res_1 = count[0], count[1] for i in range(1, l): if num[i] > 0: count[0], count[1] = count[0] + 1, count[1] else: count[0], count[1] = count[1], count[0] +1 res_0 += count[0] res_1 += count[1] print(res_1, res_0) ac了,可以看作指针滑动,以当前指针所指元素为尾考虑的话,很类似双指针滑动那道题。 就出现了状态转移公式,对应在代码里,自己看吧
1 回复 分享
发布于 2023-03-09 01:01 湖北
借楼问有没有做A卷的佬,其他踢没A但至少有思路,第一题子序列拆分一点思路都没😥
1 回复 分享
发布于 2023-03-07 21:29 浙江
超时不会提醒吗
1 回复 分享
发布于 2023-03-07 20:59 上海
可以考虑二维dp,边算边保存应该就可以了.
点赞 回复 分享
发布于 2023-03-14 12:51 北京
百度的笔试是在牛客网上的吗?可以用本地ide吗
点赞 回复 分享
发布于 2023-03-12 14:01 黑龙江
请问笔试一共是三道编程题吗?
点赞 回复 分享
发布于 2023-03-10 15:38 四川
楼主,这是春招吗
点赞 回复 分享
发布于 2023-03-09 10:11 北京
黑魔法是DP,难度都不高
点赞 回复 分享
发布于 2023-03-08 16:52 山西
这样一直乘是不是会爆了。。
点赞 回复 分享
发布于 2023-03-07 23:59 日本
m[i] 的范围在-10^9到10^9之间,如果你每次都乘m[i]那你的t值会非常巨大
点赞 回复 分享
发布于 2023-03-07 23:28 德国
动态规划。 l = [1,-1,1,-1,1] 一维转移方程:dp[i] = l[i]*dp[i-1], dp[i]表示用i个连续时的乘积;两次循环,小循环从后面开始,每大循环计算一次当前dp中正负数,最后求和; 二维转移方差:dp[i][j] = l[i]*dp[i-1][j-1],dp[i][j]表示每次l中第i位置的数和其余与之连续的j-1个数的乘积,最后直接计算二维矩阵的正负个数; 27%可能是超时,82%应该是没用1,-1代替,导致数据超了
点赞 回复 分享
发布于 2023-03-07 22:35 四川
怀疑是不是python语言有问题啊On了只过27%
点赞 回复 分享
发布于 2023-03-07 21:25 北京
蹲,用的dp复杂度On, 也只过27
点赞 回复 分享
发布于 2023-03-07 21:09 江西
欸我去你们一说超时那还真是,问题是他也不提醒我也没想到是超时了
点赞 回复 分享
发布于 2023-03-07 21:07 河北
你这肯定超时啊,动态规划不就行了
点赞 回复 分享
发布于 2023-03-07 21:04 北京
(不同指的就是不同段连续释放组成的结果) 这句话应该代表最后释放的魔法序列不同 比如 [-1, 1, -1] 可以分成 一、[-1] [1, -1] 魔法序列就是(黑, 黑) 二、[-1, 1] [-1] 魔法序列也是(黑,黑) 这两种算作一种方案数
点赞 回复 分享
发布于 2023-03-07 21:03 河南
第一超时,第二t=m[i]
点赞 回复 分享
发布于 2023-03-07 21:03 河南

相关推荐

2025-11-21 03:09
已编辑
南昌大学 golang
bg普211本,走的golang后端方向。找实习经历:最近一个月投了一些日常,面了4场,都是一面挂。简历包装成分比较多,当时这个简历准备了两个星期,问AI解决什么问题用什么技术,跟其他技术对比优缺点在哪,等等。但是面试的时候一些基础的八股都答的模模糊糊,然后项目延伸的场景题一点不会。有点害怕面试,面前焦虑…本文可能带点碎碎念…省流就是因为每周面心态不行,不知道先学什么以及三天打鱼两天晒网…现在的主要问题,一个是只能依靠即时满足无法撑过枯燥的学习,另一个是难以调整心态,面试焦虑。个人背景:主包其实本来是大一开始学后端的,但是当时不知道合适的学习方法(学习路线和借助AI),也社恐不太敢问学长,走了很多弯路,也没有花很多时间在后端上面(按兴趣学的只有大二上学期写了opencamp的rustlings和learning-cxx,还有玩steam的图灵完备,剩余时间比较摆烂)。结果就是现在这鬼样子,只会写crud,差不多就是会gin&nbsp;gorm基础,会写注册登录和简单业务接口,写过几种项目结构和设计模式。缺乏自己延展的能力。计算机基础:也相当差,之前大二学的计网全忘光了,操作系统60飘过。虽然大一的时候打算法竞赛(也没什么成绩就是,省二等奖收集者),但到现在一年半没碰了,就只有dfs,并查集啥的一些很基础的题目随便写,hot100链表因为竞赛没练过相当不熟练。大二下的时候,数据库课看八股,又困又累,什么都没看进去,后面自然又是全忘光了。现在我虽然有了个概览,知道后端除了crud有缓存、微服务、分布式、消息队列等等东西,知道后端架构设计是要做权衡,性能、一致性、容灾,需要通过实验测出具体的数据来做决策,但是具体的方案不会,看基础知识是真看不进去。现在的主要问题,一个是只能依靠即时满足无法撑过枯燥的学习,另一个是难以调整心态。我高中以前一直是优等生,能够享受大部分题目都会的快感,能明确地有信心自己能做出来,解题过程需要进行推理,并且做完立刻就能得到正确反馈,其中的失败调整过程长度也在可接受范围内。(喜欢写rustlings一类的语言lab和玩《图灵完备》大概也是因为这个吧…)而现在的情景相当于我成了高三但是基础知识基本不会的状态,比我当年(会基础知识只是差做题)差多了。在这种情况下去面试也是相当痛苦,因为面试是不知道范围的。每次准备都不知道先看什么,学也学不进去。明明知道面试只是为了了解真实会问什么,但是还是很焦虑,拧巴心态。学长说去投简历面试实践是为了了解自己在哪里,别人在哪里,市场在哪里,但是我似乎还没有找到收敛的下限,只是一直失败…但是我也不能确定不面试就能学进去啊,因为我大二暑假是真的一点代码都不想碰,相当烦躁,八股也不想看。现在甚至连稍微花点时间的算法题(不能即时反馈的)都不想写了。还在纠结要不要整块时间搓项目压测试试,感觉会非常花时间。可能我项目管理也是一坨。
圆规学java:27届不着急,边投边学,克服恐惧感,你现在不敢面试,你为什么认为你暑期就勇敢了,你现在的进度其实还很早,我当时大三下才开始实习,我也很焦虑着急。永远没有准备好的时候,当下努力就是最好的加油!
点赞 评论 收藏
分享
评论
11
15
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务