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


相关文章
|
算法 Go 索引
【LeetCode 热题100】45:跳跃游戏 II(详细解析)(Go语言版)
本文详细解析了力扣第45题“跳跃游戏II”的三种解法:贪心算法、动态规划和反向贪心。贪心算法通过选择每一步能跳到的最远位置,实现O(n)时间复杂度与O(1)空间复杂度,是面试首选;动态规划以自底向上的方式构建状态转移方程,适合初学者理解但效率较低;反向贪心从终点逆向寻找最优跳点,逻辑清晰但性能欠佳。文章对比了各方法的优劣,并提供了Go语言代码实现,助你掌握最小跳跃次数问题的核心技巧。
798 15
|
算法
Leetcode第45题(跳跃游戏II)
这篇博客文章讨论了如何使用贪心算法解决LeetCode第45题“跳跃游戏II”,目的是找到使用最少跳跃次数到达数组末尾的策略。
507 8
Leetcode第45题(跳跃游戏II)
LeetCode第55题跳跃游戏
LeetCode第55题"跳跃游戏"的解题方法,通过记录当前最远可达到的位置并判断每个位置是否可达以及能否到达末尾,有效解决了跳跃至数组末尾的可行性问题。
LeetCode第55题跳跃游戏
|
存储 人工智能 算法
从零掌握贪心算法Java版:LeetCode 10题实战解析(上)
在算法世界里,有一种思想如同生活中的"见好就收"——每次做出当前看来最优的选择,寄希望于通过局部最优达成全局最优。这种思想就是贪心算法,它以其简洁高效的特点,成为解决最优问题的利器。今天我们就来系统学习贪心算法的核心思想,并通过10道LeetCode经典题目实战演练,带你掌握这种"步步为营"的解题思维。
|
算法 Go
【LeetCode 热题100】55:跳跃游戏(详细解析)(Go语言版)
本篇解析详细讲解了 LeetCode 热题 55——跳跃游戏(Jump Game)。通过判断是否能从数组起点跳至终点,介绍了两种高效解法:贪心算法和反向思维。贪心法通过维护最远可达位置 `maxReach` 实现一次遍历,时间复杂度 O(n),空间复杂度 O(1);反向法则从终点回溯,判断是否可到达起点。两者均简洁高效,适合面试使用。延伸题目如 LeetCode 45 进一步提升挑战。
695 7
|
算法
优化策略:揭秘钢条切割与饼干分发的算法艺术
本文探讨了钢条切割与饼干分发两个经典算法问题,展示了算法在解决实际问题中的应用。钢条切割问题通过动态规划方法,计算出不同长度钢条的最大盈利切割方式,考虑焊接成本后问题更为复杂。饼干分发问题则采用贪心算法,旨在尽可能多的喂饱孩子,分别讨论了每个孩子一块饼干和最多两块饼干的情况。这些问题不仅体现了数学的精妙,也展示了工程师的智慧与创造力。
414 4
Leetcode第55题(跳跃游戏)
LeetCode第55题“跳跃游戏”要求判断在一个非负整数数组中,从第一个位置出发,是否能够到达最后一个位置,其中每个位置的元素代表可跳跃的最大长度。
242 0
|
机器学习/深度学习 算法 机器人
【水下图像增强融合算法】基于融合的水下图像与视频增强研究(Matlab代码实现)
【水下图像增强融合算法】基于融合的水下图像与视频增强研究(Matlab代码实现)
1076 0
|
数据采集 分布式计算 并行计算
mRMR算法实现特征选择-MATLAB
mRMR算法实现特征选择-MATLAB
631 2
|
传感器 机器学习/深度学习 编解码
MATLAB|主动噪声和振动控制算法——对较大的次级路径变化具有鲁棒性
MATLAB|主动噪声和振动控制算法——对较大的次级路径变化具有鲁棒性
551 3

热门文章

最新文章