---

Internal Error: 去掉print的语句
Output Limit Exceeded: 返回的集合的长度大于正确答案
Time Limit Exceeded: 用时过长，需要优化 使用Python时的一个注意事项：
如果有List或者Dictionary作为类里面的attribute，则在函数里一定要清空。
比如有个M={}用于动态规划。则在调用递归函数的最外层函数里，要有个M={}。
不要import，很多东西直接用，例如heapq.heappush等。 使用C++时的一个注意事项：
如果用.size()，一定要强制转换为int类型。

题目：Given an array of integers, every element appears twice except for one. Find that single one. 方法：(1) HashSet (2) Xor 扩展：appears three times，用3个变量，记录每个bit是出现1次，还是2次，还是3次
        for(int i=0;i<A.length;i++)
        {
            int newone=one|(three&A[i]);
            int newtwo=two|(one&A[i]);
            int newthree=three|(two&A[i]);
            one=newone&(~(one&A[i]));
            two=newtwo&(~(two&A[i]));
            three=newthree&(~(three&A[i]));

        }

再扩展，除了两个数外，其余数都出现两次。求这两个数。

方法：先将所有数都异或，得到A^B，然后找到A^B为1的一位，A和B这一位不同。将所有数这一位为0的异或起来得到A和B中一个；将所有数这一位为1的异或起来得到另一个。

找为1的那位可以用A&~(A-1)。

Divide Two Integers
题目：Divide two integers without using multiplication, division and mod operator.
简单方法：从0开始每次加divisor看要加几个。很慢。
Trick：从c=1开始对divisor进行位运算，divisor每乘以2，将c也乘以2，直到divisor再乘以2就要大于dividend为止。求差，对差再次进行。

Unique Paths
题目：m*n的格子从左上到右下多少种走法，只能向下向右走。

用组合数的关键问题是overflow。虽然电脑上用long能成功，但LeetCode上用long还是失败。

算组合数的关键是不能先乘完了再除。要先除后乘，因为有定理：(1+m)(2+m)...(n+m)能被1*2*...*n整除。每一步，要被除的那个数，先和要被乘的那个数求GCD，约分，再和已有乘积求GCD，约分。最后一步再做乘法。

Set Matrix Zeroes
题目：将0元素的整行整列设为0。
constant space solution: 用矩阵的第一行和第一列做标记。

Sqrt(x)
牛顿法：要求f(x)=0的根，则

要求sqrt(a)，f(x)=x^2-a且要使f(x)=0。 二分法：从0到(x+1)/2进行搜索。 注意：要用long。 额外知识：Fast inverse square root，magic number，Quake
x_(n+1) = x_n ( 1.5 - a/2 * x_n ^ 2 )

Pow(x, n)

x ⁿ = x ^n/2 * x ^n/2 * x ^n%2

Best Time to Buy and Sell Stock
问题：一买一卖的最大利润。
方法1：
创建一个数组，从右往左记录出现过的最大值。然后再从左往右找。O(n)时间，O(n)空间。
方法2：
O(n)时间、O(1)空间的算法：记录low和high还有profit。碰到比low更小的就更新low，并清除high。碰到比high更大的就更新high并检查是否更新profit。 Best Time to Buy and Sell Stock II
问题：任意买任意卖的最大利润。
我的解法：记录拐点。
更简单的方法：比较任意相邻两个，如果i比i-1大，则累加price[i]-price[i-1]。 Best Time to Buy and Sell Stock III（技巧题）
问题：交易最多两次。（最多两买两卖）
PreProcessing：从左往右扫，记录最小；从右往左扫，记录最大。
第一步扫描，先计算出子序列[0,...,i]中的最大利润，用一个数组保存下来，那么时间是O(n)。
第二步是逆向扫描，计算子序列[i,...,n-1]上的最大利润，这一步同时就能结合上一步的结果计算最终的最大利润了，这一步也是O(n)。
所以最后算法的复杂度就是O(n)的。

