牛客第一菜狗
2023-03-30 17:47 谷歌_SDE
关注
第一题：
动态规划，dp[i]记录到i为止的结果，last[j]表示上一次拿到宝石j的关卡。则dp[i]=max{dp[i-1], dp[last[x]] + y}，要求last[x]存在。
第二题：
简单dfs，从下向上记录将子树修复所需要派出的施工队数。如果发现一个孩子的dfs为0且从本节点到孩子的道路需要修复，则该孩子的答案设为1。最后把所有孩子的答案加起来就是本节点的result。
第三题：
参考力扣原题152，本题不保证数据范围，因此要把所有a[i]对2取对数并记录符号。我写得比较恶心。先根据0切片，对每个切片分情况讨论：
如果负数的数量是偶数，则直接把子数组求和（已经转为对数）即可。
如果负数数量是奇数，找到第一个负数和最后一个负数，分别取其后和其前，更新结果即可。
第四题：
先记录每个值所对的所有下标。贪心从后往前，维护到当前为止的右侧最小值right，当且仅当a[i]≤right且a[i]占据一片连续的区域时才可以跳过a[i]，否则就要把所有a[i]更新为0。同时更新right。
查看原帖
5 13
相关推荐
查看1道真题和解析
牛客热帖
更多
正在热议
更多
# 这个offer值得去吗？ #
21022次浏览 178人参与
# 上班苦还是上学苦呢？ #
345273次浏览 2069人参与
# 在爱玛，骑向未来 #
2939次浏览 319人参与
# 如果春招能重来，我会___ #
21663次浏览 229人参与
# 提名点击就挂的公司 #
144177次浏览 491人参与
# 除了线上，还能去哪些地方投简历 #
11734次浏览 116人参与
# 联宝杯大学生创新大赛，你的技术值得产业级答案 #
47740次浏览 517人参与
# 字节开奖 #
151390次浏览 693人参与
# 实习怎么做才有更好的产出 #
49952次浏览 457人参与
# AI coding的好用工具分享 #
88464次浏览 567人参与
# 找工作以来，你最看不惯__ #
79426次浏览 594人参与
# 大学四年该怎么过，才不算浪费时间？ #
23861次浏览 107人参与
# 运营每日一题 #
144366次浏览 978人参与
# 面试等了一周没回复，还有戏吗 #
246003次浏览 1857人参与
# 字节7000实习来了，你投了吗？ #
55256次浏览 421人参与
# 毕业后不工作的日子里我在做什么 #
269135次浏览 1739人参与
# 薪资爆料 #
422534次浏览 2226人参与
# HR问：你期望的薪资是多少？如何回答 #
99344次浏览 833人参与
# 我的秋招“寄”录 #
476388次浏览 3063人参与
# 哪一刻你突然觉得实习“有点值了” #
28279次浏览 177人参与
# 双非本科求职如何逆袭 #
1649021次浏览 13083人参与
# 双非应该如何逆袭？ #
586731次浏览 6396人参与