102. Binary Tree Level Order Traversal

好久没有刷题了。 最近大家都在刷题, 我不刷的话估计找不着工作了。
遇到了一个值得记录的easy题。

题本身很简单：
Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]

这种题以前我的做法就是每层最后在queue里面mark一下是不是这层结束，以便判断在最后return的array里面新建一个array。

但这次我不想这么做，觉得直接通过计算能得出什么时候进入了新的一层。
在第一层结束的时候推算出下一层的node总数是 2^depth = (1 << depth)
在queue里面null node不push进去
这样每层null的个数=上层null的个数*2 + 本层null的个数

这样这层应该处理的node个数就是 (1<<depth) – (lastLvlNull * 2 + thisLvlNull)

代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root)
    {
    	if (root == NULL) return{};
    
    	queue<TreeNode *> q;
    	q.push(root);
    
    	int numNodeCurLvl = 1;
    	int numNullNextLvl = 0;
    	int numNullLastLvl = 0;
    	int depth = 0;
    
    	vector<vector<int> > res = { {} };
    	res[0].reserve(1);
    
    	while (!q.empty())
    	{
    		if (numNodeCurLvl == 0)
    		{
    			depth++;
    			
    			int totalNullCurLvl = numNullNextLvl + (numNullLastLvl << 1);
    			numNodeCurLvl = (1 << depth) - totalNullCurLvl;
    			numNullLastLvl = totalNullCurLvl;
    			numNullNextLvl = 0;
    
    			res.push_back(vector<int>());
    			res[depth].reserve(numNodeCurLvl);
    		}
    
    		TreeNode *curNode = q.front();
			res[depth].push_back(curNode->val);
			if (!curNode->left)
			{
				numNullNextLvl++;
			}
			else
			{
				q.push(curNode->left);
			}

			if (!curNode->right)
			{
				numNullNextLvl++;
			}
			else
			{
				q.push(curNode->right);
			}

    		q.pop();
    
    		numNodeCurLvl--;
    	}
    
    	return res;
    }

};

逻辑上绝对没问题。。。
可是竟然没Accepted。。。

原因出在很长的长得像linked list的tree

