关于算法:基础算法系列-贪心算法之力扣热度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