leetcode second round: 8/19

today's mission: 191-160

160: insertion of two linked list
the intersection of two linked list, corner case no intersection
step1: compute length, step2: catch up the shorter one step3: go together to find the intersectoin
注意代码的构造， 相同的代码用子函数来重构， 可以使得代码更加简洁。

161:find peak number
这个题目brute force的解法很容易想到， 但是时间复杂度太高，use binary search based divide and conquer 会把时间复杂度降到logn, 这个题目给的启示是对于unsorted array, 也是可以用bianry search 的，只是比较的情况可能会稍微不同，如果面试中，面试官要求找到比o(n)更好的解法，就往binary search 方向想， 哪种情况下可以把array size 减半。

162: maximum gap
这个题目很典型的就是用桶排序的思想，桶的数目， 桶的个数，每个元素怎么对应到相应的桶中。是这个题目的解题关键,注意在最后遍历桶的时候， 空桶是应该直接跳过的。

163: compare version numbers
这个属于字符串处理的问题，先要通过观察，发现规律，知道这个问题怎么去解，即算法是什么， 最后再实现， 很强的观察题。
面试的时候， 可能需要面试官给更加general的例子， 以便发现规律。
其实就是比较以每个‘.’为分隔符的字符串的大小。

164:

168: excel sheet column titile
这个题目跟一般的10进制到26进制的转换是有区别的，因为范围是从1-26， 而不是从0-25，所以对于26的整数倍的n是需要进行特殊处理的， 此时n纪录的是n里面还剩下多少个26.

171: excel sheet column number

这个题目和上面那题实质是一个进制转变的题目，这个题目是将26进制数转换成10进制数， 以26为底来进行计算就可以了，跟上面的那个由十进制转变成26进制更简单一些。

169: majority number
vote algorithm, 使之前majority numberII的简化版本。

171: binary search tree iterator
从这个题目可以知道binary tree的iterator的写法， 其实是循环的一个拆分， 这个题目其实是ignored traversal 的循环写法的拆分， 每次在get next的时候都从当前的root开始遍历左子树，get next函数就好像是inorder traversal iteration写法里面的内部循环。


173:
174 ： dungeon game
179 ： largest number
这个题目看到结果其实是input的一个排序，就可以想到利用sort函数来做，重载操作符（），但是对于特殊的情况，第一个数为0， 说明这整个input array 都是0， 所以最后的字符串就是“0”。
要注意corner case的处理。

186:

187:  repeated DNA sequences
这个题目属于字符串匹配次数问题，如果在map里面直接存字符串，会造成memory limit exceeds, 那么先将string做一个hash, 怎么hash呢？可以利用string里面char的组成，找可以代表一个char的数字，用ascii 码来进行哈希，最后存入map里面的string的hash值， 这样节省了很多空间。

188： Best time to buy and sell stock



189： rotate array
这个问题用的是跟yahoo loves me那个题目一样的做法，就是多次reverse, 最后达到rotate的目的。但是这个题目的细节还是需要注意的，即reverse的范围。
190: reverse bits
reverse bits 跟reverse string 的做法类似，对首尾对称的两个bit进行swap。 但是bit swap的方法跟string的swap不同，需要与之前的number 进行异或才可以完成swap操作。

191: number of 1 bits
判断一个无符号整型数的二进制里面含有多少个‘1’， bit operation, 只要对number里的每一位进行判断就可以了。
但是这里代码是可以优化的 ， 最好写到最优的代码，也能省去很多的计算。
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while (n) {
            count += n & 1;
            n = n >> 1;
        }
        return count;
    }
};