乐趣区

关于算法:基础算法系列-贪心算法之力扣热度TOP5贪心策略记录

TOP1 跳跃游戏

给定一个非负整数数组,你最后位于数组的第一个地位。数组中的每个元素代表你在该地位能够跳跃的最大长度。判断你是否可能达到最初一个地位。

例如对于 [2,3,1,1,4] 返回真,对于 [3,2,1,0,4] 返回假。

贪婪策略 1 :如果地位 i 能够达到,那么 i 之前的所有地位肯定能够达到。

def solution(nums):
  reach = 0
  for i in range(len(nums)):
    if i > reach:
      return False
    reach = max(reach, i + nums[i])
  return True

贪婪策略 2 :向前遍历记录能够达到起点的最前的地位。

def solution(nums):
  start = len(nums) - 1
  for i in range(len(nums)-1, -1, -1):
    if i + nums[i] >= start:
      start = i
  return 0 == start

TOP2 跳跃游戏Ⅱ

给定一个非负整数数组,你最后位于数组的第一个地位。数组中的每个元素代表你在该地位能够跳跃的最大长度。你的指标是应用起码的跳跃次数达到数组的最初一个地位。假如你总是能够达到数组的最初一个地位。

例如对于 [2,3,1,1,4] 返回 2。

贪婪策略 1 :每一次记录能到起点的最前的地位,并更新起点地位。

def solution(nums):
  aim = len(nums) - 1
  cnt = 0
  while aim:
    for i in range(len(nums)):
      if i + nums[i] >= aim:
        aim = i
        cnt += 1
        break
  return cnt

贪婪策略 2 :记录地位 i 步长范畴内哪个地位能达到的间隔最远,此步就走哪个地位。

def solution(nums):
  aim, edge, ans = 0, 0, 0
  for i in range(len(nums)-1):
    aim = max(aim, i + nums[i])
    if i == edge:
      ans += 1
      edge = aim
  return ans

TOP3 交易股票的最佳时机 II

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你能够尽可能地实现更多的交易(屡次交易一支股票)。你不能同时参加多笔交易(你必须在再次购买前发售掉之前的股票)。

例如对于 [7,1,5,3,6,4] 返回 7,对于 [1,2,3,4,5] 返回 4。

贪婪策略:只记录上升段收益。

def solution(prices):
  profit = 0
  for i in range(1, len(prices)):
    if prices[i] > prices[i-1]:
      profit += prices[i] - prices[i-1]
  return profit

TOP4 宰割均衡字符串

在一个「均衡字符串」中,’L’ 和 ‘R’ 字符的数量是雷同的。给出一个均衡字符串 s,请你将它宰割成尽可能多的均衡字符串。返回能够通过宰割失去的均衡字符串的最大数量。

例如对于 ”RLRRLLRLRL” 返回 4,对于 ”RLLLLRRRLR” 返回 3。

贪婪策略:遍历到均衡状态则后果加一。

def solution(s):
  ans, balance = 0, 0
  for i in s:
    balance += 1 if i == 'L' else -1
    if not balance: ans += 1
  return ans

TOP5 散发饼干

假如你是一位很棒的家长,想要给你的孩子们一些小饼干。然而,每个孩子最多只能给一块饼干。对每个孩子 i,都有一个胃口值 gi,这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 sj。如果 sj >= gi,咱们能够将这个饼干 j 调配给孩子 i,这个孩子会失去满足。你的指标是尽可能满足越多数量的孩子,并输入这个最大数值。

贪婪策略:优先满足胃口小的孩子。

def solution(g, s):
  g.sort()
  s.sort()
  i, j = 0, 0
  while i < len(g) and j < len(s):
    if g[i] <= s[j]: i += 1
    j += 1
  return i
退出移动版