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

简介: 【经典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语言
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
10 1
|
5天前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
1月前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
17天前
|
算法
力扣经典150题第十五题:分发糖果
力扣经典150题第十五题:分发糖果
12 0
|
24天前
|
人工智能 算法 搜索推荐
蓝桥杯宝藏排序题目算法(冒泡、选择、插入)
以下是内容的摘要: 本文介绍了三种排序算法:冒泡排序、选择排序和插入排序。冒泡排序通过不断交换相邻的逆序元素逐步排序,最坏情况下需要 O(n^2) 次比较。选择排序在每轮中找到剩余部分的最小元素并放到已排序序列的末尾,同样具有 O(n^2) 时间复杂度。插入排序则是将每个元素插入到已排序序列的正确位置,时间复杂度也是 O(n^2),但空间复杂度为 O(1)。
|
1月前
|
容器
【LeetCode刷题】栈和队列题目练习~
【LeetCode刷题】栈和队列题目练习~
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总(4)
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总
|
1月前
|
存储 算法
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总(1)
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总
|
1月前
|
算法
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
|
1月前
|
算法
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