top100-贪心算法

这篇具有很好参考价值的文章主要介绍了top100-贪心算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

第一题

题目链接

121. 买卖股票的最佳时机 - 力扣(LeetCode)

解题思路

1、暴力破解

我们需要找出给定数组中两个数字之间的最大差值,即max(prices[j] - prices[i])

# 此方法会超时
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        ans = 0
        for i in range(len(prices)):
            for j in range(i + 1, len(prices)):
                ans = max(ans, prices[j] - prices[i])
        return ans
2、一次遍历

遍历价格数组一遍,记录历史最低点,然后在每一天考虑这么一个问题:如果我是在历史最低点买进的,那么我今天能赚多少钱

# 此方法会超时
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
       inf = int(1e9)
       minprice = inf
       maxprofit = 0
       for price in prices:
           maxprofit = max(price - minprice,maxprofit)
           minprice = min(price,minprice)

       return maxprofit

第二题

题目链接

55. 跳跃游戏 - 力扣(LeetCode)

解题思路

这样一来,我们依次遍历数组中的每一个位置,并实时维护最远可以到达的距离。对于当前遍历到的位置x,,如果它是在最远可以到达的位置的范围内,那么我们就可以从起点通过若干次跳跃到达该位置,因此我们可以用x + nums[x]更新 最远可以到达的位置。

在遍历的过程中,如果最远可以到达的位置大于等于数组中的最后一个位置,那就说明最后一个位置可达,我们就可以直接返回True作为答案。反之,如果在遍历结束后,最后一个位置仍然不可达,我们就返回False作为答案。

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n,rightmost = len(nums),0
        for i in range(n):
            if i <= rightmost:
                rightmost = max(rightmost,i + nums[i])
                if rightmost >= n -1:
                    return True
        return False

第三题

题目链接

45. 跳跃游戏 II - 力扣(LeetCode)

解题思路

1、如果某一个作为起跳点的格子可以跳跃的距离是3,那么表示后面3个格子都可以作为起跳点。

        可以对每一个能作为起跳点的格子都尝试跳一次,把能跳到最远的距离不断更新。

2、如果从这个起跳点起跳叫做第1次跳跃,那么从后面3个格子起跳都可以叫做第2次跳跃。

3、所以,当一次跳跃结束时,从下一个格子开始,到现在能跳到最远距离,都是下一次跳跃的起跳点。

        跳完一次之后,更新下一次起跳点的范围

        在新的范围内跳,更新能跳到最远的距离

4、记录跳跃次数,如果跳到了终点,就得到了结果。

class Solution:
    def jump(self, nums: List[int]) -> int:
        ans, start, end = 0,0,1
        while end < len(nums):
            maxPos = 0
            for i in range(start,end):
                maxPos = max(maxPos,i + nums[i])
            start = end
            end = maxPos + 1
            ans += 1
        return ans

第四题

题目链接

763. 划分字母区间 - 力扣(LeetCode)文章来源地址https://www.toymoban.com/news/detail-843298.html

解题思路

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last = [0] * 26
        for i,ch in enumerate(s):
            last[ord(ch) - ord("a")] = i
        
        partition = list()
        start = end = 0
        print(last)
        for i, ch in enumerate(s):
            end = max(end,last[ord(ch) - ord("a")])
            if i == end:
                partition.append(end - start + 1)
                start = end + 1
        return partition