Container With Most Water （经典题！）
问题：n个从(i,0)到(i,a_i)的线段。找两条能装最多的水。
头尾指针法。
O(n)的复杂度。保持两个指针i,j；分别指向长度数组的首尾。如果ai 小于aj，则移动i向后（i++）。反之，移动j向前（j--）。如果当前的area大于所记录的area，替换之。这个想法的基础是，如果i的长度小于j，无论如何移动j，短板在i，不可能找到比当前记录的area更大的值了，只能通过移动i来找到新的可能的更大面积。
证明：向中间移动长板是无法增加面积的：短板限制了高无法增加，而宽又是减少的，所以要增加面积只能移动短板。

Trapping Rain Water （经典题！）
问题：如图，能存多少水。
算法很简单，核心思想是：对某个值A[i]来说，能trapped的最多的water取决于在i之前最高的值leftMostHeight[i]和在i右边的最高的值rightMostHeight[i]。（均不包含自身）。如果min(left,right) > A[i]，那么在i这个位置上能trapped的water就是min(left,right) – A[i]。 有了这个想法就好办了，第一遍从左到右计算数组leftMostHeight，第二遍从右到左计算rightMostHeight，在第二遍的同时就可以计算出i位置的结果了，而且并不需要开空间来存放rightMostHeight数组。 时间复杂度是O(n)，只扫了两遍。

Two Sum （经典基础题！）
问题：在一个数组中找到两个数使它们的和最接近target。
方法：先排序，设定头尾指针，头为i，尾为j。如果sum<target，则i++；如果sum>target，则j--。
排序为O(N log N)，搜索为O(N)。
如果用暴力算法，则为O(N^2)。 K-sum问题
先排序，前面的数用暴力法，最后两个数用2Sum的头尾指针法。
K>2时，复杂度为O(N^(K-1))。
如果完全用暴力法，则为O(N^K)。
递归实现：K-Sum调用(K-1)-Sum 2Sum的线性解法：
如果只是要找是否存在，而不是最接近，则可以将这些数都hash起来。
对3Sum无帮助，依然为O(N^2)。 4Sum的O(N^2)解法：

将每一个pair的和hash起来，并记录是哪些pair（用HashMap）。同一个sum对应多个pair，用ArrayList。

3Sum Smaller

问题：找出有多少个(i,j,k)使得这三个位置的数的和小于target。

解答：先排序，考虑固定i，然后j和k设为两端。如果和小于target，那么把k换成小于k的数也小于。按照此规律去叠加。最后直到j和k相遇为止。只需要O(n^2)的time complexity。

Candy
问题：There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:

What is the minimum candies you must give? 算法：初始化所有小孩糖数目为1，从前往后扫描，如果第i个小孩等级比第i-1个高，那么i的糖数目等于i-1的糖数目+1；从后往前扫描，如果第i个小孩的等级比i+1个小孩高,但是糖的数目却小或者相等，那么i的糖数目等于i+1的糖数目+1。
该算法时间复杂度为O(N)。

Jump Game
问题：数组的每个数表示最多能跳几步。能否从开头跳到末位？
O(N)，记录一下每一步时当前能达到的最远距离maxReach即可。 Jump Game II

问题：最少跳几步？

类似，要记录已经达到过的最远处maxReach。每扫描一个元素，根据其数值更新maxReach之外的元素并更新maxReach。O(N)。

Largest Rectangle in Histogram（很难！）
问题：在直方图里找最大的矩形。
(1) O(N^3) approach: for every pair of bars i, j, find its area of the rectangle using i as the left bound and j as the right bound. To calculate the area, one needs to find the shortest bar between i and j, so the total time would be O(N^2) * O(N) which is O(N^3). (2) O(N^2) approach: one doesn’t have to scan the bars between i and j everytime to find the shortest bar in approach (1). One can always keep a the current shortest bar and each time use const time to update this value. So the time complexity would be reduced as O(N^2). (3) O(N) approach: this approach is really not easy to come up with. The idea is that, each bar say H defines a maximum rectangle which use this bar H as the shortest histogram in it. H defines this maximum rectangle by finding both the first left and the first right side bar to H which is shorter than H. If we can find the left and right bounds for each bar in linear time, then another linear scan could give us the global maximum rectangle by finding the maximum value over height[i] * (rightbound[i] – leftbound[i] – 1). Increasing stack is such a data structure helping us to find all the bounds in linear time.  For example, to find the right bound for each bar i (the right bound of i is just the index of the first bar shorter than bar i on the right side of i), we continue to push the histogram into the stack until we get a shorter histogram (we call this shorter histogram as the current histogram) than the one on the top of the stack. Ok, obviously, this shorter one is the right bound of the top histogram. We then keep poping the stack until we get a histogram which is shorter than the current histogram. All the poped out histogram will use the current histogram as their right bound (think about it, this is correct). We repeat this process, until all the histogram are pushed into the stack. Finally, we need to clear the stack, and set the right bound of the remaining histograms in that stack. Since each histogram is just pushed and poped once, this process cost O(N) time. Similarly, we can get the left bounds. Then a third linear scan will give us the global maximum rectangle as previously discussed.

