leetcode second round 8/20

today's mission: 155-127
155: min stack
属于数据结构设计题，怎样利用已有的数据结构设计出带有新功能的数据结构。

154: find minimum in rotated sorted arrayII
153: find minimum in rotated sorted array
这两个题目是一类题，但是由于条件改变，时间复杂度也发生了改变。有duplicate的时候，移动某一边使其不再相等。 时间复杂度降为O(N)
这种类型的题目，根据binary search的判断依据不同有两种可能的解，一种是只关注右半部分是不是sort 好的， 另一种是只关注左半部分是不是sort好的， 其实这种类型的题目用第一种方法更加方便，因为如果只关注左半部分，最小值可能存在左端点也有可能出现在右半部分，不能直接找出来所存在的段，但是如果只关注右半部分，如果右半部分排好了序，那么最小值一定在左半段中，如果右半部分没有排好序，那么最小值一定在右半段中，这样就更好判断一些，就不需要再用一个global量来记录每次分段的最小值。
为什么要left < end作为结束条件？

(3) base case： 

a. start =  end，必然A[start]为min，为搜寻结束条件。

b. start + 1 = end，此时A[mid] =  A[start]，而min = min(A[mid], A[end])。而这个条件可以合并到(1)和(2)中。

152: maximum product subarray

需要维护3个变量, local_min, local_max, global_max, 因为对于product可能前面最小的负数，到后面与一个小的负数相乘会得到一个较大的数。

151:reverse words in a string

这个题目不仅需要去reverse words,而且需要进行一个预处理， 因为题目里并没有讲string里面有没有多余的空格，所以这个题目应该是分为两步：
1. deduplicate spaces
2. reverse words
对于第一步来说，属于string 快慢指针操作的问题，属于去重，对每一个fast指针指向的char需要在一定条件下移动慢指针那里。
150： evaluate reverse polish notation
这个题目相比之前的calculator I II来说就很简单了，用一个val stack存储value就可以了。
NOTE: 如果一个数使用string 存储的，那么必须要用 stoi()来进行string to int 的转换，因为可能存在‘－’， 不能简单地用positive number的处理方式来进行处理， 这个问题感觉老是犯！

149: Max points on a line

148: sort list
这个题目看时间复杂度就知道可以用merge sort但是问题是如果是常规的recursion版本的merge sort空间复杂度是不满足条件的， 所以必须用iteration的做法来做，但总觉得iteration的方法很繁琐，暂时还没有更新用iteration的方法。

147: insertion sort list
这个题目以前的做法都是去改变node里面的值，但是这无疑是个不好的做法， 其实可以通过指针的操作， 每次都把比current node 大的node放到current node 后面，

146: LRU cache
145:
144:

143: reorder list 
这个题目是利用link list里面一些常用的method来解决一个比较复杂的问题，这个题目分为3步， 找中点，reverse后半段， twist merge

141/142: cycle  in linked list
快慢指针找cycle。

140: 

137: single number II
每个元素出现3次，只有一个出现一次，找出那个single number， 其实这个题目给出的是这类问题的一个general的解法，就是针对每一位，对每一位进行累加+并且mod 3， 结果那个就是single number的那个位上的数。
+ | &这三种操作符的区别：
+： 就是数的运算符
| ：相当于bit的+ ： 0|0 = 0， 0|1 = 1， 1|1=1， 1|0 = 0，通常用来连接字符。
&：是相当是并， 也是bit运算。

136: single number I
每个元素出现两次，只有一个出现一次，找出那个single number，这个题目有个技巧就是如果用xor的话相同的两个数会抵消。


138: copy linked list with random pointer
133: clone graph
这两个题目用的思想是相似的，但是具体做法上不太一样，每个题目都有自己的难点，
copy linked list with random pointer的难点在于有两个指针需要copy，
clone graph的难点在于， 需要对整个graph进行遍历，对graph进行遍历，需要用到bfs， bfs 在graph遍历的话需要一个visited set， 这个题目特别需要注意的点是，需要对graph的所有node都进行遍历，所以copy的操作是不管这个node之前有没有visited的。bfs只是提供了一个node copy的顺序。