天字第一条:永远不要首先尝试贪心算法,并尝试证明它是对的。而要使用动态规划推出一个算法,然后可以尝试简化到贪心算法。
尤其是在面试中,基本不会出现贪心算法,太 tricky 了。如果一个面试官问了一个题目,并且他只会用贪心算法解,那么这个面试官水平也一般,这样的公司不去也罢。
相比动态规划来说,贪心算法一般来说:
- 要求条件更严格,也就是贪心选择条件;
- 时间复杂度往往更低,能达到线性时间复杂度。
贪心选择性质:每一步都选择局部最优解,而局部最优解恰好是全局最优解。贪婪一般需要预排序,证明贪婪成立可以采用数学归纳法,或者证明不会有更好的方法
区间问题
合并、排序区间也是一个常见的问题。
例题
LeetCode 56
LeetCode 57 合并区间
这道题关键之处在于合并后,把剩余的区间直接加上来,这样就不用考虑不少特殊情况了。
class Solution:
def insert(self, intervals, newInterval):
ans = []
start, end = newInterval
remainder = 0
for x, y in intervals:
if start <= y:
if end < x:
break # 找到了结尾了
start = min(start, x)
end = max(end, y)
else:
ans.append([x, y])
remainder += 1
ans.append([start, end])
ans += intervals[remainder:]
return ans