第五周arts
Algorithm-dp算法题
121. Best Time to Buy and Sell Stock
题意理解：给定一个股票交易数组，每个值代表当天买卖的价格，如果最多只允许一次买卖交易（先买一次再卖出一次），问最大收益是多少？
比如[7,1,5,3,6,4], 可以明显看出在第二天买入（1元），第五天卖出（6元），取得最大收益5元解题思路：
方法1：采用暴力破解，O(n^2)
方法2：O(n), 采用dp，dp[i]代表在第i天卖出所取得的最大收益，关键就是找出与dp[i-1]的关系。考察下dp[i]在哪天买入，要么在第i-1天买入，要么与dp[i-1]在相同的一天买入，从而得到递归公式如下：
dp[i] = Math.max(dp[i-1]+prices[i]-prices[i-1], prices[i]-prices[i-1])下面就可以开始写程序了，dp[i]数组是可以用两个变量来代替的
class Solution {
public int maxProfit(int[] prices) {
//如果是1，则只能买入不能卖出、或者不交易
if (prices == null || prices.length <= 1) {
return 0;
}
int preMax = 0, currMax = 0, max = Integer.MIN_VALUE;
for (int i = 1; i < prices.length; i++) {
currMax = Math.max(preMax + prices[i] - prices[i - 1], prices[i] - prices[i - 1]);
preMax = currMax;
max = Math.max(max, currMax);
}
return max > 0 ? max : 0;
}
}
- 参考discuss之后的思考
看discuss发现还有一种理解的方法，就是对于第i天卖出要取得最大值，就是去找第i天之前的买入最小值，这种思路也是ok的
Review
继续分布式入门相关的学习
Scalability, Availability & Stability Patterns
看了个大概，粗略画了个脑图，东西有点多，有点懵，等把后面的知识一点一点学起来再回来对照看。
Tip
看耗叔群里分享的IntegerCache很有意思的设计，自己也借此专门看了下Integer的源码：
- Integer类初始化时会将[-128,max]范围的整数缓存到IntegerCache类的一个Integer[]数组中，其中max默认是127，可以在jvm启动的时候指定max的值
- 当调用Integer.valueOf(int)时，会先去缓存数组中拿，在范围内则返回缓存数组中的值，不在则new一个Integer对象
- 当采用Integer val = new Integer(x), 则不会重缓存中拿
- Integer val = x; 也是先重缓存数组中拿，没拿到才new一个Integer对象
Share
人要活得舒舒服服，不存在的，人其实没有轻松活着的福分。
需要给自己定一个稍高一点的目标，这样才有方向的努力，有的放矢，给自己定个小目标，年后达到BAT的社招要求。
一般来说，说没有时间干什么，那都是借口，如果你真的热爱是一定会挤出时间来做的，如何形成热爱呢？慢慢养成习惯，一旦养成习惯就会自然而然的坚持下来了，让自己看到正向成果，就会慢慢变成爱好的。
把arts养成一种习惯，越不想写越要逼迫自己写，越要逼迫自己不拖欠，只要养成自律的习惯，你就已经超越了大多数人了。
