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


相关文章
|
9天前
|
机器学习/深度学习 算法 数据可视化
基于Qlearning强化学习的机器人迷宫路线搜索算法matlab仿真
本内容展示了基于Q-learning算法的机器人迷宫路径搜索仿真及其实现过程。通过Matlab2022a进行仿真,结果以图形形式呈现,无水印(附图1-4)。算法理论部分介绍了Q-learning的核心概念,包括智能体、环境、状态、动作和奖励,以及Q表的构建与更新方法。具体实现中,将迷宫抽象为二维网格世界,定义起点和终点,利用Q-learning训练机器人找到最优路径。核心程序代码实现了多轮训练、累计奖励值与Q值的可视化,并展示了机器人从起点到终点的路径规划过程。
39 0
|
5月前
|
算法 数据可视化 安全
基于DWA优化算法的机器人路径规划matlab仿真
本项目基于DWA优化算法实现机器人路径规划的MATLAB仿真,适用于动态环境下的自主导航。使用MATLAB2022A版本运行,展示路径规划和预测结果。核心代码通过散点图和轨迹图可视化路径点及预测路径。DWA算法通过定义速度空间、采样候选动作并评估其优劣(目标方向性、障碍物距离、速度一致性),实时调整机器人运动参数,确保安全避障并接近目标。
227 68
|
8月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
84 0
|
7月前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
145 4
|
8月前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
79 2
|
8月前
|
人工智能 算法 Java
【搜索算法】数字游戏(C/C++)
【搜索算法】数字游戏(C/C++)
|
10月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
114 6
|
10月前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
106 1
|
10月前
|
存储 算法 Java
LeetCode经典算法题:预测赢家+香槟塔java解法
LeetCode经典算法题:预测赢家+香槟塔java解法
123 1

热门文章

最新文章