贪心算法 leetcode编程题

ゝ一世哀愁。 2022-12-23 09:55 256阅读 0赞

1. [452. 用最少数量的箭引爆气球][452.]

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。

一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。

给你一个数组 points ，其中 points \[i\] = \[xstart,xend\] ，返回引爆所有气球所必须射出的最小弓箭数。  
示例 1：

输入：points = [[10,16],[2,8],[1,6],[7,12]]
    输出：2
    解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球

**示例 2：**

输入：points = [[1,2],[3,4],[5,6],[7,8]]
    输出：4

**示例 3：**

输入：points = [[1,2],[2,3],[3,4],[4,5]]
    输出：2

解法1:

class Solution:
        def findMinArrowShots(self, points: List[List[int]]) -> int:
            # 贪心法
            if not points:
                return 0
            points = sorted(points, key=lambda x: x[1])
            arrow = points[0][1] # 使用最 右端作为箭
            points_len = len(points)
            count = 1
            for i in range(1, points_len):
                if arrow < points[i][0]: # 不能射
                    count += 1  
                    arrow = points[i][1]  # 换箭
            return count

2. [767. 重构字符串][767.]

给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。

若可行，输出任意可行的结果。若不可行，返回空字符串。

示例 1:

输入: S = "aab"
    输出: "aba"

示例 2:

输入: S = "aaab"
    输出: ""

解法1: 贪心+堆（没用堆，瞎写）

class Solution:
        def reorganizeString(self, S: str) -> str:
            # 贪心策略, 重复最多的字母 出现的次数不能超过（n+1）// 2， 否则 不能 重构字符串
            # 统计字符出现的次数
            S_len = len(S)
            count_s = {}
            for item in S:
                if item in count_s:
                    count_s[item] += 1
                else:
                    count_s[item] = 1
            # pass
            count_s = sorted(count_s.items(), key=lambda x: x[1], reverse=True)
            if count_s[0][1] > (S_len+1)//2:
                return ""
            # 一定能组成， 堆 
            count_s_len = len(count_s)
            count_s_list = [list(item) for item in count_s]
            result = ""
            # print(count_s_list)
            def sum_list(a):
                ss = 0
                for k, v in a:
                    ss += v
                return ss
            while sum_list(count_s_list) != 0:
                i = 0
                i_c = 0 # 计数 2
                while i < len(count_s_list):
                    if i_c < 2:
                        if count_s_list[i][1] > 0:  # 每次都要取出现次数 最大的 次大 两个；
                            result += count_s_list[i][0]
                            count_s_list[i][1] -= 1
                            i_c += 1
                    else:
                        break
                    i += 1
                count_s_list = sorted(count_s_list, key=lambda x: x[1], reverse=True)  # 每次都要重排吗？ 太耗时
            return result

解法2:  不知道哪位大神写的，思路很巧妙！

class Solution:
        def reorganizeString(self, S: str) -> str:
            #思路：排序，后面的数组个数能否填满之间的空隙
            a = list(S)
            b = dict(collections.Counter(a))
            c = sorted(b,key = lambda k : 0 -b[k])
            d = []
            for i in c:
                d += [i] * b[i]
            # print(d)
            ans = [0] * len(a)
            # print(ans)
    
            ans[::2] = d[:len(ans[::2])] #放前一半
            # print(ans)
            ans[1::2] = d[len(ans[::2])::]# 放后一半
            # print(ans)
            if ans[0] == ans[1]:
                return ""
            else:
                return ''.join(ans)

3. [455. 分发饼干][455.]

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g\[i\]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s\[j\] 。如果 s\[j\] >= g\[i\]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

方法1: 贪心策略，

class Solution:
        def findContentChildren(self, g: List[int], s: List[int]) -> int:
            # 贪心算法， 贪心策略: 1. 小饼干先喂饱小胃口
            g = sorted(g)
            s = sorted(s)
    
            g_len = len(g)
            s_len = len(s)
            j = 0
            i = 0 
            while i < g_len and j < s_len:
                while j < s_len  and g[i] > s[j]:
                    j = j + 1
                if j >= s_len:
                    break
                j = j + 1 
                i = i + 1
            return i

方法2:

class Solution:
        def findContentChildren(self, g: List[int], s: List[int]) -> int:
            # 贪心算法， 贪心策略: 1. 小饼干先喂饱小胃口
            g = sorted(g)
            s = sorted(s)
    
            child = 0
            cookie = 0
            while child < len(g) and cookie < len(s):
                if g[child] <= s[cookie]:
                    child += 1
                cookie += 1
            return child

4. [135. 分发糖果][135.]

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。  
相邻的孩子中，评分高的孩子必须获得更多的糖果。  
那么这样下来，老师至少需要准备多少颗糖果呢？

示例 1:

输入: [1,0,2]
    输出: 5
    解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

**示例 2:**

输入: [1,2,2]
    输出: 4
    解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
         第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

解法1: 贪心算法， 贪心表现在： 每次遍历，只考虑并更新相邻一次的大小关系；

class Solution:
        def candy(self, ratings: List[int]) -> int:
            # 两次遍历： 先初始化为 1， 
            # 1. 首先从左向右遍历， 若右边数大于左边数，则 糖果数 更新为 左边糖果数+1；
            # 2. 其次，从右向左遍历，若左变数大于右边数，并且 糖果数不大于右边糖果数，则更新为 右边糖果数+1
            # 贪心策略表现在什么地方呢？： 表现在 每次遍历中，只考虑并更新相邻一侧的大小关系；
            ratings_len = len(ratings)
            result = [1]*ratings_len
            for i in range(ratings_len-1): # 从左向右遍历, 右边大于左边，则右边更新为 左边糖果数+1
                if ratings[i+1] > ratings[i]:
                    result[i+1] = result[i] + 1
            for i in range(ratings_len-1, 0, -1): # 从右向左遍历, 左边大于右边且左边糖果数不大于右边，则左边糖果数更新为 右边+1
                if ratings[i-1] > ratings[i] and result[i-1] <= result[i]:
                    result[i-1] = result[i] + 1
            return sum(result)

5. [435. 无重叠区间][435.]

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意:

可以认为区间的终点总是大于它的起点。  
区间 \[1,2\] 和 \[2,3\] 的边界相互“接触”，但没有相互重叠。  
示例 1:

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

**示例 2:**

输入: [ [1,2], [1,2], [1,2] ]
    
    输出: 2
    
    解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

**示例 3:**

输入: [ [1,2], [2,3] ]
    
    输出: 0
    
    解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

解法1:

class Solution:
        def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
            # 区间的， 按照 右端排序（根据情况进行判定）， 
            if not intervals:
                return 0
            intervals = sorted(intervals, key=lambda x: x[1])
            count = 0
            temp = intervals[0][1]  # 用来比较
            # 按区间右端排序，这样可以选择  符合条件且 区间右端值较小的，可以保留更多的区间；
            for i in range(1, len(intervals)):
                if temp <= intervals[i][0]:  # 后一个左端值 大于等于 前一个右端值，不符合的剔除！
                    temp = intervals[i][1]
                else:
                    # 剔除
                    count += 1
            return count

[452.]: https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/
[767.]: https://leetcode-cn.com/problems/reorganize-string/
[455.]: https://leetcode-cn.com/problems/assign-cookies/
[135.]: https://leetcode-cn.com/problems/candy/
[435.]: https://leetcode-cn.com/problems/non-overlapping-intervals/