[-150,null,-149,null,-148,null,-147,null,-146,null,-145,null,-144,null,-143,null,-142,null,-141,null,-140,null,-139,null,-138,null,-137,null,-136,null,-135,null,-134,null,-133,null,-132,null,-131,null,-130,null,-129,null,-128,null,-127,null,-126,null,-125,null,-124,null,-123,null,-122,null,-121,null,-120,null,-119,null,-118,null,-117,null,-116,null,-115,null,-114,null,-113,null,-112,null,-111,null,-110,null,-109,null,-108,null,-107,null,-106,null,-105,null,-104,null,-103,null,-102,null,-101,null,-100,null,-99,null,-98,null,-97,null,-96,null,-95,null,-94,null,-93,null,-92,null,-91,null,-90,null,-89,null,-88,null,-87,null,-86,null,-85,null,-84,null,-83,null,-82,null,-81,null,-80,null,-79,null,-78,null,-77,null,-7...

生成的结果应该是这样的

[[-150],[-149],[-148],[-147],[-146],[-145],[-144],[-143],[-142],[-141],[-140],[-139],[-138],[-137],[-136],[-135],[-134],[-133],[-132],[-131],[-130],[-129],[-128],[-127],[-126],[-125],[-124],[-123],[-122],[-121],[-120],[-119],[-118],[-117],[-116],[-115],[-114],[-113],[-112],[-111],[-110],[-109],[-108],[-107],[-106],[-105],[-104],[-103],[-102],[-101],[-100],[-99],[-98],[-97],[-96],[-95],[-94],[-93],[-92],[-91],[-90],[-89],[-88],[-87],[-86],[-85],[-84],[-83],[-82],[-81],[-80],[-79],[-78],[-77],[-76],[-75],[-74],[-73],[-72],[-71],[-70],[-69],[-68],[-67],[-66],[-65],[-64],[-63],[-62],[-61],[-60],[-59],[-58],[-57],[-56],[-55],[-54],[-53],[-52],[-51],[-50],[-49],[-48],[-47],[-46],[-45],[-44],[-43],[-42],[-41],[-40],[-39],[-38],[-37],...

也就是每个array只有一个node

我的生成前半部分都没问题，只有在-118这个node出了问题。

[-121],[-120],[-119],[-118,-117],[-116,-115],[-114,-113],[-112,-111],

突然有node合并在一个array里了。

逻辑上这个是绝对不可能发生的。。。
假设出问题的话那肯定是totalNullCurLvl这个var出了问题
所以我就print了一下， 结果大跌眼镜。。

totalNull: 1
totalNull: 3
totalNull: 7
totalNull: 15
totalNull: 31
totalNull: 63
totalNull: 127
totalNull: 255
totalNull: 511
totalNull: 1023
totalNull: 2047
totalNull: 4095
totalNull: 8191
totalNull: 16383
totalNull: 32767
totalNull: 65535
totalNull: 131071
totalNull: 262143
totalNull: 524287
totalNull: 1048575
totalNull: 2097151
totalNull: 4194303
totalNull: 8388607
totalNull: 16777215
totalNull: 33554431
totalNull: 67108863
totalNull: 134217727
totalNull: 268435455
totalNull: 536870911
totalNull: 1073741823
totalNull: 2147483647
totalNull: -1
totalNull: 0
totalNull: 2
totalNull: 6
totalNull: 14
totalNull: 30
totalNull: 62
totalNull: 126
totalNull: 254
totalNull: 510
totalNull: 1022
totalNull: 2046
totalNull: 4094
totalNull: 8190
totalNull: 16382

这个var在32层之后就跪了。原因就是depth 所在的node数超过int bit长度了！！！！
150-118=32 正好是32层出的问题。。
这样即使把var改成64位的long long也无济于事， 因为那顶多linked-list长度不能超过64层。。。

好吧 这算是涨经验了 具体解决办法我还没想出来
暂时用老方法重新写

7. Reverse Integer

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

Need to handle overflow.

(12ms, 6.43%)
Attempt #1:

class Solution {
public:
    int sign(int x)
	{
		return (x > 0) - (x < 0);
	}

	int reverse(int x) {
	    if(x == 0) return 0;
	    
		list<int> queue;
		while (x != 0)
		{
			queue.push_back(x % 10);
			x /= 10;
		}

		int sum = 0;
		int peak = sign(queue.front()) > 0 ? INT_MAX : INT_MIN;
		if (queue.size() > 10) return 0;

		while (queue.size() != 1)
		{
			sum = sum * 10 + queue.front();
			queue.pop_front();
		}

		if (abs((peak - queue.front()) / 10) < abs(sum))
		{
			return 0;
		}
		else
		{
			sum = sum * 10 + queue.front();
		}

		return sum;
	}
};

写完就发现脑抽了。为啥要用queue呢。。
不用queue的push_back省了很多时间
而且对于overflow的check也做了改进

(8ms, 37.52%)
Attempt #2:

class Solution {
public:
    int sign(int x)
	{
		return (x > 0) - (x < 0);
	}

	int reverse(int x) {
	    if(x == 0) return 0;
	    
        int sum = 0;
		while (x != 0)
		{
		    int mod = x % 10;
		    int newSum = sum * 10 + mod;
			if ((newSum - mod) / 10 != sum)
			{
			    return 0;
			}
			
			sum = newSum;
			x /= 10;
		}

		return sum;
	}
};

253. Meeting Rooms II

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei), find the minimum number of conference rooms required.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.

==========================================
目前花时间最长的Leetcode题。各种试Greedy algorithm的corner case。。。
Greedy水太深。。
Some useful testcases:
[[2,15],[36,45],[9,29],[16,23],[4,9]]
[[928,5032],[3072,3741],[3960,4588],[482,2269],[2030,4360],[150,772]]
[[9,50],[30,37],[39,45],[4,22],[20,43],[1,7]]
[[9,50],[30,37],[20,43],[1,7]]
==========================================

Attempt #1:
(584ms, 76.22%)
基本思路就是Greedy Algorithm。
对于scheduling的感觉是试sort by front increasing或者 by end increasing.
一开始我试的by end就跪了。
这题sort by front可以work。

这题一个关键是：只有non-overlapping的intervals是可以放在一个rooms里面的
所以这题就变成了找所有的non-overlapping intervals。

这就想到了经典的570课上的greedy algorithm. 找能schedule最多的intervals
sort一下。
loop一遍array, 拿第一个interval和后面的比，如果后面的一个interval跟这个不重叠，那么继续从这个不重叠的interval往后loop. 这样复杂度是O(n)。

但这题不太一样。不是让你找能schedule的最多的intervals.
而是找到所有的disjoint intervals.
这就让这个问题截然不同了。

诚然maximum schedule的greedy algorithm能找到一个optimal的disjoint intervals.
但是他的过程会干掉那些suboptimal的disjoint intervals.
导致不是简简单单在原有greedy外面套个for loop就行的。

所以这题的正确解法其实也很简单。就是把maximum schedule的sort从least finish time变成least start time. 然后外面套个for loop过所有的element。

至于为什么这个就好用，因为我试了n次花了5个小时……才ok的
所以具体的correctness还得想想为什么。

姑且现在记住maximum number of disjoint intervals是sort start time
然后loop所有element. O(n^2)

而maximum scheduling intervals是sort end time. O(n)

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
struct SortByFront
{
    inline bool operator()(const Interval &i1, const Interval &i2)
    {
        if(i1.start == i2.start)
        {
            return i1.end < i2.end;
        }
        return i1.start < i2.start;
    }
};

class Solution {
public:
    int minMeetingRooms(vector<Interval>& intervals) 
    {
        if(intervals.size() == 0) return 0;
        
        sort(intervals.begin(), intervals.end(), SortByFront());
        
        vector<bool> done;
        done.resize(intervals.size(), false);
        
        int numDisjoints = 0;
        for(int k = 0; k < intervals.size(); k++)
        {
            if(done[k]) continue;
            
            int prevIndex = k;
            for(int i = k + 1; i < intervals.size(); i++)
            {
                if(done[i]) continue;
                
                Interval &cur = intervals[i];
                Interval &prev = intervals[prevIndex];
                
                if(cur.start >= prev.end)
                {
                    numDisjoints++;
                    done[prevIndex] = true;
                    done[i] = true;
                    
                    prevIndex = i;
                }
            }
        }
        
        return intervals.size() - numDisjoints;
    }
};

复杂度 worst case: O(n^2)

============================================

Attempt #2:
(584ms, 76.22%)
和上面思路一样，只不过是改成recursion了

class Solution
{
public:
    struct Comp
    {
        inline bool operator()(const Interval &i1, const Interval &i2)
        {
            if(i1.start == i2.start) 
            {
                return i1.end < i2.end;
            }
            else
            {
                return i1.start < i2.start;
            }
        }
    };
    
    int helper(const vector<Interval> &intervals)
    {
        if(intervals.size() == 0) return 0;
        
        int preIndex = 0;
        vector<Interval> newIntervals;
        
        for(int i = 1; i < intervals.size(); i++)
        {
            const Interval &cur = intervals[i];
            const Interval &pre = intervals[preIndex];
            if(pre.end > cur.start)
            {
                newIntervals.push_back(cur);
            }
            else
            {
                preIndex = i;
            }
        }
        
        return 1 + helper(newIntervals);
    }

    int minMeetingRooms(vector<Interval> &intervals)
    {
        sort(intervals.begin(), intervals.end(), Comp());
        return helper(intervals);
    }
};

121. Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

非常经典的一道题。上节课570还讲过。
可以从Divide and conquer经过两次优化到DP的解法

Attempt #1：
大体思路：
将Array recursively分成2份。
如果分的不能再分了就return 0. 因为buy和sell都是同一个day，那肯定没有profit。
下面就出现了几种情况
2 | 7
这里左面profit 0， 右面profit 0
但是如果是左面买的右面卖的，那profit就是7 – 2 = 5
所以我们就要求max(0, 0, 5) = 5 就是这两个day的最大profit。
然后拓展成4个day的情况
2 7 | 1 8
左面算完profit得5(过程上面)， 右面算完profit得7(过程省略）
如果左面买的右面卖的这时候就稍微复杂了点。
为了maximize profit需要买最少卖最多
所以2 7里面得选2， 1 8里面得选8
这样profit = 8 – 2 = 6
最后算这4个day的profit
max(5, 7, 6) = 7

依次类推。

基本就是标准的Divide and conquer.
Divide: 每步把problem分成两份
Conquer: 只要problem size不是1，那就继续Divide。Size是1的时候没有profit
Combine: Solution to the subproblems.
这里三种情况：
1) 买和卖都在左面
2) 买和卖都在右面
3) 买在左面卖在右面
最终solution = max(leftMax, rightMax, max(rightArr) – max(leftArr))
说白了就是三种情况取profit最大的一种