Maximal Rectangle
问题：0-1矩阵里找最大的全1（或全0）矩阵。

常称为Largest empty rectangle问题。

比较面试书18.12。

解法1：
扫描每一个点（作为矩阵的左上角），对这个点，往下逐行扫描，当前面积为扫过的行里最短的乘以到第一行的距离。利用dp存储每个点的向右连续长度。时间复杂度为O(n^3)。 或者说矩阵为m*n，时间复杂度为O(m*n*m)。因为用了dp，所以空间复杂度为O(m*n)。 如果纯暴力求解不用dp，则时间复杂度为O(m^3 * n^3)。 解法2：
利用Largest Rectangle in Histogram，逐列扫描（作为矩阵的左边），对每一列使用histogram的算法，时间复杂度O(m*n)。

Gas Station（难题）
问题：一个圆上有n个加油站，每个加油站有gas[i]的油，去下一个加油站要cost[i]的油。从哪里出发能走完圆？
O(N)的解法：建立两个变量sum和total，从0到length遍历gas[]和cost[]，sum和total都+=gas[i]-cost[i]，检测sum是否小于0，如果是，res变量(restart)等于当前index+1，同时sum归零。最终根据total变量是否大于零决定返回res或者-1。

First Missing Positive（技巧题）
题目：给一个没排序的整数数组，找最小的不在数组里的正整数。O(n)时间，常数空间。
题目的最后一行，要求O(n)实际上暗示了用hash，但是又说要constant space，就没法再开新空间来建hash。
正好这个题目中处理的是1到n的数据，提供了一个将输入的数组同时用作hash表的可能性。
于是算法就是：
第一遍扫描排除所有非正的数，将它们设为一个无关紧要的正数(n+2)，因为n+2不可能是答案。
第二遍扫描，将数组作为hash表来使用，用数的正负来表示一个数是否存在在A[]中。
当遇到A[i]，而A[i]属于区间[1,n]，就把A中位于此位置[ A[i] – 1 ]的数值翻转为负数。
所以我们取一个A[i]的时候，要取它的abs，因为如果它是负数的话，通过步骤一之后，只可能是我们主动设置成负数的。
第三遍扫描，如果遇到一个A[i]是正数，说明i+1这个数没有出现在A[]中，只需要返回即可。
上一步没返回，说明1到n都在，那就返回n+1。

Longest Consecutive Sequence（经典题！）
问题：整数数组，找最长的子序列使其包含连续整数。
requirement: O(n)
不排序的话，就先hash起来，然后每一个元素，搜索其+1以及-1，每搜到一个，从hash中删掉，记录最大的连续序列。

Median of Two Sorted Arrays （难题）
方法：关键在于要实现一个函数，找到两个sorted arrays中的第k个数。用二分法。
int findKth(int A[], int B[], int a0, int a1, int b0, int b1, int k)
这里[a0,a1]和[b0,b1]是查找范围。
二分法规则：
考虑A的第k/2和B的第k/2个元素。
如果A[k/2]>B[k/2]，则意味着B的前k/2个元素都在A union B的前k个。则可以缩小B的范围，同时减小k。

Maximum Product Subarray
题目：整数可正可负的数组，找连续的子数组，使得乘积最大。
方法：记录当前元素为end的最大乘积与最小乘积。

