【经典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

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