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