贪心相关：柠檬水找零、买卖股票的最佳时机、分发饼干、跳跃游戏 ...

柠檬水找零、买卖股票的最佳时机、分发饼干、跳跃游戏 ..."/>

贪心相关：柠檬水找零、买卖股票的最佳时机、分发饼干、跳跃游戏 ...

文章目录

• • 一、柠檬水找零
  • 二、买卖股票的最佳时机
  • 三、买卖股票的最佳时机II
  • 四、分发饼干
  • 五、模拟行走机器人（困难）
  • 六、跳跃游戏
  • 七、跳跃游戏II（困难）

一、柠檬水找零

注意：是按顺序收取，不是先把所有钱都收上来，然后再给别人分别找钱

# 此题的贪心在于收到20，优先用10元的！
class Solution:def lemonadeChange(self, bills: List[int]) -> bool:five = ten = 0for i, v in enumerate(bills):if v == 5:five += 1elif v == 10:if not five:return Falsefive -= 1ten += 1else:if ten and five:ten -= 1five -= 1elif five >= 3:five -= 3else:return Falsereturn True

二、买卖股票的最佳时机

此题不涉及贪心

class Solution:def maxProfit(self, prices: List[int]) -> int:min_pri, max_pro = math.inf, 0for cur in prices:if cur < min_pri:min_pri = curmax_pro = max(max_pro, cur - min_pri)return max_pro# 最小栈 + 单调栈 (其实也就是变相的在维护min price)stack, max_pro = [], 0for cur in prices:if stack and cur > stack[-1]:max_pro = max(max_pro, cur - stack[-1])continuestack.append(cur)return max_pro

三、买卖股票的最佳时机II

# 此题的贪心在于：因为交易次数不受限，因此只要有利可图，就买了再抛售！
class Solution:def maxProfit(self, prices: List[int]) -> int:profit = 0for i in range(1, len(prices)):v = prices[i] - prices[i - 1]if v > 0:profit += vreturn profit

四、分发饼干

'''
为了尽可能满足最多数量的孩子，从贪心的角度考虑，应该按照孩子的胃口从小到大的顺序依次满足每个孩子
且对于每个孩子，应该选择可以满足这个孩子的胃口且尺寸最小的饼干
'''
class Solution:def findContentChildren(self, g: List[int], s: List[int]) -> int:g.sort()s.sort()i = j = count = 0while i < len(g) and j < len(s):if g[i] <= s[j]:count += 1i += 1j += 1else:j += 1return count

五、模拟行走机器人（困难）

此题没有贪心，并且此题的题难读懂！

注意：题目要求的是过程中各点到原点的欧式平方距离的最大值, 而不是终点到原点的欧式平方距离

某点到原点欧式平方距离：x*x+y*y

class Solution:def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:# 四个方向的x，y应该怎么加减!# 这是按照顺时针方向写的，即向右转方向dx = [0, 1, 0, -1]dy = [1, 0, -1, 0]# x、y表示当前机器人的坐标，cur_dir表示当前机器人的面朝方向x = y = cur_dir = 0# map函数式编程，把obstacles中的元素作为参数传入tuple函数中去obstacleSet = set(map(tuple, obstacles)) ans = 0for cmd in commands:if cmd == -2:# 这里有人是(cur_dir + 3)%4，其实不用，因为-1%4就等于3cur_dir = (cur_dir - 1) % 4elif cmd == -1:cur_dir = (cur_dir + 1) % 4else:for _ in range(cmd):if (x + dx[cur_dir], y + dy[cur_dir]) not in obstacleSet:x += dx[cur_dir]y += dy[cur_dir]ans = max(ans, x*x + y*y)return ans

六、跳跃游戏

'''
1. 如果某一个作为 起跳点 的格子可以跳跃的距离是 3，那么表示后面 3 个格子都可以作为 起跳点。
2. 可以对每一个能作为 起跳点 的格子都尝试跳一次，把 能跳到最远的距离 不断更新。
3. 如果可以一直跳到最后，就成功了。
'''
# 此题贪心在于：
# 每个位置都计算自己能达到的最远距离，同时每个位置要判断自己是否可达
# 也就是本位置需要在当前最远能到达的距离中。
class Solution:def canJump(self, nums: List[int]) -> bool:maxPos = 0for i, jump in enumerate(nums):if maxPos >= i: # 此位置能到达，便更新最远位置maxPos = max(maxPos, i + jump)else:return Falsereturn True

七、跳跃游戏II（困难）

'''
由于题目中明确说了假设你总是可以到达数组的最后一个位置
假设没有这个要求，你恐怕就得考虑使用bfs！当然bfs我也做了，超出了时间间隔！如果我们「贪心」地进行正向查找，每次找到可到达的最远位置，就可以在线性时间内得到最少的跳跃次数。例如，对于数组 [2,3,1,2,4,2,3]，初始位置是下标 0，从下标 0 出发，最远可到达下标 2。下标 0 可到达的位置中，下标 1 的值是 3，从下标 1 出发可以达到更远的位置，因此第一步到达下标 1。核心思想：肯定能达到最后一个位置，那么我们只管每一步都选择走的最远，局部最优，那么对于整体肯定也是最优的！即跳跃数最少，因此使用贪心算法程序在遍历的时候不断更新最远距离，难点在于怎么去标记不同层（借用bfs思想）
下面程序的level_end就是用来标记当前层结束的，结束了step++
'''
class Solution:def jump(self, nums: List[int]) -> int:# 贪心算法maxPos = level_end = step = 0# 不用考虑从最后一个位置起跳的情况，所以i < nums.size()-1for i in range(len(nums) - 1):# 由于肯定能到达数组最后一个位置，所以这里不用加 if maxPos >= i:maxPos = max(maxPos, i + nums[i])if i == level_end:level_end = maxPosstep += 1return step