Menu Sidebar
Menu

August 2021

Kth Smallest Subarray Sum

找第k小的subarray sum. 这题吧..如果不卡时间, 应该不难, 但是这题用treeset过不了, 所以只能用binary search做, 已知subarray sum可以用pre sum求, 并且是递增的 (nums[i] >= 1) 所以这题可以用binary search找一个mid最小值下, 第k的值.

Delete and Earn

给一个数组, 给一个操作: 删除一个数字, 然后得到这个数字的分数, 并且必须删除这个数字-1和+1的所有数字, 求最大的分数. 这题就是dp+贪心, 因为要得到最高的分数, 所以肯定要删大的先, 找到最大的删后, 就不用担心这个数字有+1的数字被删掉了. 然而只是贪心不够的, 因为如果是按照排序的数删除的话, 会有[10,8,8,8,8,8]这类情况, 所以还是要dp. 那么设dp[i]为删到大小为i的时候最大的分数. 那么dp[0] = 0, dp[1] = {all 1}, dp[2] = max{all 2 + dp[0], dp[1]}. dp[3] = max{all 3 + dp[1], dp[2]} dp[i] = {dp[i-2] + sum[i], dp[i-1]}意义是: 两种选法儿, 第一种是选i-2的最佳答案,并且加上sum[i], 因为隔了一个, 所以是能选的. 第二种选法是选上一个的最佳答案, 这次的不要了

Older Posts

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.