Majority Element
题目：长度为n的数组，求出现次数超过一半的数。（假设肯定有）
方法1：排序后中间那个数。O(N log N)
方法2：计数法。从第一个数开始，看出现的次数。一旦计数小于0，就不再计这个数。而是计下一个新的数。一旦遇到正在计的数，就加1。扫完一遍之后，正在计的数就是majority element。这是因为出现次数超过一半的那个数足以抵消掉所有其他数。 Majority Element II
题目：长度为n的数组，求所有出现次数超过三分之一的数。
解答：关键点1是这样的数最多有两个；关键点2是数组要遍历两遍。
第一遍类似前一题，考虑次数最多的两个数。碰到加1，碰到其它数各自减1。
第二遍把第一遍得到的两个数数一遍，看看次数是否超过三分之一。

Rotate Array
题目：长度为n的数组，每个元素右移k步。
解答：我的O(n)时间O(1)空间的方法：
先算n和k的最大公约数，假设为m。那么要对数组进行m轮操作，每一轮以k为步长进行遍历，直到回到起始点。注意遍历要从最后一个元素开始。
也就是说，假如n=10，k=4，那么m=2，两轮遍历顺序为：
9 -> 5 -> 1 -> 7 -> 3 -> (9)
8 -> 4 -> 0 -> 6 -> 2 -> (8)
只要记住一开始的那个数就行了。

Find Peak Element
题目：找出数组里比邻居都大的那个数的index（任意一个都行）。要求O(log N)时间。边界的数只要大于唯一的邻居也算。无相等的邻居。
方法：二分法。二分中间的相邻两个数为a和b。如果a>b，则a到左边界一定有peak。如果a<b，则b到右边界一定有peak。

Maximum Gap
题目：乱序的非负整数数组，求排序后最大的相邻数的差。要求O(N)时间空间。
方法：桶排序。
假设有N个元素，范围从A到B。
那么最大差值不会小于ceiling[(B - A) / (N - 1)]
令bucket（桶）的大小len = ceiling[(B - A) / (N - 1)]，则最多会有(B - A) / len + 1个桶
对于数组中的任意整数K，很容易通过算式loc = (K - A) / len找出其桶的位置，然后维护每一个桶的最大值和最小值
由于同一个桶内的元素之间的差值至多为len - 1，因此最终答案不会从同一个桶中选择。
对于每一个非空的桶p，找出下一个非空的桶q，则q.min - p.max可能就是备选答案。返回所有这些可能值中的最大值。

Contains Duplicate II
题目：数组里是否存在距离不超过k的相等元素。
解答：建立hash表。
value -> [indices] Contains Duplicate III

题目：数组里是否存在两个不同的元素，距离不超过k，值相差不超过t。

解答：用BST。对每一个值v，考虑左边k个数和右边k个数，维护在BST里（不包括v本身）。只要最大值或最小值与v相差不大于t则可。

插入、删除、最小值、最大值都是log k，因此复杂度为O(N log k)。
暴力法为O(Nk)。

House Robber
题目：很多房子排成一条线，每个有一定金额，不能抢相邻的，最多能抢多少钱？
解答：动态规划很简单。

Minimum Size Subarray Sum
问题：正整数数组，和一个正整数s，要找数组里最短的子数组，使得和不小于s。
解答：两个pointer，只要和小于s，右pointer就往右走。一旦和达到或超过s，左pointer就往右走，直到和小于s为止。和的计算因为每次走一步，所以很快。O(N)。

Product of Array Except Self
问题：给一个数组A，返回一个同等大小的数组B，B[i]是A里除了A[i]外的所有元素乘积。不能使用除法。O(n)时间O(1)空间。

解答：两次遍历。先从左往右，记录累积的乘积，放入B，此时B的每个元素B[i]是A里的i左边元素的乘积。再从右往左遍历一次即可。

---

问题：很多房子，三种颜色，每个房子涂成每种颜色有特定的cost，相邻房子不能同色。求最小总cost。

解答：Viterbi算法，动归。

Same Tree
两个树如果前序和中序遍历都等价，则相同。
其实这道题有更简单的做法，直接迭代比较就可以了。