(16ms, 2.21%)

class Solution {
public:
    int findMax(const vector<int> &prices, int left, int right)
    {
        int max = INT_MIN;
        for(int i = left; i <= right; i++)
        {
            max = std::max(prices[i], max);
        }
        return max;
    }
    
    int findMin(const vector<int> &prices, int left, int right)
    {
        int min = INT_MAX;
        for(int i = left; i <= right; i++)
        {
            min = std::min(prices[i], min);
        }
        return min;
    }

    int helper(const vector<int> &prices, int left, int right)
    {
        if(right == left) return 0;
        
        int mid = left + ((right - left) >> 1);
        
        int leftMax = helper(prices, left, mid);
        int rightMax = helper(prices, mid + 1, right);
        
        int crossMax = findMax(prices, mid + 1, right) - findMin(prices, left, mid);
        
        return std::max(std::max(leftMax, rightMax), crossMax);
    }

    int maxProfit(vector<int>& prices) 
    {
        if(prices.size() == 0) return 0;
        return helper(prices, 0, prices.size() - 1);
    }
};

Complexity:
Divide: O(1), 因为Divide我们只算了index和mid
Conquer: 原本的array用了T(n)的话，2个divide过后的subproblems是2T(n/2)
Combine: O(n). 左面和右面都是O(1) 因为返回的结果就直接用了。但是买左卖右的解法需要把左面两个array都search一遍以找到最大值所以是O(2n) + O(2) = O(n)

