当前位置:   article > 正文

【算法训练-贪心算法 一】买卖股票的最佳时机II_买卖股票的最佳时机ii(贪心)java

买卖股票的最佳时机ii(贪心)java

废话不多说,喊一句号子鼓励自己:程序员永不失业,程序员走向架构!本篇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算法)
      • 哈夫曼编码问题
      • 活动选择问题
      • 货币找零问题
    • 贪心算法通常更简单和高效,但不能解决所有问题,因为它没有全局的视野。

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

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Cpp五条/article/detail/635907
推荐阅读
相关标签
  

闽ICP备14008679号