【文件属性】:
文件名称:leetcode安卓-leetcode:遇险代码
文件大小:184KB
文件格式:ZIP
更新时间:2021-06-30 02:42:12
系统开源
leetcode安卓
[toc]
leetcode
刷题笔记
1.
贪心算法
贪心算法证明
面对题目,初步判定可以用贪心算法,则尝试举出几个反例,看看是否提出的贪心算法是错的
如果举不出反例,则基本是对的。可以使用贪心。接下来可以用反证法证明贪心算法的正确性。
在第i步,按照提出的贪心算法策略选择某个元素,或者作出某个决定。
反证,假设当前第i步提出的决定不是最优的,则。。。顺着往下推,发现矛盾。说明贪心算法策略是正确的。
贪心
+
动态维护最远距离
预先扫描数组并统计一遍信息(频率、个数、最后一次出现的位置等),可以帮助降低复杂度
动态维护最右端最大距离
贪心
+
仅考虑左右相邻位置
考虑左右位置的复杂版。两次扫描,一次仅考虑左邻居,一次考虑右邻居,然后合并考虑结果
贪心
+
interval
特点:
这类题一般要对【区间排序】。可能按照左端点排序,也可能按照右端点。这是关键问题。
给n个区间,返回需要移除的区间的最小数量,使得剩下的区间不重叠。
移除k,反过来想,就是选择n
-
k个不重叠的区间,使得n
-
k最大。把删除问题变成插入问题。
给定n个元素,重建成n个。我们不一定要新