所以总的就是:
T(n) = 2T(n/2) + O(n) + O(1)
f(n) = O(n) = Theta(n^log2(2)) = Theta(n^1)
所以T(n) = O(nlog(n)) – master theorem

======================================

Attempt #2:
上面有一步是搜索Array。这个要take O(n)
但实际上并不用
我们在Divide and conquer的同时也可以把当前array的最大和最小值返回去
到最底层返回自己就可以，
每往上一层都和return那层的左面和右面的最大最小值比较
这样每层的search就从O(n)变成了O(1)

总体就是：
T(n) = 2T(n/2) + O(1)
f(n) = O(1) = O(n^log2(2)) = O(n)
所以T(n) = O(n^log2(2)) = O(n)

(16ms, 2.21%)

class Solution {
public:
    struct ValuePair
    {
        int maxProfit;
        int maxValue;
        int minValue;
    };

    ValuePair helper(const vector<int> &prices, int left, int right)
    {
        if(right == left) return {0, prices[left], prices[left]};
        
        int mid = left + ((right - left) >> 1);
        
        ValuePair leftRet = helper(prices, left, mid);
        ValuePair rightRet = helper(prices, mid + 1, right);
        
        int &leftMaxProfit = leftRet.maxProfit;
        int &leftMaxValue = leftRet.maxValue;
        int &leftMinValue = leftRet.minValue;
        
        int &rightMaxProfit = rightRet.maxProfit;
        int &rightMaxValue = rightRet.maxValue;
        int &rightMinValue = rightRet.minValue;
        
        int crossProfit = rightMaxValue - leftMinValue;
        int maxValue = std::max(leftMaxValue, rightMaxValue);
        int minValue = std::min(leftMinValue, rightMinValue);
        
        return { std::max(std::max(leftMaxProfit, rightMaxProfit), crossProfit), maxValue, minValue };
    }

    int maxProfit(vector<int>& prices) 
    {
        if(prices.size() == 0) return 0;
        return helper(prices, 0, prices.size() - 1).maxProfit;
    }
};

可以看到速度并没有变化。可能是test case太少的原因。
但是实际上O(n)和O(nlogn)差的并不多。

有更好的方法么？
但理论上算法速度已经不能比O(n)快了。因为如果找出大小，那最少也要看n个element
但是memory usage有可能更优化。
现在Divide conquer的做法需要O(logn)的内存。
因为Conquer过程会生成高度为logn的树。也就是stack深度是logn个call的深度。

Attempt #3:
换个思路。
这题其实就是求某day的值(Pd) – 这day之前的day的值(Ppd)最大

profit = Pd – Ppd;
要使得profit最大，需要maximize Pd， minimize Ppd。
所以loop一遍array，在过程中记录最小值和最大值。然后最后最大值减最小值就是maxprofit？？
错！！！
要知道这里有个重要的constraint: Pd的index必须在Ppd之后。
上面做法如果array是[4 1 2]那就跪了

