ARTS 打卡第 2 周

 关注
发布于: 2020 年 07 月 11 日
Algorithm 一道算法题；
Review 阅读并点评一篇英文文章；
Technique/Tips 是分享一个技术技巧；
Share 是分享一篇有观点和思考的技术文章。
﻿
Algorithmleetcode-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，但是依然收获很多，从另一个方面了解了现在最新的编程语言是什么样子的。
﻿