到了这里,关于top100-贪心算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode - #85 最大矩形(Top 100)

    本题为 LeetCode 前 100 高频题 本题由于没有合适答案为以往遗留问题,最近有时间将以往遗留问题一一完善。 我们社区陆续会将顾毅( Netflix 增长黑客,《iOS 面试之道》作者,ACE 职业健身教练。 )的 Swift 算法题题解整理为文字版以方便大家学习与阅读。 LeetCode 算法到目前我

    2024年02月10日
    浏览(36)
  • 【Leetcode】top 100 多维动态规划

    62 不同路径 一个机器人位于一个  m x n   网格的左上角,机器人每次只能向下或者向右移动一步,机器人试图达到网格的右下角,问总共有多少条不同的路径? 分析:dp[i][j] 代表走到 (i, j) 的路径总和数 递推规律:dp[i][j] = dp[i-1][j] + dp[i][j-1] 初始条件:dp[0][:] = 1 dp[:][0] = 1

    2024年03月26日
    浏览(47)
  • Leetcode Top 100 Liked Questions(序号105~139)

    题意:根据前序遍历和中序遍历来构造二叉树 要用递归造树,要同时递归左子树和右子树,造树需要左边边界和右边边界 build函数有 树的跟指针, 前序的有左边边界和右边边界,中序的左边边界和右边边界 如果lr return; 因为是先序遍历,所以左子树是先序的第一个,先构

    2024年02月10日
    浏览(33)
  • Leetcode Top 100 Liked Questions(序号75~104)

     题意:红白蓝的颜色排序,使得相同的颜色放在一起,不要用排序 哈希 代码 Runtime 4 ms Beats 28.23% Memory 8.3 MB Beats 9.95% Dutch National Flag Problem荷兰国旗问题; 代码 计数排序 Runtime 0 ms Beats 100% Memory 8.3 MB Beats 41.44% 感觉和我之前做的差不多 代码 双指针 Runtime 0 ms Beats 100% Memory

    2024年02月10日
    浏览(33)
  • Leetcode Top 100 Liked Questions(序号53~74)

    题意:一个数组,找到和最大的子串 我记得好像On的动态规划来做的?但是想不起来了,先死做,用的 前缀和——TLE超时 那就只能想想dp怎么做了 假设dp[i]表示的是以 i 为右端点的最大的子串,dp[0]是自己; i=1时,如果dp[0]小于0,dp[1]=nums[1],否则dp[1]=dp[0]+nums[1] i=2时,如果

    2024年02月12日
    浏览(39)
  • 奖项快报 | ALVA Systems 上榜 《2022 高成长企业 TOP100》!

    近日,《2022 高成长企业 TOP 100》榜单发布,凭借卓越的创新能力与在工业 AR 领域的赋能价值,ALVA Systems 在2022年度高成长企业TOP100大赛活动中脱颖而出,成功入选榜单。  *ALVA Systems 入选榜单 创新驱动,赋能数字经济发展 创办于2009年,高成长企业TOP100榜单经过十余年的沉淀

    2023年04月24日
    浏览(31)
  • Cloud Studio实战——热门视频Top100爬虫应用开发

    最近 Cloud Studio 非常火,我也去试了一下,感觉真的非常方便!我就以Python爬取B站各区排名前一百的视频,并作可视化来给大家分享一下 Cloud Studio !应用链接:Cloud Studio实战——B站热门视频Top100爬虫应用开发 点开一个工作台,选择一个环节,即可在里面编辑代码,不用再担

    2024年02月13日
    浏览(33)
  • [Selenium] 通过Java+Selenium查询某个博主的Top100文章质量分

    通过Java+Selenium查询文章质量分 通过Java+Selenium查询某个博主的Top40文章质量分 通过Java+Selenium查询某个博主的Top100文章质量分 大家好,我是青花,本篇给大家分享一下《通过Java+Selenium查询某个博主的Top100文章质量分》,针对上一章Top40文章,做了简单的优化,在查询博客质量

    2024年02月11日
    浏览(45)
  • 力扣hot100 最长递增子序列 线性DP 贪心 二分

    Problem: 300. 最长递增子序列 时间复杂度: O ( n 2 ) O(n^2) O ( n 2 ) 空间复杂度: O ( n ) O(n) O ( n ) 👨‍🏫 参考题解 时间复杂度: O ( n log ⁡ n ) O(nlog{n}) O ( n lo g n ) 空间复杂度: O ( n ) O(n) O ( n )

    2024年01月20日
    浏览(41)
  • 贪心算法问题实验:贪心算法解决TSP问题

    TSP问题是指旅行商问题,即给定一组城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP困难问题,在运筹学和理论计算机科学中有着广泛的应用。 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最

    2024年02月03日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包