ARTS 打卡 第 2 周

发布于: 2020 年 07 月 11 日

Algorithm 一道算法题;

Review 阅读并点评一篇英文文章;

Technique/Tips 是分享一个技术技巧;

Share 是分享一篇有观点和思考的技术文章。

Algorithm

leetcode-122 买卖股票的最佳时机 II

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

 

示例 1:

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
  随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
  注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。
  因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。

示例 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

链接https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

解题思路:

开始被题目迷惑了,以为买和卖不能在同一天,结果走入了死胡同,后来看了别人的思路,才明白这个题的意思。本题采用贪心算法,即在每次操作时选择当前的最优解,累计操作多次后,就可以得到整体的最优解。

这个题的焦点就在于,我们有两种操作思路:

1.每天都进行股票操作,那么累计利润;

2.只取这段时间的股票价格最大和最小值,计算利润。

根据上面两个图可以看到,如果价格连续上涨,则每天操作的累积利润等于一次操作(股票最大和最小值)的利润;如果价格有涨有跌,那么每天操作只要涨价就卖,那么累积利润大于一次操作的利润。

综上,这个题的思路就有了:

1.从第二天开始,遍历每天的价格,只要比前一天贵,就卖出股票,得出当天利润;

2.累加每天的利润得到最大利润。

class Solution {
public:
int maxProfit(vector<int>& prices) {
int size = prices.size();
if(size < 2)
{
return 0;
}
int maxprofit = 0;
for(int i = 1; i < size; ++i)
{
if(prices[i] > prices[i - 1])
{
maxprofit += prices[i] - prices[i - 1];
}
}
return maxprofit;
}
};

Review

本周的英文阅读文章:understanding iops latency and storage performance理解IOPS、延迟和存储性能

这篇文章详细的介绍了IOPS,IOPS虽然能反应磁盘的性能,但是脱离了响应延迟和请求队列大小而只看IOPS是没有意义的。如果一块磁盘的IOPS是1000,响应延迟是10ms,那么它的性能很可能是好于IOPS是5000,响应延迟50ms的磁盘的。

文中利用顾客在超市结账的例子,详细的描述了响应延迟是怎么影响IOPS的,当有顾客(IO)在排队等待响应的时候,典型的响应延迟是要大于单个请求的响应延迟的,因为有多个请求在排队。

那磁盘是怎么处理瞬间的大量随机请求呢?原因是磁盘可以更智能的管理请求队列,让IO请求顺序的完成。

这篇文章一下子让我对磁盘的IO性能有了更清晰的认识。

Technique/Tips

几种流控算法的介绍,这个分享来自极客时间--每日一课

目前,流量控制已经成为互联网应用的必要条件,主要的流控算法分为以下三种:

1.固定窗口算法(在固定时间窗口按照阈值限流);

优点:实现简单,

缺点:时间窗口内突发流量,会有流量踩踏。

2.漏桶算法(定义一个有一定容量的桶,超过桶容量的流量将被丢弃);

特点:强行限制输入速度,输出速度(数据处理)速率不变,削峰填谷,

缺点:直接丢弃超额流量。

3.令牌桶算法(定义一个有一定容量的令牌桶,并以一定速度放入令牌,流量到来时首先请求令牌,有可用令牌则处理流量,否则丢弃流量)。

特点:依赖令牌,能处理突发流量。

这三种算法中,令牌桶算法是最强选择;但是在实际使用中,也要按照应用特性来选择,如果是比较简单的应用,可以使用固定窗口算法。

Share

这次继续分享耗子叔的文章:RUST语言的编程范式

这篇文章详细的介绍了RUST语言的特点,给我的总体印象就是:如果你对Rust的概念认识的不完整,你完全写不出程序,那怕就是很简单的一段代码。这逼着程序员必需了解所有的概念才能编码。但是,另一方面也表明了这门语言并不适合初学者。

看完这篇文章,感觉被实力劝退RUST,但是依然收获很多,从另一个方面了解了现在最新的编程语言是什么样子的。

用户头像

Scotty

关注

我爱编程 Always Be Coding 2017.12.05 加入

11年程序员,4年java web全栈,7年服务端C++

评论

发布
暂无评论
ARTS 打卡 第2周