所以并不需要记录Pd最大值。只需要拿当前的值Pd 减 前面最小的值minPpd
得到的profit大于以前记录的maxProfit就可以。

这样就只需要几个固定的var记录profit和最小值。O(1) space

(8ms, 26.53%)

class Solution {
public:
    int maxProfit(vector<int> &prices) 
    {
        int g_min = INT_MAX;
        int maxProfit = 0;
        
        for(int i = 0; i < prices.size(); i++)
        {
            int p = prices[i];
            
            g_min = std::min(g_min, p);
            
            int profit = p - g_min;
            // if(profit > 0)
            {
                maxProfit = std::max(maxProfit, profit);
            }
        }
        
        return maxProfit;
    }
};

注意~： 这个算法还有个好处.
就是可以支持streaming.
如果不断有新element加入array, 我们也可以继续计算。
也就是说这个算法不需要知道data的whole picture.
而上面divide and conquer by nature就需要知道整体size才能divide。

152. Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

Time: O(n), Space O(1)

========================================================
这题也想了很长时间。有几个难点
1) 知道这种题不能sort 因为sort以后得到的结果就不是contigious array了
2) 一般不能sort的array题求maximum或者minimum的解法基本就是brute force + dp。
3) dp难度在于构建subproblem。 有时候想出来subproblem但是因为需要大量例子验证所以一直没法确定正确
4) corner case很多， 需要巧妙处理

Attempt #1:
完整思路：
首先把思路往构建Subproblem上想。
Recursive的题有个特点：就是前一个得出的结果会成为后一个结果的一部分。
在没想出来subproblem以前，就往这个想法上套。
比如DP[i]给DP[i+1]或者DP[i-1]用。
这时候i是array的index.
那么problem就变成了在array i这个index下得出的一个运算会给i+1这个运算带来什么好处？
这个好处再往题目上靠。
题目出的是maximum product。 那么我就套一下变成i这个index下得出的maximum product
会给i+1的maximum product作为部分解。

这时候挺兴奋，但是开始写recurrence relation的时候发现了定义的不明确。
这个ith maximum product的运算里面是不是必须包括ith element.
举个例子：

 0 1 2 3
[1,2,3,-4]

3th product 是1*2*3=6 还是 1*2*3*(-4) 诶？
肯定不能是1*2*3*-4 这样就比6小了。但是maximum就是6.
但如果选1*2*3的话，那还会出现反例

 0 1 2  3 4
[1,2,3,-4,5]

如果上面的例子3th maximum product选了1*2*3=6,
那么4th就会变成6*5=30
这样就错了， 因为有这个-4导致了1,2,3和5不是contigious的，所以4th不能直接乘6

另外如果5th是个负数的话， 如下

 0 1 2  3 4  5
[1,2,3,-4,5,-6]

那么这个最大解应该是1*2*3*(-4)*5*(-6)
因为负负得正。
但是因为在3th选择了6，所以失去了*(-4)这个运算结果导致上面的最大解出不来。

那么现在就需要一种解法，既能保证ith maximum里面存的是在ith下的最大product，又能保证每个运算，包括使得array non-contigious的运算结果保存下来，以供以后负负得正的时候使用。

这时候发现每当往后乘的时候如果突然出现一个负数，那么当前的最大值就变成了最小值
那么我们就可以同时保存前一个index的最大值和最小值。
当ith element是正数的时候，那么就拿i-1 max乘以A[i]放到imax里.
如果ith element是负数的时候，就拿i-1 min乘以A[i]放到imax里
但assumption是保证imax>=0, imin<=0

 
arr: [1 2 3 -4   5     -6  -7] 
max: [1 2 6 0    5    720  210] 
min: [0 0 0 -24  -120 -30 -5040] 

会发现max的最大解是720.而不是最后一个210.所以这里需要在每个ith max算的时候都用个var去keep track imax里面的最大值作为结果。 注意1：因为每后面一个结果都”只“ depend on前面一个结果，所以没有必要存一个array。 只存一个imax, imin的variable代表ith max/min就行。 这样space就是O(1) 注意2：这里有个特别subtle的corner case。 如果array里面只有一个element 比如[-2] 那么上面的方法就会失效。因为如果imax=0的时候，我会把当前ith >0的element作为新的imax。
因为-2只走进了imin，并且我是保证imax里面只存非负数，imin里面只存非正数，所以就导致结果是0.

