做淘客网站用备案吗,做网站如何团队分工,我有项目想找投资人,汕头市网络优化推广平台废话不多说#xff0c;喊一句号子鼓励自己#xff1a;程序员永不失业#xff0c;程序员走向架构#xff01;本篇Blog的主题是【贪心算法】#xff0c;使用【数组】这个基本的数据结构来实现#xff0c;这个高频题的站点是#xff1a;CodeTop#xff0c;筛选条件为…废话不多说喊一句号子鼓励自己程序员永不失业程序员走向架构本篇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并执行贪心策略所有上涨交易日都买卖赚到所有利润所有下降交易日都不买卖永不亏钱
设 tmp 为第 i-1 日买入与第 i 日卖出赚取的利润即 tmp prices[i] - prices[i - 1] 当该天利润为正 tmp 0则将利润加入总利润 profit当利润为 0 或为负则直接跳过遍历完成后返回总利润 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;}
}复杂度分析
时间复杂度遍历了一遍数组所以时间复杂度为ON 空间复杂度没有借助额外空间空间复杂度为O1
拓展知识动态规划与贪心算法
动态规划
动态规划Dynamic Programming简称DP是一种解决复杂问题的算法设计技术常用于优化问题和组合问题的求解。它通过将原问题分解成子问题并保存子问题的解以避免重复计算从而提高算法的效率。动态规划通常用于解决具有重叠子问题和最优子结构性质的问题。
动态规划的基本思想可以总结为以下几个步骤 定义问题的状态首先要明确定义问题的状态这些状态可以用来描述问题的各种情况。 找到状态转移方程状态转移方程描述了问题之间的联系即如何从一个状态转移到另一个状态。这通常涉及到问题的递归关系通过这个关系可以从较小规模的子问题得到更大规模的问题的解。 初始化状态确定初始状态的值这通常是问题规模最小的情况下的解。 自底向上或自顶向下求解动态规划可以采用自底向上Bottom-Up或自顶向下Top-Down的方式求解问题。自底向上是从最小的状态开始逐步计算直到得到最终问题的解自顶向下是从最终问题开始递归地计算子问题的解直到达到最小状态。 根据问题的要求从状态中找到最终解。
动态规划常见的应用领域包括 最长公共子序列问题在两个序列中找到一个最长的共同子序列用于比较字符串相似性。 背包问题在给定一定容量的背包和一组物品的情况下选择一些物品放入背包使得物品的总价值最大或总重量不超过背包容量。 最短路径问题求解图中两点之间的最短路径如Dijkstra算法和Floyd-Warshall算法。 硬币找零问题给定一组硬币面额和一个目标金额找到使用最少数量的硬币组合成目标金额。 斐波那契数列问题求解斐波那契数列的第n个数通过动态规划可以避免重复计算。
动态规划是一种强大的问题求解方法但它并不适用于所有类型的问题。在使用动态规划时需要仔细分析问题的性质确保问题具有重叠子问题和最优子结构性质以确保动态规划算法能够有效地解决问题。
贪心算法
贪心算法Greedy Algorithm是一种常用的问题求解策略通常用于解决最优化问题如最短路径、最小生成树、背包问题等。贪心算法的基本思想是每一步都选择当前状态下的最优解而不考虑全局的最优解希望通过局部最优的选择最终达到全局最优。贪心算法通常是一种高效的方法但并不是所有问题都适合使用贪心算法因为有些问题的最优解不一定可以通过贪心选择得到。
贪心算法的一般步骤如下 定义问题的优化目标明确问题的约束条件。 从问题的初始状态开始通过一系列选择每次选择局部最优解更新当前状态。 检查是否满足问题的约束条件和终止条件。如果不满足则回到第2步继续选择如果满足则算法结束。 对于某些问题需要证明贪心选择的局部最优解确实能够导致全局最优解这需要数学证明或者举出反例。
以下是一些常见的问题可以使用贪心算法解决 最小生成树问题如Kruskal算法和Prim算法用于寻找无向图中的最小生成树。 最短路径问题如Dijkstra算法用于寻找图中两点之间的最短路径。 背包问题如分数背包问题和0/1背包问题可以使用贪心算法进行求解。 活动选择问题如贪心选择活动安排最多的问题可以使用贪心算法求解。
需要注意的是并非所有问题都适合使用贪心算法因为有些问题的最优解可能需要全局搜索或者动态规划等其他算法。因此在应用贪心算法之前需要仔细分析问题的特点和性质以确定贪心算法是否合适。
动态规划与贪心算法区别
动态规划Dynamic Programming和贪心算法Greedy Algorithm都是常见的问题求解策略但它们在问题求解时有很大的区别适用于不同类型的问题和场景。
区别 最优子结构性质 动态规划动态规划问题通常具有最优子结构性质即全局最优解可以通过子问题的最优解来构造。动态规划通常涉及到将问题划分为重叠的子问题然后利用这些子问题的解来构建全局最优解。贪心算法贪心算法通常涉及到每一步选择当前状态下的最优解但不一定具有最优子结构性质。贪心算法通常是通过一系列局部最优选择来达到全局最优但不能保证一定能够得到全局最优解。 选择的灵活性 动态规划在动态规划中可以在每个子问题中考虑多种选择并计算每种选择的代价或价值然后选择最优的。通常需要一个状态转移方程来描述问题的子结构和递归关系。贪心算法贪心算法在每一步都选择当前状态下的最优解不考虑其他选择的影响。它通常适用于问题具有贪心选择性质的情况即通过局部最优选择能够得到全局最优解。
问题解决场景 动态规划适用场景 当问题的最优解可以通过子问题的最优解来构造时通常使用动态规划。典型问题包括 最短路径问题如Dijkstra算法最长公共子序列问题背包问题如0/1背包问题编辑距离问题 需要存储和重用子问题的解通常使用表格或数组来实现。 贪心算法适用场景 当问题具有贪心选择性质即通过每一步的局部最优选择能够达到全局最优时可以使用贪心算法。典型问题包括 最小生成树问题如Prim算法和Kruskal算法哈夫曼编码问题活动选择问题货币找零问题 贪心算法通常更简单和高效但不能解决所有问题因为它没有全局的视野。
总之动态规划和贪心算法是两种不同的问题求解策略根据问题的特性和要求选择合适的算法非常重要。有些问题可以同时使用这两种策略的思想即使用贪心算法的局部最优性来设计动态规划的状态转移方程。
