Leetcode——贪心算法之无重叠区间,种花问题,最长递增序列

小鱼儿 2023-01-10 10:17 193阅读 0赞

[直通车biu][biu]

思路：

官网说的很难懂(没有通俗易懂)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70][]

在选择要保留区间时，区间的结尾十分重要：选择的区间结尾越小，余留给其它区间的空间 就越大，就越能保留更多的区间。因此，我们采取的贪心策略为，优先保留结尾小且不相交的区 间。

具体实现方法为，先把区间按照结尾的大小进行增序排序，每次选择结尾**最小**且和**前一个选择**的区间**不重叠**的区间。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70 1][]

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

[605 种花问题][605]

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

思路：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70 2][]

首先这里我用的是**连跳两格**的方法，因为如果遇到1,那么下一格子一定是0，这是毋庸置疑的（规则限定），所以如果遇到最后一个格子，或者下个格子不是1，果断填充

class Solution:
        def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
            if not flowerbed: return False
            m = len(flowerbed)
            i = 0
            while i < m:
                if flowerbed[i] == 0 :
                    if i == m-1 or flowerbed[i+1] == 0:
                        n -= 1
                    else:
                        i += 1
                i += 2
            return n <= 0

[最长递增序列][Link 1]

过程：

1.  count 为当前元素峰值，ans为最大峰值
2.  初始化 count = 1
3.  从 0 位置开始遍历，遍历时根据前后元素状态判断是否递增，递增则 count++，递减则 count=1
4.  如果 count>ans，则更新 ans
5.  直到循环结束

class Solution:
        def findLengthOfLCIS(self, nums: List[int]) -> int:
            if not nums: return 0
            count = 1
            ans = 1
            lens = len(nums)
            for i in range(lens - 1):
                if nums[i] < nums[i + 1]:
                    count += 1
                else:
                    if count > ans:
                        ans = count
                    count = 1
            return max(count,ans)

[biu]: https://leetcode-cn.com/problems/non-overlapping-intervals/solution/wu-zhong-die-qu-jian-by-leetcode-solutio-cpsb/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70]: /images/20221119/4b91df717e11408aa7ff6ee53a53089f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210123165055992.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg==,size_16,color_FFFFFF,t_70
[605]: https://leetcode-cn.com/problems/can-place-flowers/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210123202631573.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg==,size_16,color_FFFFFF,t_70
[Link 1]: https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/