当前位置：首页 > article >正文

✅DAY27贪心算法 | 455.分发饼干 | 376. 摆动序列 | 53. 最大子序和

article 2024/11/19 5:26:59

一、贪心算法

核心理念是每一步都做出局部最优选择，以期最终得到全局最优解。它通常用于求解一些最优化问题，例如最小生成树、最短路径、背包问题等。

二、贪心算法的步骤

1. 定义选择标准：确定每一步如何选择当前最优解。

2. 验证贪心策略的正确性：分析问题是否满足贪心算法的条件，确保贪心选择可以得到最优解。

3. 迭代选择：从初始状态开始，每一步按照选择标准做出决策，直到找到问题的完整解决方案。

三、贪心算法的优缺点

优点：

• 简单且高效：贪心算法通常实现简单，运行速度较快。

• 适用性强：适用于许多最优化问题，例如图算法中的最小生成树和最短路径。

缺点：

• 不保证全局最优解：并非所有问题都能通过贪心算法获得最优解。尤其是涉及多个约束条件的复杂问题，贪心选择可能导致非最优解。

• 适用场景有限：只有当问题满足最优子结构和无后效性时，贪心算法才能得到全局最优解。

455. 分发饼干

解题思路：需要找出有几个满足饼干>小孩，尽量用大的饼干满足较大的小孩

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()  # 小孩的胃口
        s.sort()  # 饼干的大小
        index = len(s) - 1  # 从最后一个饼干开始
        result = 0
        # 从胃口最大的孩子开始遍历
        for i in range(len(g) - 1, -1, -1):
            # 如果当前饼干满足孩子的胃口，分配饼干并记录结果
            if index >= 0 and s[index] >= g[i]:
                result += 1
                index -= 1  # 使用掉一个饼干，向前移动
        return result

解题思路：就从小到大尝试，满足则把小孩的index+1，最后返回index

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        index = 0
        for i in range(len(s)):
            if index < len(g) and g[index] <= s[i]:
                index += 1
        return index

376. 摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列。

解题思路：保留峰值，把单调坡上的中间元素删除

计算 prediff（nums[i] - nums[i-1]）和 curdiff（nums[i+1] - nums[i]），如果prediff < 0 && curdiff > 0 或者 prediff > 0 && curdiff < 0 此时就有波动就需要统计。

本题要考虑三种情况：

情况一：上下坡中有平坡
情况二：数组首尾两端
情况三：单调坡中有平坡

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        if len(nums) <= 1: 
            return len(nums)
        
        curDiff, preDiff = 0, 0
        result = 1  # 记录峰值个数
        
        for i in range(len(nums) - 1):
            curDiff = nums[i + 1] - nums[i]
            # 检查摆动峰值
            if (preDiff <= 0 and curDiff > 0) or (preDiff >= 0 and curDiff < 0):
                result += 1
                preDiff = curDiff
        
        return result

53. 最大子数组和

暴力递归

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        result = float('-inf')
        count = 0
        for i in range(len(nums)):
            count = 0
            for j in range(i, len(nums)):
                count += nums[j]
                result = max(result, count)
        return result

贪心：遇到和为负数时，就重置，重新开始计算下个区间和

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = nums[0]
        current_sum = 0

        for num in nums:
            if current_sum < 0:
                current_sum = 0
            current_sum += num
            max_sum = max(current_sum, max_sum)

        return max_sum

查看全文

http://www.kler.cn/a/399675.html