14.最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明: 所有输入只包含小写字母a-z。
最长公共前缀
本来以为很简单的题，还是做了很长时间，很多情况都没有充分考虑，最大的问题就是数组越界问题
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。
方法一、暴力求解
Part 1
Part 2
方法一的时间复杂度
收获：
1.判断条件中，要充分利用短路来做题，第22，28，38，47行都是用这个条件，如果将两个条件调换位置，则会出现数组越界。
2.剔除数组中连续的重复元素，用del 来删除其中的重复元素，删除后，后面的元素会自动补齐，第14～19行是实现过程。
方法二.贪心算法
122. 买卖股票的最佳时机 II
方法二的时间复杂度
收获：
方法二跳过了寻找极值的这个方法（方法一）,而是采用局部最大化，将局部利润相加，就是在一个时间段获得的最大的利润。
贪心算法采用局部最优解就是整体最优解来解决问题
具体实现是只用考虑列表中递增子序列，用子序列中的最后一个元素减去第一个元素，得到每一次购买到抛售的过程（最优子结构），然后找到列表中所有的最优子结构，将所有最优子结构累加即为问题的整体最优解。（第18～24行是最优子结构表达式）
此问题在刚刚做的时候，用了两个while循环，运行在leetcode中显示超时，于是直接continue不符合子结构的过程，大大减少了运行时间。（第15～16行)
从时间复杂度表中可以看出，采用贪心算法后，效率大大提高了，从吊车尾华丽丽转身为top了
网友评论