这时候就要单独check一下,如果array size=0，那么就返回第一个element。

那么会不会引入新的corner case呢？比如都是负数的时候？
答案是否定的。 因为只要数不是单独一个，那么就100%会产生一个最大正数乘积。

[-2,-2] - 4
[-2, 2] - 2 
。。。

(4ms, 72.57%)

class Solution {
public:
void swap(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}

int maxProduct(vector& nums)
{
if(nums.size() == 1) return nums[0];

int result = INT_MIN;

int imax = 0;
int imin = 0;

for(int i = 0; i < nums.size(); i++)
{
int val = nums[i];

if(val < 0)
{
swap(imax, imin);
}

if(imax == 0)
{
imax = std::max(0, val);
}
else
{
imax *= val;
}

if(imin == 0)
{
imin = std::min(0, val);
}
else
{
imin *= val;
}

result = std::max(imax, result);
}

return result;
}
};
[/code]

238. Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

===================================
又是一道毫无头绪的题。可耻的看了答案。
===================================

思路很简单：
既然不让1*2*3*4 / index = number at index那就换种乘法

1 2 |3| 4

假设在i=2.那结果应该是1*2*4
可以看出这个可以通过分别算1*2 和4最后乘起来得出
也就是index左面的乘积乘以index右面的乘积

这样可以准备两个array。
一个放在每个index左面的数的乘积
一个放在每个index右面的数的乘积

这题要用O(n)所以关键点就是每个index往后一个的index得出的乘积都依赖于前一个乘积
也就是A[i+1] = A[i] * num[i]。
这样只需要loop两遍array就可以拿到所有的数乘积

放一个O(1) space的算法。
原理一样
只是用不着第二个array去存。这题要求说result array不算space所以
就可以利用这块地方放index左面的乘积。
而右面的乘积每算一个都可以得出一个结果，所以不用另一个array存。

(64ms, 14.98%)

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> res(nums);
        res[0] = 1;
        
        for(int i = 1; i < nums.size(); i++)
        {
            res[i] = nums[i - 1] * res[i - 1];
        }
        
        int rightProduct = 1;
        for(int i = nums.size() - 1; i >= 0; i--)
        {
            res[i] *= rightProduct;
            rightProduct *= nums[i];
        }
        
        return res;
    }
    
};

**333.Largest BST Subtree

Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.

Note:
A subtree must include all of its descendants.
Here’s an example:

    10
    / \
   5  15
  / \   \ 
 1   8   7

The Largest BST Subtree in this case is the highlighted one.
The return value is the subtree’s size, which is 3.

==============================================================
这题我一开始审错题了，写了一个handle更复杂情况的code。这个放到后面说。

==============================================================
我一开始以为任何valid BST即使在中间层的也算
比如

[10,5,15,1,8,7,null,0,7,6,null,null,null, 3,null,null,null,null,null,1,4]

      10    ---- |
      /\         |
     5 15   ---- | = 6
     /\ /        |
    1 8 7   ---- |
   /\ /
  0 7 6
  /
 3          ---- | 
/ \              | = 3
1 4         ---- |

我的code handle了中间层所以得到了6 而不是3.但题目要求3.因为说了A subtree must include all of its descendants.这个意思就是如果你从10开始算subtree的话那下面全得算上。。

因为这个code我写的对， 也有参考价值就贴上来了

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int postorder(TreeNode *cur)
    {
        if(cur == NULL) return 0;
        
        bool leftOK = true;
        bool rightOK = true;
        
        if(cur->left != NULL)
        {
            if(cur->left->val >= cur->val)
            {
                leftOK = false;
            }
        }
        
        if(cur->right != NULL)
        {
            if(cur->right->val < cur->val)
            {
                rightOK = false;
            }
        }
        
        int leftNum = postorder(cur->left);
        int rightNum = postorder(cur->right);
        
        if(leftOK && rightOK)
        {
            if(leftNum == -1 || rightNum == -1)
            {
                return 0;
            }
            else
            {
                _maxSubTreeNum = std::max(leftNum + rightNum + 1, _maxSubTreeNum);
                return leftNum + rightNum + 1;
            }
        }
        else
        {
           
            return -1;
        }
    }

    int largestBSTSubtree(TreeNode* root) 
    {
        _maxSubTreeNum = INT_MIN;
        postorder(root);
        return _maxSubTreeNum;
    }
    
    int _maxSubTreeNum;
};

94. Iterative Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.

