# 【经典LeetCode算法题目专栏分类】【第5期】贪心算法：分发饼干、跳跃游戏、模拟行走机器人

### 分发饼干

class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
# 贪心算法
res = 0
g.sort()
s.sort()
i = 0
j = 0
while i < len(g) and j < len(s):
# 饼干满足胃口
if g[i] <= s[j]:
res += 1
i += 1
j += 1
else:
# 饼干不满足胃口，查找下一个饼干
j += 1
return res

### 跳跃游戏

class Solution:
def canJump(self, nums: List[int]) -> bool:
# 贪心算法
reach_index = len(nums) - 1 # 表示能够到达的索引位置
for i in range(len(nums)-1,-1,-1):
# 从后往前遍历，如果满足下述条件说明能够达到当前索引
if i + nums[i] >= reach_index:
reach_index = i
return reach_index == 0
class Solution:
def canJump(self, nums: List[int]) -> bool:
if nums == [0]: return True
maxDist = 0 # 能够达到的最远距离
end_index = len(nums)-1
for i, jump in enumerate(nums):
# maxDist >= i表示能够达到当前索引位置，并且从当前索引开始
if maxDist >= i and i+jump > maxDist:
maxDist = i+jump
if maxDist >= end_index:
return True
return False

### 跳跃游戏2

class Solution:
def jump(self, nums: List[int]) -> int:
end = 0  # end 表示当前能跳的边界
maxPosition = 0
steps = 0
for i in range(len(nums) - 1):
# 找能跳的最远的
maxPosition = max(maxPosition, nums[i] + i);
if i == end: #遇到边界，就更新边界，并且步数加一
end = maxPosition;
steps += 1
return steps;

### 模拟行走机器人

class Solution:
def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
if not commands:
return 0
# 索引0,1,2,3分别表示北，东，南，西
direx = [0, 1, 0, -1]
direy = [1, 0, -1, 0]
curx, cury, curdire, ans = 0, 0, 0, 0
com_len, obs_len = len(commands), len(obstacles)
obstacle_set = {(obstacles[i][0], obstacles[i][1]) for i in range(obs_len)}  # 变为集合，使判断是否有障碍物更快

for i in range(com_len):
if commands[i] == -1: # 向右转90度
curdire = (curdire +1) % 4
elif commands[i] == -2: # 向左转90度
curdire = (curdire + 3) %4
else: #  1 <= x <= 9: 向前移动x个单位长度
for j in range(commands[i]):
# 试图走出一步，并判断是否遇到了障碍物
nx = curx + direx[curdire]
ny = cury + direy[curdire]
# 当前坐标不是障碍物，计算并存储的最大欧式距离的平方做比较
if (nx, ny) not in obstacle_set:
curx = nx
cury = ny
ans = max(ans, curx*curx + cury*cury)
else:
# 是障碍点，被挡住了，停留，智能等待下一个指令，那可以跳出当前指令了。
break
return ans

|
20天前
|
C语言

10 1
|
5天前
|

8 0
|
1月前
|

【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题：翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题：翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
32 1
|
17天前
|

12 0
|
24天前
|

19 0
|
1月前
|

【LeetCode刷题】栈和队列题目练习~
【LeetCode刷题】栈和队列题目练习~
34 0
|
1月前
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总（4）
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总
14 0
|
1月前
|

【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总（1）
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总
19 0
|
1月前
|

【经典LeetCode算法题目专栏分类】【第11期】递归问题：字母大小写全排列、括号生成
【经典LeetCode算法题目专栏分类】【第11期】递归问题：字母大小写全排列、括号生成
14 0
|
1月前
|

【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集：括号生成、岛屿问题、扫雷游戏
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集：括号生成、岛屿问题、扫雷游戏
16 0