牛客第一菜狗
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
相关推荐
点赞 评论 收藏
分享
查看8道真题和解析
牛客热帖
更多
正在热议
更多
# 你现在会用到哪些AI技能？ #
5746次浏览 80人参与
# 蚂蚁求职进展汇总 #
123078次浏览 1163人参与
# 智慧芽求职进展汇总 #
1720次浏览 5人参与
# 秋招踩过的“雷”，希望你别再踩 #
84133次浏览 1076人参与
# 我对___祛魅了 #
132244次浏览 736人参与
# 大厂VS公务员你怎么选 #
27126次浏览 393人参与
# 平安产险科技校招 #
696次浏览 0人参与
# 你还有多少年退休？ #
26735次浏览 192人参与
# 我的求职进度条 #
88977次浏览 1177人参与
# 实习在多还是在精 #
34783次浏览 242人参与
# 实习下班不想学习，正常吗？ #
19873次浏览 173人参与
# 小马智行求职进展汇总 #
13540次浏览 49人参与
# 你的房租占工资的比例是多少？ #
64757次浏览 798人参与
# 你见过哪些工贼行为 #
16488次浏览 90人参与
# 金蝶求职进展汇总 #
53891次浏览 263人参与
# 总结:哪家公司面试体验感最好 #
70146次浏览 416人参与
# 校招谈薪一定要知道的事 #
13221次浏览 114人参与
# 找工作中的小确幸 #
26797次浏览 276人参与
# 顺丰求职进展汇总 #
63350次浏览 314人参与
# 非技术岗投递进展 #
157915次浏览 1314人参与
# 反问环节如何提问 #
115329次浏览 2462人参与
# 你觉得材料多少算高薪 #
26124次浏览 159人参与