算法练习Day26 （Leetcode/Python-贪心算法）-Toy模板网

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

122. Best Time to Buy and Sell Stock II

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

思路：可以无数次买入卖出一支股票，求最大收益。那么只要每两天之间的股票是见涨的，就应该买入。用一个for循环遍历就可以了。

每两天是一个交易单元，局部最优->全局最优，即贪心算法。

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        result = 0
        if len(prices) <= 1:
            return result
        for i in range(1, len(prices)):
            result += max(0, prices[i]-prices[i-1])
        return result

55. Jump Game

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

思路：每次都可以跳<=当前格子数值的步数，判断最后是否可以到达终点。因为接下来小于等于当前格子数值的格子都是理论上可以到达的。那么就看最大的coverage是不是包含终点就可以了，不用纠结到底选择了哪一个格子。文章来源地址https://www.toymoban.com/news/detail-771330.html

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

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