181. void reversePairsOfLinkList(Node*& head) {}
[] => []
[A,B] => [B, A]
[A, B, C] => [B, A, C]
[A, B, C, D, E, F, G] => [B, A, D, C, F, E, G]

见195题

182. You have to paint N boards of length {B1, B2, B3… BN}. There are K painters available and you are also given how much time a painter takes to paint 1 unit of board. You have to get this job done as soon as possible under the constraints that any painter will only paint continuous sections of board, say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}.
know it could be solved by DP. But solution space seems quite big. What is the optimal solution Thx.

DP,类似于103题

183. 一个range的序列（链表或数组），如[1,3], [2,6], [8,10]，[15,18] 写程序合并有重叠的range，比如上面的序列合并为[1,6], [8,10], [15,18] 如果这个序列不是静态的，而是一个数据流，如何 处理？
INTERVAL TREE

184. 实现atoi，要考虑特殊的情况，比如不合法的输入等等。参照这个定义
http://www.cplusplus.com/reference/clibrary/cstdlib/atoi/

185. word edit distance.

伪代码如下：

186. longest palindrome substring.

http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/

如果是substring,那可以按中心位置依次搜索。

如果是subsequence, 与它的反求longest common subsequence即可

187. Describe and analyze an algorithm to find the longest prefix of a given string that is also a palindrome. For example, the longest palindrome prefix of ILLINOISURBANACHAMPAIGN is ILLI, and the longest palindrome prefix of HYAKUGOJYUUICHI is the single letter S. For full credit, your algorithm should run in O(n) time.

TO LEARN， 后缀树？

188. 给一个数据结构数组，（parent, child）， 重建二叉树，总是先遇见leftchild, 再遇见right child，假设输入没有问题。要求返回root。

用一个hashtable来保存所有见到过的结点。 Root结点就是没有在child位置上出现过的结点。

189. 1. 两个sorted array, 如果merge成一个array。
2. 如果这两个array没有sort呢？并分析复杂度。
3. 如果有K个没有sorted的array怎么办呢？
4. 如果当前机器有K个cpu， 怎么处理问题3呢？复杂度分析。（考虑multithreading）

后面几问假设是merge成一个sorted array, 那这个题就类似于外部排序的多路归并。

190. 给定一个tree， 每个节点有一个数值， 如果找到一个从root到leaf的path，使得这个path上的所有节点的sum最小。 Interviewer所要的答案是和hashtable联系上的，因为考虑到树很大的时候需要很长的时间。这个题很容易用recursive的方式解答，可是这个不是interviewer所要的答案。后来按照interviewer的意见，还是基本写出了用hashtable的算法。

不理解题目的意思。。

191. 给定一个没有通往父节点的连接的BST, 找到大于x的最小的那个节点

中序遍历。略。。

192. 技术问题是找一个binary tree的叶子的最少depth

分层遍历即可，略。。

193. Integer to Roman number

CODE

194. 有一行animal cages，每个cage的动物的用水量为数组,有两个pipe给所有动物供水，pipe给当前cage的cost 是 这个cage动物的用水量，给其他cage的动物供水的cost是(distance to that cage)*那个cage动物的用水量， 求两个pipe供水的位置使cost最小。

TO LEARN

195. 问把整数分成 sum of square的经典问题

TO LEARN，数论题。。。

196. longest increase consecutive subsequence. e.g. 3, 2, 4, 5, 1, 6. Return {2, 4, 5}

CODE

197. 用1*2的瓷砖覆盖8*8的地板，有多少种方式呢？如果是N*M的地板呢
中等难度的DP，有个解题报告见：

http://www.cnblogs.com/PureMilk/archive/2008/07/21/1247492.html

公式的论文见：

http://arxiv.org/abs/math/0310326

198. 生成Dyck word list

与生成所有合法的括号组合类似，见：

http://en.wikipedia.org/wiki/Catalan_number

199. one integer array A with ascending order, for example 1 ,2 ,3,4, please generate another array B with any sum of any 3 different numbers picked from the A with ascending order, for example for 1,2,3,4, the result is (1+2+3),(1＋2＋4),(1＋3＋4),(2＋3＋4）“
三重循环即可，代码略。。

200. int array a[n] with all element 0<=a[i]<=1000,find the subarray with the largest sum that is <= max and output the starting and ending index of this subarray and the sum. If there is more than one such subarray, output the one with smallest starting index.

算法：

先求出累加和cum[i] = a[0]+…+a[i],从a[k]>max开始，在前面二分查找第一个cum[l]>=(a[k]-max), 直到找到范围最大的range. 复杂度O(NlogN)