建设银行英文网站,做微信用什么网站,wordpress用thinkphp,营销型企业网站建设流程Leetcode 3049. Earliest Second to Mark Indices II 1. 解题思路2. 代码实现3. 算法优化 题目链接#xff1a;3049. Earliest Second to Mark Indices II
1. 解题思路
这道题我看貌似难度报表#xff0c;比赛的时候貌似只有36个人搞定了这道题目#xff0c;然后最快的人…Leetcode 3049. Earliest Second to Mark Indices II 1. 解题思路2. 代码实现3. 算法优化 题目链接3049. Earliest Second to Mark Indices II
1. 解题思路
这道题我看貌似难度报表比赛的时候貌似只有36个人搞定了这道题目然后最快的人耗时也花了40min以上就很离谱和平时基本15分钟就能有大佬全部做出来4道题的情况完全不懂就很吓人。
所以基本上我对这道题也算是一个半放弃的状态不过后来还是看了一下然后发现其实也不是完全无法上手本质上还是求一个处理的最优解且显然这个操作依然是单调的即从某一个位置开始后续所有的操作序列都可以使得所有的位置都被mark上。
因此最开始我的思路也是二分法来求任意一个位置作为操作序列的结束点时能否判断其是否可以使得所有的位置都被mark上然后就和上一题一样这里就变成了一个贪婪算法要最优的分配点数使得所有的值都可以先降为0然后再mark上。
但是比较尴尬的是这里我们的贪婪算法并没有完成因此有以下一个判断无法彻底想明白
已知任何一次直接归零操作都必须附加一次mark操作进行完成因此对于任意一个点我们需要判断是否要等待后续直接操作位然后再多加一轮操作使之mark还是直接使用当前富裕的点数如果有的话进行归零然后mark。
因此后续干脆就是直接绕开这个走了最暴力的动态规划的方法遍历了所有的可能即每一个位置到底是走的快速清零还是进行-1或者mark操作这里显然如果要进行快速清零那必然是在某个位置在changeIndices当中最早出现的位置上。
但是直接地实现会出现内存爆炸的情况因此我们做了一些不严谨的剪枝即如果某次快速清零可以省出100以上的富裕那么必走快速清零反之考虑是否忽略掉这个快速清零的路线。
需要强调这个方式是不严谨的因为如果存在全面富裕了非常多的点数远大于100而最后来一个可以清空100的操作那不一定要走快速清零的因为那样会需要额外多一次操作。
但是对于绝大多数的情况上述结果是对的在这里也确实可以通过测试样例。
2. 代码实现
给出python代码实现如下
class Solution:def earliestSecondToMarkIndices(self, nums: List[int], changeIndices: List[int]) - int:n, m len(nums), len(changeIndices)changeIndices [x-1 for x in changeIndices]needed sum(nums) nfirst_seen {}for i, x in enumerate(changeIndices):if x not in first_seen and nums[x] 1:first_seen[x] ifirst_seen {v:k for k, v in first_seen.items()}lru_cache(None)def dp(idx, need, extra):if need 1 and extra 1:return idxelif idx m:return mif idx not in first_seen:return dp(idx1, need-1, max(extra-1, 0))i first_seen[idx]if nums[i] 100:return dp(idx1, need-nums[i], extra1)else:return min(dp(idx1, need-1, max(extra-1, 0)), dp(idx1, need-nums[i], extra1))ans dp(0, needed, 0)return ans1 if ans ! m else -1提交代码评测得到耗时1219ms占用内存288.9MB。
3. 算法优化
因为前面也反复强调了上述解法有效但是剪枝的存在使得上述解法并不严谨因此我们在这里摘录一下其他大佬们的解法作为补充有兴趣的读者可以自行研读学习一下这里就让我偷个懒了……
class Solution:def earliestSecondToMarkIndices(self, nums: List[int], changeIndices: List[int]) - int:first_idx [-1] * len(nums)for i in range(len(changeIndices)):if first_idx[changeIndices[i]-1] -1:first_idx[changeIndices[i]-1] ifor i, num in enumerate(nums):if num 1:first_idx[i] -1default_needs sum(nums) len(nums)def is_possible(k):left 0h []pos_count 0flag Falsefor j in range(k, -1, -1):if flag:pos_count 1flag Falseelse:flag Trueleft 1i1 first_idx[changeIndices[j]-1]if i1 j:heapq.heappush(h, [nums[changeIndices[j]-1] - 1, changeIndices[j]-1])if len(h) pos_count:heapq.heappop(h)return default_needs - sum(h1[0] for h1 in h) leftans 0return ansl, r len(nums)-1, len(changeIndices)-1while l r:m (l r) // 2if is_possible(m):r melse:l m 1if l r or not is_possible(l):return -1return l1
