wqshr12345/leetcode-

leetcode-'s Issues

关于买卖股票问题

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

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

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

示例 1:

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

思路：
本质上，还是要深刻理解贪心算法。贪心算法的过程就是：
从问题的某一初始解出发   
while (能朝给定总目标前进一步)        
 do            选择当前最优解作为可行解的一个解元素；    
由所有解元素组合成问题的一个可行解。

在这个问题里面，我的总目标就是：赚的最多钱数。那么，我不要考虑每一次赚多少钱！我只要考虑，我这次能赚钱就ok！当数组前进时，只要我能赚钱（即prices[i+1]>prices[i]），那么这个就是当下的最优解，我把它加到总的解的集合中。让数组不断前进，直到最后！
所以，能理解我不管这次赚多少钱，我只要能赚钱就ok（可能某些情况下我这次的赚钱会使我总的赚钱数不如我这次不赚钱多，但这不是贪心算法需要考虑的），才是理解贪心算法的关键！

关于跳跃问题

问题描述：给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
示例 2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

解题思路：
这个题，第一时间想到的是递归回溯，就是从数组的第一个位置开始，针对这个位置上的值，从0开始往后推导，如果中间推导到一个不可能到达最后位置的位置，那么就回溯，继续别的推导。思路很简单，唯一的缺点是，贼鸡儿慢！时间复杂度是2的n次方，详细推导见leetcode。
然后又开始想别的方法，比如添加一个记忆表来优化，并从后往前遍历。先给每个位置赋予一个boolean变量，初始所有都是false（除了最后一个是good）。从最后一个开始往前遍历，如果这个位置可以到达一个good位置，那么把这个位置设为good。如果0的位置是good，那么说明可以到达最后一个位置。
然而这个方法也是可以优化的，我们想想，我遍历过程中，每次判断实际上只是判断了从0到num[i]中，最左边的那个good是否能到达，没有考虑所有的后面的good，所以我直接用一个指针来指向最左边的good，这样不仅不用boolean数组，而且遍历判断的时候不用递增地去一个个比较，而是直接和这个指针比较就ok。