当前位置: 首页 > news >正文

童美童程儿童编程价格站长工具seo综合查询论坛

童美童程儿童编程价格,站长工具seo综合查询论坛,adobe dreamweaver cs6,酒店网站策划书事情是这样的,突然兴起的我在letcode刷题 121. 买卖股票的最佳时机122. 买卖股票的最佳时机 II123. 买卖股票的最佳时机 III 以上三题。 1. 121. 买卖股票的最佳时机 1.1. 暴力遍历,两次遍历 1.1.1. 算法代码 public class Solution {public int Ma…

事情是这样的,突然兴起的我在letcode刷题

  • 121. 买卖股票的最佳时机
  • 122. 买卖股票的最佳时机 II
  • 123. 买卖股票的最佳时机 III

以上三题。

1. 121. 买卖股票的最佳时机

在这里插入图片描述

1.1. 暴力遍历,两次遍历

1.1.1. 算法代码

public class Solution {public int MaxProfit(int[] prices) {int profitValue=0;for(int i=0;i<prices.Length;i++){for(int j=i+1;j<prices.Length;j++){if(prices[j]>prices[i]){if(prices[j]-prices[i]>profitValue){profitValue=prices[j]-prices[i];}}}}return profitValue;}
}

上述代码的逻辑为两次遍历,后一个值比前一个值大,并使用哨兵变量profitValue记录最大差值。

1.1.2. 算法复杂度

  • 时间复杂度: O ( n 2 ) = n ∗ ( n − 1 ) 2 O(n^2)=\frac {n*(n-1)}{2} O(n2)=2n(n1)
  • 空间复杂度: O ( 1 ) O(1) O(1),因为只有哨兵变量profitValue

1.1.3. 算法问题

前面我们讲到,这个时间复杂度是 O ( n 2 ) O(n^2) O(n2),是一个指数函数。

那么在数据非常大的时候,其根据时间复杂度可以知道,其复杂度非常的高,如leetcode的超时案例

[886,729,539,474,5,653,588,198,313,111,38,808,848,364,819,747,520,568,583,253,605,442,779,903,217,284,927,33,859,75,418,612,174,316,167,40,945,740,174,279,985,133,38,919,528,844,101,291,673,561,.......
中间有3万个数值
.......561,644,484,868,53,936,186,35,219,84,455,971,922,862,434,553,948,857,491,622,162,934,66,486,569,690,596,506,452,635,690]

其时间复杂度是: 30000 ∗ 29999 / 2 = 449985000 30000*29999/2=449985000 3000029999/2=449985000,其计算数值大的可怕。

1.2. 一次遍历

1.2.1. 算法代码

public class Solution {public int MaxProfit(int[] prices) {int minprice = int.MaxValue;int maxprofit = 0;for (int i = 0; i < prices.Length; i++) {if (prices[i] < minprice) {minprice = prices[i];} else if (prices[i] - minprice > maxprofit) {maxprofit = prices[i] - minprice;}}return maxprofit;}
}

其算法,基本思路是:在最低点购入,在最高点卖出,由于for循环是从0开始的,所以其每一次minprice是当前时点前最低点购入值,故此算法可靠

1.2.2. 算法复杂度

  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( 1 ) = 2 O(1)=2 O(1)=2

2.2 122. 买卖股票的最佳时机 II

在这里插入图片描述

第一题相较比较简单,而第二题中增加了一个限定:可以购买多次,只是手上最多只有一支股票

2.1. 贪心算法

2.1.1. 算法代码

public class Solution {public int MaxProfit(int[] prices) {int ans = 0;int n = prices.Length;for (int i = 1; i < n; ++i) {int diffPrice=prices[i] - prices[i - 1];if(diffPrice>0){ans += diffPrice;}}return ans;}
}

2.1.2. 算法思路与步骤

只要后一天的价格比今天高,那么我今天就买,后一天就卖。

在这里插入图片描述

2.1.3. 算法复杂度

  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( 1 ) = 2 O(1)=2 O(1)=2

2.2. 动态规划算法

2.2.1. 算法代码

public class Solution {public int MaxProfit(int[] prices) {if (prices.Length < 2) {return 0;}int[] OwnStocks=new int[prices.Length];int[] NoStocks=new int[prices.Length];OwnStocks[0]=-prices[0];NoStocks[0]=0;for(int i=1;i<prices.Length;i++){OwnStocks[i]=Math.Max(OwnStocks[i-1],NoStocks[i-1]-prices[i]);NoStocks[i]=Math.Max(NoStocks[i-1],OwnStocks[i-1]+prices[i]);}return NoStocks[prices.Length-1];}
}

2.2.2. 算法思路与步骤

  • 由于不可以同时存在多支股票,所以每天只有可能有两种状态有股票没有股票
  • 第一天存在股票=0-第一天股票价值;第一天不存在股票=0(没有购买或者当天售出)
  • 后续每一天,当天有股票的最大利益=Math.Max(前一天有股票的值,前一天没有股票的值-当天股票值[购买股票])
  • 后续每一天,当前没有股票的最大利益=Math.Max(前一天没有股票的值,前一天有股票的值+当天股票值[卖出股票]`)

图解如下:

在这里插入图片描述

2.2.3. 算法复杂度

  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( n ) = 2 n O(n)=2n O(n)=2n

2.3. 123. 买卖股票的最佳时机 III

在这里插入图片描述

2.3.1. 动态规划算法

这一题就和第二题的动态规划类似,只是第二题是两个状态,而第三题是四个状态。

  • 没有买入
  • 第一次买入,没有卖出
  • 第一次买出,没有卖入
  • 第二次买入,没有卖出
  • 第二次买出

由于没有买入全程是0所以不做考虑,列出了5种,但实际上只有4种状态。

2.3.2. 算法代码

public class Solution {public int MaxProfit(int[] prices) {if(prices.Length<2){return 0;}int oneBuy=-prices[0];int oneSale=0;int twoBuy=-prices[0];int twoSale=0;for(int i=1;i<prices.Length;i++){oneBuy=Math.Max(oneBuy,-prices[i]);oneSale=Math.Max(oneSale,oneBuy+prices[i]);twoBuy=Math.Max(twoBuy,oneSale-prices[i]);twoSale=Math.Max(twoSale,twoBuy+prices[i]);}return twoSale;}
}

2.3.3. 算法复杂度

  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( 1 ) = 4 O(1)=4 O(1)=4
http://www.hengruixuexiao.com/news/23426.html

相关文章:

  • 南昌比较好的网站设计百度热词
  • 网站建设开发的规划流程抖音推广怎么收费
  • wordpress sql过滤点金推广优化公司
  • 做非法集资资讯的网站营销培训内容有哪些
  • 用vue.js做网站的好处收录排名好的发帖网站
  • 目前做那些网站能致富百度竞价排名怎么做
  • php开发网站 用java做后台国际新闻军事最新消息
  • 网站让百度收录应该怎么做适合小学生的最新新闻
  • ui培训班大概多少钱seo算法培训
  • 通辽做网站哪家好电商线上推广
  • 网站是做java还是c网络营销专业
  • wordpress关注公众号登录项目优化seo
  • 站长工具seo域名解析不了成都seo技术经理
  • 如何做网站宣传域名解析网站
  • 玉山电商网站建设社群营销怎么做
  • 服装网站建设平台真正免费的网站建站
  • 做初中题赚钱的网站郑州网络公司
  • 网站上线具体流程品牌网络推广外包
  • 凌晨三点播放的视频叫什么网站怎么优化排名
  • 大兴 网站建设凡科建站登录
  • 做网站找王思奇网站seo设计方案案例
  • wordpress破解插件放心用吗seo研究中心论坛
  • 做网单哪个网站最好用社群营销案例
  • 简述网站建设的标准惠州seo外包公司
  • 怎样在微信做产品网站个人免费自助建站网站
  • 成都的网站设计公司价格免费网络推广
  • wordpress文章上作者seoul是哪个国家
  • 阿克苏网站建设公司优化搜索关键词
  • 电子商务网站建设规划教案培训心得简短50字
  • 跳网站查询的二维码怎么做的独立站seo推广