• 【算法训练-贪心算法 一】买卖股票的最佳时机II


    废话不多说,喊一句号子鼓励自己:程序员永不失业,程序员走向架构!本篇Blog的主题是【贪心算法】,使用【数组】这个基本的数据结构来实现,这个高频题的站点是:CodeTop,筛选条件为:目标公司+最近一年+出现频率排序,由高到低的去牛客TOP101去找,只有两个地方都出现过才做这道题(CodeTop本身汇聚了LeetCode的来源),确保刷的题都是高频要面试考的题。
    在这里插入图片描述

    名曲目标题后,附上题目链接,后期可以依据解题思路反复快速练习,题目按照题干的基本数据结构分类,且每个分类的第一篇必定是对基础数据结构的介绍

    买卖股票的最佳时机II【MID】

    难度升级,股票可以反复买卖,不是只买卖一次,还是求最大收益

    题干

    在这里插入图片描述

    解题思路

    整体使用贪心算法实现:

    • 对于单独交易日: 设今天价格 p1 、明天价格 p2 ,则今天买入、明天卖出可赚取金额 p2−p1(负值代表亏损)。
    • 对于连续上涨交易日: 设此上涨交易日股票价格分别为 p1,p2,…,pn,则第一天买最后一天卖收益最大,即 pn−p1 ;等价于每天都买卖,即 pn−p1=(p2−p1)+(p3−p2)+…+(pn−pn−1)p_n - p_1=(p_2 - p_1)+(p_3 - p_2)+…+(p_n - p_{n-1})
    • 对于连续下降交易日: 则不买卖收益最大,即不会亏钱。

    在这里插入图片描述
    遍历整个股票交易日价格列表 price,并执行贪心策略:所有上涨交易日都买卖(赚到所有利润),所有下降交易日都不买卖(永不亏钱)

    1. 设 tmp 为第 i-1 日买入与第 i 日卖出赚取的利润,即 tmp = prices[i] - prices[i - 1] ;
    2. 当该天利润为正 tmp > 0,则将利润加入总利润 profit;当利润为 0 或为负,则直接跳过;
    3. 遍历完成后,返回总利润 profit

    代码实现

    给出代码实现基本档案

    基本数据结构数组
    辅助数据结构
    算法贪心算法
    技巧

    其中数据结构、算法和技巧分别来自:

    • 10 个数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
    • 10 个算法:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
    • 技巧:双指针、滑动窗口、中心扩散

    当然包括但不限于以上

    import java.util.*;
    
    
    public class Solution {
        /**
         * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
         *
         * 计算最大收益
         * @param prices int整型一维数组 股票每一天的价格
         * @return int整型
         */
        public int maxProfit (int[] prices) {
            // 1 定义总利润
            int maxProfit = 0;
            for (int i = 1; i < prices.length; i++) {
                // 2 获取当天利润
                int curProfit = prices[i] - prices[i - 1];
                // 3 只有当天利润为正值才计入总利润
                maxProfit = Math.max(curProfit, 0) + maxProfit;
            }
    
            return maxProfit;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    复杂度分析

    时间复杂度:遍历了一遍数组,所以时间复杂度为O(N)
    空间复杂度:没有借助额外空间,空间复杂度为O(1)

    拓展知识:动态规划与贪心算法

    动态规划

    动态规划(Dynamic Programming,简称DP)是一种解决复杂问题的算法设计技术,常用于优化问题和组合问题的求解。它通过将原问题分解成子问题,并保存子问题的解,以避免重复计算,从而提高算法的效率。动态规划通常用于解决具有重叠子问题和最优子结构性质的问题。

    动态规划的基本思想可以总结为以下几个步骤:

    1. 定义问题的状态:首先要明确定义问题的状态,这些状态可以用来描述问题的各种情况。

    2. 找到状态转移方程:状态转移方程描述了问题之间的联系,即如何从一个状态转移到另一个状态。这通常涉及到问题的递归关系,通过这个关系可以从较小规模的子问题得到更大规模的问题的解。

    3. 初始化状态:确定初始状态的值,这通常是问题规模最小的情况下的解。

    4. 自底向上或自顶向下求解:动态规划可以采用自底向上(Bottom-Up)或自顶向下(Top-Down)的方式求解问题。自底向上是从最小的状态开始逐步计算,直到得到最终问题的解;自顶向下是从最终问题开始,递归地计算子问题的解,直到达到最小状态。

    5. 根据问题的要求,从状态中找到最终解

    动态规划常见的应用领域包括:

    1. 最长公共子序列问题:在两个序列中找到一个最长的共同子序列,用于比较字符串相似性。

    2. 背包问题:在给定一定容量的背包和一组物品的情况下,选择一些物品放入背包,使得物品的总价值最大或总重量不超过背包容量。

    3. 最短路径问题:求解图中两点之间的最短路径,如Dijkstra算法和Floyd-Warshall算法。

    4. 硬币找零问题:给定一组硬币面额和一个目标金额,找到使用最少数量的硬币组合成目标金额。

    5. 斐波那契数列问题:求解斐波那契数列的第n个数,通过动态规划可以避免重复计算。

    动态规划是一种强大的问题求解方法,但它并不适用于所有类型的问题。在使用动态规划时,需要仔细分析问题的性质,确保问题具有重叠子问题和最优子结构性质,以确保动态规划算法能够有效地解决问题。

    贪心算法

    贪心算法(Greedy Algorithm)是一种常用的问题求解策略,通常用于解决最优化问题,如最短路径、最小生成树、背包问题等。贪心算法的基本思想是每一步都选择当前状态下的最优解,而不考虑全局的最优解,希望通过局部最优的选择最终达到全局最优。贪心算法通常是一种高效的方法,但并不是所有问题都适合使用贪心算法,因为有些问题的最优解不一定可以通过贪心选择得到。

    贪心算法的一般步骤如下:

    1. 定义问题的优化目标,明确问题的约束条件

    2. 从问题的初始状态开始,通过一系列选择,每次选择局部最优解,更新当前状态

    3. 检查是否满足问题的约束条件和终止条件。如果不满足,则回到第2步继续选择;如果满足,则算法结束。

    4. 对于某些问题,需要证明贪心选择的局部最优解确实能够导致全局最优解,这需要数学证明或者举出反例。

    以下是一些常见的问题,可以使用贪心算法解决:

    1. 最小生成树问题:如Kruskal算法和Prim算法用于寻找无向图中的最小生成树。

    2. 最短路径问题:如Dijkstra算法用于寻找图中两点之间的最短路径。

    3. 背包问题:如分数背包问题0/1背包问题,可以使用贪心算法进行求解。

    4. 活动选择问题:如贪心选择活动安排最多的问题,可以使用贪心算法求解。

    需要注意的是,并非所有问题都适合使用贪心算法,因为有些问题的最优解可能需要全局搜索或者动态规划等其他算法。因此,在应用贪心算法之前,需要仔细分析问题的特点和性质,以确定贪心算法是否合适。

    动态规划与贪心算法区别

    动态规划(Dynamic Programming)和贪心算法(Greedy Algorithm)都是常见的问题求解策略,但它们在问题求解时有很大的区别,适用于不同类型的问题和场景。

    区别:

    1. 最优子结构性质:

      • 动态规划:动态规划问题通常具有最优子结构性质,即全局最优解可以通过子问题的最优解来构造。动态规划通常涉及到将问题划分为重叠的子问题,然后利用这些子问题的解来构建全局最优解。
      • 贪心算法:贪心算法通常涉及到每一步选择当前状态下的最优解,但不一定具有最优子结构性质。贪心算法通常是通过一系列局部最优选择来达到全局最优,但不能保证一定能够得到全局最优解。
    2. 选择的灵活性:

      • 动态规划:在动态规划中,可以在每个子问题中考虑多种选择,并计算每种选择的代价或价值,然后选择最优的。通常需要一个状态转移方程来描述问题的子结构和递归关系。
      • 贪心算法:贪心算法在每一步都选择当前状态下的最优解,不考虑其他选择的影响。它通常适用于问题具有"贪心选择性质"的情况,即通过局部最优选择能够得到全局最优解。

    问题解决场景:

    1. 动态规划适用场景:

      • 当问题的最优解可以通过子问题的最优解来构造时,通常使用动态规划。典型问题包括:
        • 最短路径问题(如Dijkstra算法)
        • 最长公共子序列问题
        • 背包问题(如0/1背包问题)
        • 编辑距离问题
      • 需要存储和重用子问题的解,通常使用表格或数组来实现。
    2. 贪心算法适用场景:

      • 当问题具有贪心选择性质,即通过每一步的局部最优选择能够达到全局最优时,可以使用贪心算法。典型问题包括:
        • 最小生成树问题(如Prim算法和Kruskal算法)
        • 哈夫曼编码问题
        • 活动选择问题
        • 货币找零问题
      • 贪心算法通常更简单和高效,但不能解决所有问题,因为它没有全局的视野。

    总之,动态规划和贪心算法是两种不同的问题求解策略,根据问题的特性和要求选择合适的算法非常重要。有些问题可以同时使用这两种策略的思想,即使用贪心算法的局部最优性来设计动态规划的状态转移方程。

  • 相关阅读:
    黑客技术(网络安全)自学2024
    【0115】libpq连接PostgreSQL数据库
    23 张图细讲使用 Devtron 简化 K8S 中应用开发
    Linux简单安装ffmpeg 实现用PHP压缩音频
    vue动态修改css样式
    全新跑分软件GeekRUN-7问世
    搭建一款实用的个人IT工具箱——it-tools
    Hdu 2022多校训练(5) Slipper
    鸿蒙 gnss 发起定位流程
    828华为云征文 | 华为云Flexus X实例柔性算力助力中小企业和开发者
  • 原文地址:https://blog.csdn.net/sinat_33087001/article/details/133435340