Leetcode 超难题目 Hard

动态规划

2945. 找到最大非递减数组的长度 (难度分2943,“超难”)

这道题很有可能是LC主站(LCP除外)新的天花板,之所以难度分没有超过1719题,是因为双周赛样本量本身不多,而这题有一定的“猜结论”。某个LC积分2900+的大佬认为,即使数据范围只有1000,这也是一道相当难的题目。因为记录dp[j]为最优时,nums[j]的最小值(注意nums[j]很可能是被改过的),这样的DP本身就很难想到。而同时保证dp[j]最大nums[j]最小是否就更利于后面的转移,这点非常难证明。这个题的数据范围并不是1000,因此需要单调数据结构优化来保证复杂度合理。

2809. 使数组和小于等于 x 的最少时间 (难度分2978,“超难”)

思路也是非常难想的,只是代码很好写。很显然重复操作相同下标一定是血亏的,而根据排序不等式,如果选了一些下标j,则对应nums2元素较大的j应该尽量晚操作。因此正解是转化为二维DP,状态定义为前i个数(注意是按nums2从小到大排好的前i个)中操作j个数,能减少的数组和。然后根据每多操作一次总和增加sum(nums2),遍历DP数组找答案。注意这道题二分猜答案是错误的,由于每操作一次都会带来额外的数组和,操作j次能满足题意,但操作j+1次做不到是很正常的。

2851.字符串转换 (难度分2857,“超纲”)

题号和难度分正好是相邻素数~这道题有2个超纲点

相关推荐

  1. Leetcode 题目 Hard

    2024-01-05 20:56:03       39 阅读
  2. Leetcode】269.火星词典(Hard

    2024-01-05 20:56:03       26 阅读
  3. Leetcode】772.基本计算器III (Hard

    2024-01-05 20:56:03       39 阅读
  4. LeetCode 968.监控二叉树 (hard)

    2024-01-05 20:56:03       17 阅读
  5. LeetCode 每日一题(Hard) Day 11||单调栈

    2024-01-05 20:56:03       34 阅读
  6. Leetcode】239.滑动窗口最大值(Hard

    2024-01-05 20:56:03       31 阅读

最近更新

  1. TCP协议是安全的吗?

    2024-01-05 20:56:03       16 阅读
  2. 阿里云服务器执行yum,一直下载docker-ce-stable失败

    2024-01-05 20:56:03       16 阅读
  3. 【Python教程】压缩PDF文件大小

    2024-01-05 20:56:03       15 阅读
  4. 通过文章id递归查询所有评论(xml)

    2024-01-05 20:56:03       18 阅读

热门阅读

  1. 前端深拷贝

    2024-01-05 20:56:03       35 阅读
  2. Linux 网络工具

    2024-01-05 20:56:03       35 阅读
  3. Qt快捷键

    2024-01-05 20:56:03       33 阅读
  4. Vue3.0+Echarts (可视化界面)

    2024-01-05 20:56:03       37 阅读