2022-08-20 20:59 东南大学 算法工程师 发布于江苏
关注
#民生银行笔试# #民生银行# #笔试# #算法工程师#
第一题
题意：给定包含n个链表序列，从第n个链表连接到第1个链表，返回连接后的链表。
跳过空链表直接求解即可，复杂度 O(n)。
第二题
题意：给定一个硬币集合 x，返回不能通过这些硬币拼凑得到的最小正整数。
排序后DP。dp[i] 表示前 i 个硬币能拼凑出的连续的最大值，如硬币序列为 [1,2] 时dp数组为 [1,3]。如果满足 x[i] <= dp[i-1]+1 则 dp [i] = x[i]+dp]i-1]；否则就说明 dp[i-1]+1 无法得到，即为结果；如果能一直递推结束，结果则为 dp[-1] + 1。时空复杂度 O(n)。
暴力的话复杂度是 2^n 会超时。
第一题
题意：给定包含n个链表序列，从第n个链表连接到第1个链表，返回连接后的链表。
跳过空链表直接求解即可，复杂度 O(n)。
第二题
题意：给定一个硬币集合 x，返回不能通过这些硬币拼凑得到的最小正整数。
排序后DP。dp[i] 表示前 i 个硬币能拼凑出的连续的最大值，如硬币序列为 [1,2] 时dp数组为 [1,3]。如果满足 x[i] <= dp[i-1]+1 则 dp [i] = x[i]+dp]i-1]；否则就说明 dp[i-1]+1 无法得到，即为结果；如果能一直递推结束，结果则为 dp[-1] + 1。时空复杂度 O(n)。
暴力的话复杂度是 2^n 会超时。
全部评论
Les1ie 楼主
楼主 东南大学 算法工程师
第二题有个排序，仅dp的复杂度是O(n)，所以总复杂度是（n log n）
月照江
西安电子科技大学 C++
民生科技吗
今晚打老虎Boy
韩山师范学院 Java
请问这是科技类的部分题吗？
相关推荐
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
01-10 18:10
点赞 评论 收藏
分享
，不过这经纬恒润是真扣 
野猪不是猪🐗：小厂最大的问题就是，你不知道哪天公司就直接🈚️了。大厂被裁，拿着大厂履历也不难再找，小厂寄了那后面有没有人要你就不好说了
点赞 评论 收藏
分享