Iteratively.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

recursive很简单。但变成iterative很tricky. 各种corner case。
==============

Attempt #1:
(4ms, 0.61% meh…)

大体思路：
用vector去模拟stack
每拿stack head就check他的左面是否visited过了。是的话把自己也mark visited。同时写进inorder结果。
因此需要个hash_set去存visited.
而且如果左面visited了，这时候要把自己pop掉，然后insert右面。
省的到时候右面traverse回来以后自己因为又check了左边一遍而再次写进inorder结果。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) 
    {
        if(root == NULL) return {};
        
        vector<TreeNode *> stack;
        vector<int> result;
        
        stack.push_back(root);
        unordered_set<TreeNode *> visited;
        visited.insert(NULL);
        
        while(!stack.empty())
        {
            TreeNode *curNode = stack.back();
            
            bool leftVisited = visited.count(curNode->left) != 0;
            bool rightVisited = visited.count(curNode->right) != 0;
            
            if(leftVisited)
            {
                result.push_back(curNode->val);
                
                visited.emplace(curNode);
                stack.pop_back();
            }
            else
            {
                stack.push_back(curNode->left);
            }
            
            if(leftVisited && !rightVisited)
            {
                stack.push_back(curNode->right);
            }          
        }
        
        return result;
    }
};

Attempt #2:
大体思路：
并不用visited来记录。
只要在左面到头以后，pop parent，然后拿parent右面的继续向左traverse

(0ms, 11.77%)

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) 
    {
        if(root == NULL) return {};
        
        vector<TreeNode *> stack;
        vector<int> result;
        
        TreeNode *curNode = root;
        while(!stack.empty() || curNode)
        {
            if(curNode != NULL)
            {
                stack.push_back(curNode);
                curNode = curNode->left;
            }
            else
            {
                curNode = stack.back();
                result.push_back(curNode->val);
                
                stack.pop_back();
                curNode = curNode->right;
            }
        }
        
        return result;
    }
};

6. ZigZag Conversion

The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: “PAHNAPLSIIGYIR”
Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);
convert(“PAYPALISHIRING”, 3) should return “PAHNAPLSIIGYIR”.

====================
这题做了好久。从一开始读题就没读懂到后来操作string各种问题。。哎
难道是状态不好么。。。 感觉想想自己就lost了
====================
(16ms, 74.28%)
大体思路：
Brute Force。。。

拿一个例子：
EBAYISHIRING, 5
画成表格就是
E       R
B     I I
A   H   N
Y S     G
I       

展开就成
EBAYI | SHI | RING
^         ^   ^

这三个pointer最左面和最右面那个往右走， 中间那个往左走(只有在不是头和尾的时候走)

因为中间case最复杂。为了节省各种branch，那就先把第一排和最后一排先走一遍。
然后code中间单独处理三个pointer一起动的case

Attempt #1:

class Solution {
public:
	string convert(string s, int numRows) {
		if (numRows == 1) return s;

		const int length = s.size();
		const int stride = numRows * 2 - 2;

		string str;
		str.reserve(length);

		// first row
		int pos = 0;
		while (pos < length)
		{
			str.append(1, s[pos]);
			pos += stride;
		}

		for (int loop = 1; loop < numRows - 1; loop++)
		{
			pos = loop;
			int mid = stride - loop;

			while (mid < length)
			{
				if (pos < length)
				{
					str.append(1, s[pos]);
				}
				str.append(1, s[mid]);

				pos += stride;
				mid += stride;
			}

			if (pos < length)
			{
				str.append(1, s[pos]);
			}
		}

		// last row
		pos = numRows - 1;
		while (pos < length)
		{
			str.append(1, s[pos]);
			pos += stride;
		} 

		return str;
	}
};

这里有点很关键， str.reserve(length);这行整整提升4ms性能。从56.32%到74.28%提升。

======================================================
转了一圈discussion board 找到了一个很巧的做法。虽然性能和空间使用都不如我上面那个
https://leetcode.com/discuss/10493/easy-to-understand-java-solution

(28ms, 22.53%)

class Solution {
public:
string convert(string s, int numRows) {
vector vs(numRows, &quot;&quot;);
int n = s.length(), i = 0;
while (i &amp;lt; n) {
for (int j = 0; j &amp;lt; numRows &amp;amp;&amp;amp; i = 1 &amp;amp;&amp;amp; i &amp;lt; n; j–)
vs[j].push_back(s[i++]);
}
string zigzag;
for (string v : vs) zigzag += v;
return zigzag;
}
};

