当前位置: 首页 > news >正文

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

文章目录

    • 一、柠檬水找零
    • 二、买卖股票的最佳时机
    • 三、买卖股票的最佳时机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

http://www.taodudu.cc/news/show-6105751.html

相关文章:

  • 干货来了 | SQL 进阶技巧
  • 干货 | SQL 进阶技巧
  • 【LeetCode】两道贪心算法题目-455分发饼干,860柠檬水找零
  • LeetCode455分发饼干
  • 柠檬模拟群面复盘
  • 7-7 快速求和
  • 1.神奇的字符串之快速求和
  • 奔波真是辛苦啊,然而生命终将逝去,只希望当一切都结束的时候,能够没有遗憾吧。
  • 热爱可抵岁月漫长,温柔可挡艰难时光—2020年终总结
  • 经典S Q L语句大全
  • 最美的时光在飞逝,为什么还在努力的路上蹒跚?
  • 时光飞逝,思考,实践,伴我一生的经验
  • 315编辑器
  • 039.简单的文本编辑器
  • mavon-editor编辑器与图片上传
  • 编辑器111
  • 题注中的图一.1变成图1.1
  • MySQL数据库实验(四):E-R图实例讲解
  • (一)1. 数据流图(DFD)概念及画法
  • 如何把word中的多级编号中的题注“图一.1”自动变成“图1.1”
  • 图一:入门篇
  • (宏) Word图片题注“图一-1”转化为“图1-1”
  • app性能测试怎么做
  • PCB布局和绘制的关键操作
  • 什么是CAD的模型和布局?
  • 阿里巴巴矢量图标库icon图标在线引用
  • 精灵随着鼠标的移动而移动
  • 【cocos2D-X】Plist使用 实现 移动精灵多图片动画
  • 移动设备上“精灵图”的制作适配
  • cocos2dx 精灵的移动(2)