第一个题复杂度直接暴力dfs的复杂度是O(n!),n=10的时候一般就很慢了,剪枝一下可能能过。我感觉正解应该是用状压dp,dp[i][j]表示在状态i下最后一个数是j的数据总数,这样复杂度就能降到O(n*2^n),就能解决部分评论说的回溯超时的问题了。 第二个题可以用一个双指针+map的做法复杂度O(nlogn),枚举子数组左区间,显然可行的右区间是一段后缀,而且当左区间越枚举时可行右区间的后缀越来越小。就可以用双指针来枚举,用map记录可行性,然后记一下每一次后缀长度累加一下即可。 楼上的第二题O(n)做法看不懂,我太菜了。
1 3

相关推荐

想去毕业旅行的斑马在...:学校不是92的话,没有实习经历投不了大厂,去投中小厂,拿点实习经历
点赞 评论 收藏
分享
牛客网
牛客网在线编程
牛客网题解
牛客企业服务