=======================================================
网上还找了个纯用数学算坐标的方法, 代码比我的简洁。但性能没我的好。
http://fisherlei.blogspot.com/2013/01/leetcode-zigzag-conversion.html

n=4
P              I              N
A         L  S         I   G
Y   A       H    R
P              I

N=5
P               H
A          S  I
Y      I       R
P   L          I      G
A              N

所以，对于每一层主元素(红色元素)的坐标 (i,j)= (j+1 )*n +i
对于每两个主元素之间的插入元素（绿色元素），(j+1)*n -i
(20ms, 56%)

class Solution {
public:
    string convert(string s, int nRows) {  
      if(nRows <= 1) return s;  
      string result;  
      result.reserve(s.size());
      if(s.size() ==0) return result;  
      for(int i =0; i< nRows; i++)  
      {  
        for(int j =0, index =i; index < s.size();   
            j++, index = (2*nRows-2)*j +i)  
        {  
          result.append(1, s[index]);  //red element
          if(i ==0 || i == nRows-1)   //green element
          {            
            continue;  
          }  
          if(index+(nRows- i-1)*2 < s.size())  
          {  
            result.append(1, s[index+(nRows- i-1)*2]);  
          }  
        }  
      }  
      return result;  
    }  
};

295. Find Median from Data Stream

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:
[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

void addNum(int num) – Add a integer number from the data stream to the data structure.
double findMedian() – Return the median of all elements so far.
For example:

add(1)
add(2)
findMedian() -> 1.5
add(3)
findMedian() -> 2

=============================

这个题上来看感觉巨简单。直接用array存然后去中点返回就行了啊。
但是被例子欺骗了。例子是[234]但如果是[423]呢？中位数肯定不是2
所以这个题必须要保证list是sorted。
那么现有data structure比如set一类的复杂度都是O(logn)insert。
所以反复insert就会是nlogn。 而拿中间的element也是O(logn)
所以上来就用这个方法肯定TLE。。。

之后想了半天也没想出来什么好方法就去Discussion board取经。
看到里面大神用了binary heap。 ok打住不看他怎么实现的就往这想。

Attempt #1:
大体思路：binary heap可以使max heap或者min heap。
这两个structure取最大或最小只需要O(1)
那么只要把前半部分放到max heap， 后半部分放到min heap里面
这样min heap的top就是中位数（odd number size)
min heap top 和 max heap top的平均数就是中位数(even number size)

(204ms, 29.94%)

class MedianFinder {
public:
	void addNum(int num)
	{
		_maxHeap.emplace(num);
		_minHeap.emplace(_maxHeap.top());
		_maxHeap.pop();
		if (_maxHeap.size() < _minHeap.size())
		{
			_maxHeap.emplace(_minHeap.top());
			_minHeap.pop();
		}
	}

	// Returns the median of current data stream
	double findMedian()
	{
		if (_maxHeap.size() > _minHeap.size())
		{
			return _maxHeap.top();
		}
		else
		{
			return _maxHeap.top() + ((double)_minHeap.top() - _maxHeap.top()) / 2;
		}
	}

	priority_queue<int> _maxHeap;
	priority_queue<int, std::vector<int>, std::greater<int> > _minHeap;

};

这个性能感觉不咋地。insert worst case是 5*log(n) findMedian是O(1)
按正理应该很快啊。。。前70%的人都是怎么写的…

然后我去Discussion board里面看到有人用binary search的方式insert进array，使得array本身就是sorted。然后再取中位数。
然后试了一下竟然进了80%。。。。
但这不科学啊。。。。
因为Array的insert要O(n) worst case的
我觉得可能就是leetcode的test case不足导致的 没有测过大的N

但是还是学了一招求sorted array中位数不用if else判断奇数偶数的一招

lastIndex = arr.size() -1;
median = arr[lastIndex] + (arr[lastIndex + 1] - arr[lastIndex]) / 2;

之所以不用判断奇偶是因为lastIndex / 2 和 (lastIndex + 1) / 2
在array size是偶数的时候对应了差一个的位置
size = 4: 3 / 2 = 1 | 4 / 2 = 2 <–中间两个数

在size是奇数的时候两个index相等
size = 3: 2 / 2 = 1 | 3 / 2 = 1 <–中间一个数