贪心算法 leetcode编程题

ゝ一世哀愁。 2022-12-23 09:55 275阅读 0赞
  1. 452. 用最少数量的箭引爆气球

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

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

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

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

示例 2：

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

示例 3：

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

解法1:

  1. class Solution:
  2.     def findMinArrowShots(self, points: List[List[int]]) -> int:
  3.         # 贪心法
  4.         if not points:
  5.             return 0
  6.         points = sorted(points, key=lambda x: x[1])
  7.         arrow = points[0][1] # 使用最 右端作为箭
  8.         points_len = len(points)
  9.         count = 1
  10.         for i in range(1, points_len):
  11.             if arrow < points[i][0]: # 不能射
  12.                 count += 1  
  13.                 arrow = points[i][1]  # 换箭
  14.         return count
  1. 767. 重构字符串

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

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

示例 1:

  1. 输入: S = "aab"
  2. 输出: "aba"

示例 2:

  1. 输入: S = "aaab"
  2. 输出: ""

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

  1. class Solution:
  2.     def reorganizeString(self, S: str) -> str:
  3.         # 贪心策略, 重复最多的字母 出现的次数不能超过（n+1）// 2， 否则 不能 重构字符串
  4.         # 统计字符出现的次数
  5.         S_len = len(S)
  6.         count_s = {}
  7.         for item in S:
  8.             if item in count_s:
  9.                 count_s[item] += 1
  10.             else:
  11.                 count_s[item] = 1
  12.         # pass
  13.         count_s = sorted(count_s.items(), key=lambda x: x[1], reverse=True)
  14.         if count_s[0][1] > (S_len+1)//2:
  15.             return ""
  16.         # 一定能组成， 堆 
  17.         count_s_len = len(count_s)
  18.         count_s_list = [list(item) for item in count_s]
  19.         result = ""
  20.         # print(count_s_list)
  21.         def sum_list(a):
  22.             ss = 0
  23.             for k, v in a:
  24.                 ss += v
  25.             return ss
  26.         while sum_list(count_s_list) != 0:
  27.             i = 0
  28.             i_c = 0 # 计数 2
  29.             while i < len(count_s_list):
  30.                 if i_c < 2:
  31.                     if count_s_list[i][1] > 0:  # 每次都要取出现次数 最大的 次大 两个；
  32.                         result += count_s_list[i][0]
  33.                         count_s_list[i][1] -= 1
  34.                         i_c += 1
  35.                 else:
  36.                     break
  37.                 i += 1
  38.             count_s_list = sorted(count_s_list, key=lambda x: x[1], reverse=True)  # 每次都要重排吗？ 太耗时
  39.         return result

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

  1. class Solution:
  2.     def reorganizeString(self, S: str) -> str:
  3.         #思路：排序，后面的数组个数能否填满之间的空隙
  4.         a = list(S)
  5.         b = dict(collections.Counter(a))
  6.         c = sorted(b,key = lambda k : 0 -b[k])
  7.         d = []
  8.         for i in c:
  9.             d += [i] * b[i]
  10.         # print(d)
  11.         ans = [0] * len(a)
  12.         # print(ans)
  14.         ans[::2] = d[:len(ans[::2])] #放前一半
  15.         # print(ans)
  16.         ans[1::2] = d[len(ans[::2])::]# 放后一半
  17.         # print(ans)
  18.         if ans[0] == ans[1]:
  19.             return ""
  20.         else:
  21.             return ''.join(ans)
  1. 455. 分发饼干

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

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

方法1: 贪心策略， 

  1. class Solution:
  2.     def findContentChildren(self, g: List[int], s: List[int]) -> int:
  3.         # 贪心算法， 贪心策略: 1. 小饼干先喂饱小胃口
  4.         g = sorted(g)
  5.         s = sorted(s)
  7.         g_len = len(g)
  8.         s_len = len(s)
  9.         j = 0
  10.         i = 0 
  11.         while i < g_len and j < s_len:
  12.             while j < s_len  and g[i] > s[j]:
  13.                 j = j + 1
  14.             if j >= s_len:
  15.                 break
  16.             j = j + 1 
  17.             i = i + 1
  18.         return i

方法2:

  1. class Solution:
  2.     def findContentChildren(self, g: List[int], s: List[int]) -> int:
  3.         # 贪心算法， 贪心策略: 1. 小饼干先喂饱小胃口
  4.         g = sorted(g)
  5.         s = sorted(s)
  7.         child = 0
  8.         cookie = 0
  9.         while child < len(g) and cookie < len(s):
  10.             if g[child] <= s[cookie]:
  11.                 child += 1
  12.             cookie += 1
  13.         return child
  1. 135. 分发糖果

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

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

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

示例 1:

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

示例 2:

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

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

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

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

注意:

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

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

示例 2:

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

示例 3:

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

解法1:

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

发表评论

表情：
评论列表 （有 0 条评论，275人围观）

还没有评论，来说两句吧...

相关阅读

    相关 贪心算法刷题

    1.递增数组 题目链接：[递增数组][Link 1] 题目介绍： > 牛牛有一个数组array，牛牛可以每次选择一个连续的区间，让区间的数都加1，他想知道把这

    快来打我*快来打我*/ 0 赞/ 78 阅读