今天开始刷题！希望自己可以坚持下去

今天再加一道题：
128. Longest Consecutive Sequence
我自己先用O（nlogn）解出来的（sort），对于O（N）的方法，一个知识点是将array变成set==》set和hashtable一样，查找元素的时间复杂度为O（1）
这道题还需要注意这里的时间复杂度，看着像是N的平方，但是是O（n+n）=O（n）

补上昨天的8月30号：
42. Trapping Rain Water
（1）DP：ans+=min（max_right,max_left）-height[curr]
（2）两个指针：两个指针分别指向左端最大的数和右端最大的数（以左右两端为起点），然后找出小的那个，如：若左边最大数小，则左边指针往前移，然后指针指的height与左端最大数之间的大小，若小于左端最大，则ans+=max_left-height[left],若大于，则max_left=height[left]
154. Find Minimum in Rotated Sorted Array II
该方法与153. Find Minimum in Rotated Sorted Array的不同在于其有重复的数字出现，因此，处理nums[left]==nums[mid]时略有不同
第二遍：
153. Find Minimum in Rotated Sorted Array（做的很顺利）
442. Find All Duplicates in an Array（不是很顺利，过阵子再看一遍）

8月31日：
309. Best Time to Buy and Sell Stock with Cooldown
DP：buy[i] = max(sell[i-2]-price, buy[i-1])
        sell[i] = max(buy[i-1]+price, sell[i-1])
第二遍：
238. Product of Array Except Self
121. Best Time to Buy and Sell Stock(只能交易一次，那就取最小的buy，maxprofit=max（maxprofit，sell-buy）)
122. Best Time to Buy and Sell Stock II（可以多次交易。取局部最小最大的差的和）

9月1日：
"123. Best Time to Buy and Sell Stock III
DP: 定义四个变量：hold1,hold2;release1,release2
188. Best Time to Buy and Sell Stock IV
分情况：当K>=len(prices)的时候，相当于不限制交易，解决方案同122. Best Time to Buy and Sell Stock II
否则：定义profit=[[0]*len(prices) for in range(k+1)]==》第k行j列表示：第k+1次卖股票时的利润；然后：
for i in range(1,k+1):     #表示第i次交易
            tempmax=-prices[0]   
            for j in range(1,leng):
                profit[i][j]=max(profit[i][j-1],tempmax+prices[j])  #表示第j天如果进行第i次交易时的最大利润
                tempmax=max(tempmax,profit[i-1][j-1]-prices[j])   #表示第j天买入的话，最小成本是多少。profit[i-1][j-1]-prices[j]表示第j-1天进行第i-1次交易的利润---只有第j-1天进行第i-1次交易了，才能在第j天买入股票。
        return profit[k][leng-1]
注：a=[[0]*3]*5与a=[[0]*3 for i in range(5)]之间是有区别的
第二遍：
714. Best Time to Buy and Sell Stock with Transaction Fee
方法1：DP，方法同309，buy[i] = max(sell[i-1]-price, buy[i-1])； sell[i] = max(buy[i-1]+price-fee, sell[i-1])
方法2：定义变量state+=price-last_price; 当state>fee时，probit+=state-fee，state=fee；else，若state<0：state=0"

这几题股票写了之后就通了~

9月3日：
"137. Single Number II
540. Single Element in a Sorted Array==>本题要注意mid的奇偶性
第二遍：
136. Single Number--》该题的重点是只有一个数字出现1次
689. Maximum Sum of 3 Non-Overlapping Subarrays==>该题的重点是求出来sumarr，同时用DP的方法求出来left和right的最大值的索引==》掌握的不好，需要再刷"

vtiaocao 发表于 2018-9-2 01:05
这几题股票写了之后就通了~

是啊   一下子把股票全都刷了。。。

689之前不是写过了吗。看来之前没掌握呢……(我也是)

vtiaocao 发表于 2018-9-3 08:19
689之前不是写过了吗。看来之前没掌握呢……(我也是)

就算是第二遍刷，也是写的很吃力吃力吃力。。。过几天需要继续刷。。。

9月3日：
"434. Number of Segments in a String
A.strip('!')=> 用于移除字符串头尾指定的字符（默认为空格）  a.split('!')==>通过指定分隔符对字符串进行切片，如果参数num 有指定值，则仅分隔 num 个子字符串
该处需要注意，strip和split均不改变字符串A本身，只有将其进行赋值，才能得到想要的字符串--strip（或array--split)
537. Complex Number Multiplication
165. Compare Version Numbers
本题重点是split（'.'）以及将短的字符后面补上0
221. Maximal Square
1. Brute Forece: 重点是如何找square
2. DP：该睡觉了，明天继续看答案
第二遍：
179. Largest Number
需要掌握的知识点：
（1）定义sort的key：
class sortkey(str):
     def __lt__(x,y):
          return x+y>y+x    表示若x+y>y+x，返回True,否则返回False
A.sort(key=sortkey)
（2）nums=map(str,nums);
(3) "" "".join(nums)"