shenzui
2021-09-18 12:00 蚂蚁集团_算法工程师
关注
本人已ak，第二题分成递增和递减两种情况讨论，分别离散化后找环，所有环的周长-1的和就是答案，最后俩情况取min。第三题动态规划，dp[i]表示[1,i]内能得到的答案，枚举i，往前遍历找到第一个与a[i]相同的值，下标为mid，查询已经遍历的区间内有无另一个值的个数大于1，如果有，dp[i]=max（dp[i]，dp[mid-1]+1），如果无，则继续往前遍历，找到第一个满足区间内a[i]的个数大于3或者不为a[i]的个数大于1的下标pos，则dp[i]=max(dp[i],dp[pos-1]+1)，最后区dp[i]=max（dp[i]，dp[i-1]）。最终答案就是dp[n]。
查看原帖
7 7
相关推荐
点赞 评论 收藏
转发
牛客热帖
- 1... 想来字节技术实习，看我这篇就够了！——保姆级面经大放送2.6W
- 2... 外卖员面试经验1.7W
- 3... 25届第一份实习怎么找？1.6W
- 4... 【0429快问快答】99%牛油的疑惑解答（更新至38个问题1.6W
- 5... 0实习经验上岸字节，分享一下过程经验1.5W
- 6... 【奖】休息放松or学习提升，五一假期和牛牛一起“充充电”🔋1.3W
- 7... 准备去参加自己的婚礼9768
- 8... 美团后端日常实习一二面（已oc）7979
- 9... 【💰有奖征集】非技术岗位笔面经邀你来分享！攒人品时间到！6563
- 10... 【薪资计算】SS Is All You Need5838
正在热议
# 牛友的五一计划 #
20758次浏览 407人参与
# 晒一晒我的offer #
2839550次浏览 50025人参与
# 牛客帮帮团来啦！有问必答 #
405192次浏览 7868人参与
# 市场营销面经 #
1342次浏览 71人参与
# 非技术岗薪资爆料 #
9366次浏览 189人参与
# 产品实习，你更倾向大公司or小公司 #
31385次浏览 492人参与
# 如何看待offer收割机的行为 #
195344次浏览 2999人参与
# 第一次面试 #
18423次浏览 284人参与
# 2022届毕业生现状 #
285784次浏览 4103人参与
# 硬件人的春招flag #
14611次浏览 199人参与
# 浅聊一下我实习的辛苦费 #
71089次浏览 643人参与
# 华为求职进展汇总 #
443892次浏览 4450人参与
# 在国企工作的人，躺平了吗？ #
73302次浏览 889人参与
# 你更愿意参加线上面试还是线下面试？ #
7103次浏览 98人参与
# 女生做医疗销售有前景吗 #
3923次浏览 49人参与
# 简历中的项目经历要怎么写 #
382081次浏览 6406人参与
# 来聊聊机械薪资天花板是哪家 #
23296次浏览 180人参与
# 如何KTV领导 #
7602次浏览 74人参与
# 产品薪资爆料 #
28113次浏览 509人参与
# 聊聊这家公司值得去吗 #
64546次浏览 1308人参与