leetcode3_435 and 605

leetcode学习算法之贪心算法：

435. 无重叠区间
436. 种花问题

435. 无重叠区间-题目描述
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
注意 只在一点上接触的区间是 不重叠的。例如 [1, 2] 和 [2, 3] 是不重叠的。

示例 :
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

代码

class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:intervals.sort(key = lambda x: x[1])removed, prev_end = 0, intervals[0][1]for i in range(1, len(intervals)):if prev_end > intervals[i][0]:removed += 1else:prev_end = intervals[i][1]return removed

调用测试

intervals = [[1,2],[2,3],[3,4],[1,3]]
# 创建 Solution 类的实例
solution = Solution()
# 调用方法
result = solution.eraseOverlapIntervals(intervals)
# 输出结果
print("你需要移除", result, "个区间")

这一题直接使用作者书里面的源代码进行解题。
贪心策略是：按照右端点从小到大排序，每次保留右端点最小且不与前一个保留区间重叠的区间，遇到重叠就删除当前区间（即不更新 prev_end）。

605. 种花问题-题目描述
假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false 。

示例 :
输入：flowerbed = [1,0,0,0,1], n = 1
输出：true

代码

class Solution:def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:# 判断第一个位置和最后一个if len(flowerbed) >1 :if flowerbed[0] == 0 and flowerbed[1] == 0:n = n - 1flowerbed[0] = 1if flowerbed[-1] == 0 and flowerbed[-2] == 0:n = n - 1flowerbed[-1] = 1else:if flowerbed[0] == 0:n = n - 1flowerbed[0] = 1for i in range(1, len(flowerbed) - 1):if flowerbed[i - 1] == 0 and flowerbed[i] == 0 and flowerbed[i + 1] == 0:n = n -1flowerbed[i] = 1if n > 0:return Falseelse:return True

完整代码

from typing import List
class Solution:def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:# 判断第一个位置和最后一个if len(flowerbed) >1 :if flowerbed[0] == 0 and flowerbed[1] == 0:n = n - 1flowerbed[0] = 1if flowerbed[-1] == 0 and flowerbed[-2] == 0:n = n - 1flowerbed[-1] = 1else:if flowerbed[0] == 0:n = n - 1flowerbed[0] = 1for i in range(1, len(flowerbed) - 1):if flowerbed[i - 1] == 0 and flowerbed[i] == 0 and flowerbed[i + 1] == 0:n = n -1flowerbed[i] = 1if n > 0:return Falseelse:return True
flowerbed = [0,0,0,0,1]
n = 2
# 创建 Solution 类的实例
solution = Solution()
# 调用方法
result = solution.canPlaceFlowers(flowerbed, n)
# 输出结果
print("你需要移除", result, "个区间")

这一题自己的想法是：通过从左至右判断列表中的节点是否满足要求，满足要求就对n进行减法。最后判断n是否小于1确实种入n朵花。
原来的代码是先判断列表除第一个和最后一个节点是否满足，最处理列表的第一个和最后一个节点，但是存在部分测试用例不同通过。后面调整代码为先判断第一个节点，测试用例全部通过。我犯错的原因是没有严格从左到右处理，而是先处理中间节点。此外，要注意列表长度是否大于1，否则遍历两个节点时出现超出范围。