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