## Life should be colorful.

Colorful Week
Life should be as colorful as this calendar.

## Algorithm Problem: In-Place Merge Sort

The original merge sort version will take O(n) space, and O(nlogn) time.

The O(n) space is the most significant problem of this algorithm. However, there is an O(1) space version, called ‘in-place merge sort’.

## LeetCode Problem: Populating Next Right Pointers in Each Node II

The code in the previous article LeetCode Problem: Populating Next Right Pointers in Each Node, Level traversal of binary tree is also adapted to this situation.

Populating Next Right Pointers in Each Node II
Follow up for problem “Populating Next Right Pointers in Each Node”.
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
You may only use constant extra space.
For example,
Given the following binary tree,

```         1
/  \
2    3
/ \    \
4   5    7
```

After calling your function, the tree should look like:

```         1 -> NULL
/  \
2 -> 3 -> NULL
/ \    \
4-> 5 -> 7 -> NULL
```

## LeetCode Problem: Populating Next Right Pointers in Each Node, Level traversal of binary tree

It’s easy to doing this by using a queue, doing a level traversal of binary tree.

Populating Next Right Pointers in Each Node
Given a binary tree
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Note:
You may only use constant extra space.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,

```         1
/  \
2    3
/ \  / \
4  5  6  7
```

After calling your function, the tree should look like:

```         1 -> NULL
/  \
2 -> 3 -> NULL
/ \  / \
4->5->6->7 -> NULL
```

Code, 160ms pass the large test set.

```/**
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
*  int val;
*  TreeLinkNode *left, *right, *next;
*  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
void connect(TreeLinkNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
queue q;
if(root) {
q.push(root);
q.push(NULL);
}
while(q.size()) {
TreeLinkNode *cur = q.front();
q.pop();
if(cur) {
cur->next = q.front();
if(cur->left) q.push(cur->left);
if(cur->right) q.push(cur->right);
} else {
if (q.size()) q.push(NULL);
}
}
}
};
```

Code rewrite at 2013-1-19, more simple

```class Solution {
public:
void connect(TreeLinkNode *root) {
queue q;
q.push(root);
q.push(NULL);
while(true) {
TreeLinkNode *cur = q.front();
q.pop();
if(cur) {
cur->next = q.front();
if(cur->left) q.push(cur->left);
if(cur->right) q.push(cur->right);
} else {
if (q.size() == 0 || q.front() == NULL) return;
q.push(NULL);
}
}
}
};
```

## Algorithm Problem: Longest Non-Descending Sub Array or Logest Increasing Subarray, Dynamic programming

The ordinary dynamic programing gives our an algorithm of time complexity O(n2).
However, we could achieve the result by O(n * logn).
Inorder to do this, we need an array named min4length to hold the minimum value in array for the last number of the subarray in each length we could get. For example, given array {1,2,0}, the first run min4len = {1}, second {1,2}, third {0,2}.
At each step i from 0 to array.size() – 1, we find out the position l in min4length that satisfy that min4len[l] > array[i], and all the values before l is small than array[i], if exists. that is min4len[j] < array[i],j < l.
This step we could do in O(log n) time by binary search.
Then if the l is equal to min4len.size(), that indicated that we get to new length record, just push the value array[i] into min4len.
Else, update the min4len[l] = array[i], if min4len[l] > array[i]. And this step will NOT break the non-decreasing attribute of the array min4len, so we could do binary search again.
At last, the min4len.size() is the max length we could achieve.

If we need to output all the values in the final sub-array, it’s much harder, we have to keep track for each length of sub-array. see the code below in function:longestNonDecreasingSubArray()

Problem
Given an array with integers, find the longest non-descending sub-array of the given array.
For example:
Given: {1,2,3,-1,0,1,2,3,4,-1}
Should find out: {-1,0,1,2,3,4} of length 6.

Codes

<

pre>
//
// main.cpp
// LongestIncreasingSubarray
//
// Created by Qiu Xiangyu on 12-12-23.
//

# include

using namespace std;

void printArray(vector array) {
for (size_t i = 0; i < array.size(); ++i) {
if (i > 0) {
cout<<“,”;
}
cout<<array[i];
}
cout<<endl;
}

int lengthOfLongestNonDecreasingSubArray(vector &array) {
if (array.size() == 0) {
return 0;
}
vector min4Length;
for (int i = 0; i < array.size(); ++i) {
int l = 0,h = (int)min4Length.size() – 1;
while (l <= h) {
int mid = (l + h) / 2;
if (min4Length[mid] <= array[i]) {
l = mid + 1;
} else {
h = mid – 1;
}
}
if (l == min4Length.size()) {
min4Length.push_back(array[i]);
} else {
if (min4Length[l] > array[i]) {
min4Length[l] = array[i];
}
}
printArray(min4Length);
}

`return (int)min4Length.size();`

}

vector longestNonDecreasingSubArray(vector &array) {
vector ret;
if (array.size() == 0) {
return ret;
}
vector min4Length;
vector<vector > pathes;
for (int i = 0; i < array.size(); ++i) {
int l = 0,h = (int)min4Length.size() – 1;
while (l <= h) {
int mid = (l + h) / 2;
if (min4Length[mid] <= array[i]) {
l = mid + 1;
} else {
h = mid – 1;
}
}
cout<<“step “<<i<<“, value “<<array[i]<<“, position “<<l<<“, in min4len: “;
printArray(min4Length);
if (l == min4Length.size()) {
min4Length.push_back(array[i]);
vector path;
if (l > 0) {
vector &prePath = pathes[l – 1];
for (int k = 0; k < prePath.size(); ++k) {
path.push_back(prePath[k]);
}
}
path.push_back(i);
pathes.push_back(path);
cout<<“new length, min4len: “;
printArray(min4Length);
cout<<” path: “;
printArray(path);
} else {
if (min4Length[l] > array[i]) {
min4Length[l] = array[i];
if (l > 0) {
vector &prePath = pathes[l – 1];
for (int k = 0; k < prePath.size(); ++k) {
pathes[l][k] = prePath[k];
}
}
pathes[l].back() = i;
cout<<“path for “<<l<<” is:”;
printArray(pathes[l]);
}
cout<<“old for length: “< &lpath = pathes.back();
for (int i = 0; i < lpath.size(); ++i) {
ret.push_back(array[lpath[i]]);
}
return ret;
}

int main(int argc, const char * argv[])
{
vector arr = {1,2,3,-1,0,1,2,3,4,-1};
// int longest = lengthOfLongestNonDecreasingSubArray(arr);
// cout<<longest<<endl;
vector larr = longestNonDecreasingSubArray(arr);
printArray(larr);
cout<<“length : “<<larr.size()<<endl;
return 0;
}

## Algoritm Problem: Add Two Unsigned Integers

To add two unsigned integers, A and B, we can exam a binary add by hand:
Let A = 5, B = 3, that is:

``` 0101 A
+0011 B
-------
1000
```

We can notice that, if we ignore the overflow in some digital, that will be:

``` 0101 A
+0011 B
-------
0110 C
```

Where C just is A^B.

If we consider only the overflow, we can get:

``` 0101 A
+0011 B
-------
0001 D
```

The equation will be right: A + B = C + D << 1. And the D is just A&B
So we can conclude that A + B = (A^B) + (A&B)<<1.
When we recursively doing this, until B is zero, or the most significant bit of B is 1(in this case, A+B exceeds the bounds of unsigned int).

Codes

```
//
//  main.cpp
//
//  Created by Qiu Xiangyu on 12-12-21.
//

#include
using namespace std;

unsigned int add(unsigned int i0, unsigned int i1) {
static const unsigned int hMask = 0x1 << (sizeof(unsigned int) * 8 - 1);
while (i1 != 0) {
unsigned int base = i0 ^ i1;
unsigned int pro = i0 & i1;
if (pro & hMask) {
//over flow
return 0;
}
i0 = base;
i1 = pro << 1;
}
return i0;
}

int main(int argc, const char * argv[])
{

// insert code here...
std::cout << "Hello, World!\n";
unsigned int uMax = ~0;
cout<< add(uMax - 1,2);
return 0;
}
```

## How to Deploy iOS Applications into Any Device out of Apple Store

Pre-Conditions:
You have an apple developer account.

The first way, is that you plug in the device into the Mac, on which your application is developed and let xcode to install the applications automatically.

But, if you cannot access the device directly, this is not the way that fulfilled.

However, in this case, we can deploy an iOS application into Devices by Ad-Hoc and thus do not wait for the apple store review. Just following the steps below:

1. Login into developer.apple.com, in the Devices tab, add the target device by it’s UDID
2. In the provisioning tab, open the Distribute tab, add an Ad-Hoc, provisioning profile with the target device selected
3. Download this provisioning file and open it, let it available in the Xcode
4. Open the project in Xcode, using the provisioning profile downloaded in the code sign for release option
5. Archive the project again.
6. In the organizer opened automatically after archive is done, select the archived item and press the button ‘Distribute’
7. Select Ad-Hoc, and Next
8. Select ‘Enterprise’, fill in the url with the ipa url,such as”http://somedomain.com/appname.ipa
9. And save the file exact as the name that specified in the url you typed above
10. Upload the two files generated above, one plist, one ipa, onto your web site,and located exactly as in the url you specified above.
12. Done!

After doing the above steps, you can let the target device to open your web page with Safari, and press the link. Then the device can download and install the application. And any device with jailbreak can install as well, even if it does not exist in your Devices list.

But after iOS 7, the ad-hoc deploy must with Https instead of Http
So we need to modify the url link to something like:
`itms-services://?action=download-manifest&url=https://somedomain.com/appname.plist`
And the host need to be configured with ssh access, for an apache server, you can do this with the steps in this blog.
And after you configured your server well, you need one more step, that copy your certificate generated in this blog to a public place, and use your iOS device open it with Safari, so this certificate can be installed in your device. After this, the app can be installed as well as the old days.

## Algorithm Problems: Two Sum

Manage two pointer to the array, one from the front, moving forward, the other from the rear, moving backward.
When the summation of the value pointed by the two pointer is equal to the given sum, then one solution is found;
Else if the summation is lower than the given sum, moving the lower pointer forward by 1 step;
Otherwise, moving the higher pointer backward by 1 step.
Doing this until the lower pointer meet the higher pointer.

Then the time complexity is O(n), space complexity is O(1).

Problem
Given an sorted integer array, ascending order, and a given number, find all the pairs in the array that sum to the given number.

Codes

```//
//  main.cpp
//  TwoSum
//
//  Created by Qiu Xiangyu on 12-12-20.
//

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int> > twoSum(vector<int> arr, int sum) {
vector<vector<int> > ret;
size_t low = 0, hi = arr.size() - 1;
while (low < hi) {
int vlow = arr[low];
int vhi = arr[hi];
int cursum = vlow + vhi;
if (cursum == sum) {
vector<int> sol(2,vlow);
sol[1] = vhi;
ret.push_back(sol);
++low;
} else if (cursum < sum) {
++low;
} else {
--hi;
}
}
return ret;
}

int main(int argc, const char * argv[])
{

// insert code here...
vector<int> arr = {1,2,3,4,5,6,7,8,9,10};
vector<vector<int>> ret = twoSum(arr, 11);
for (int i = 0; i < ret.size(); ++i) {
vector<int> solution = ret[i];
cout<<solution[0]<<" , "<<solution[1]<<endl;
}
cout<<"total : "<<ret.size()<<endl;
return 0;
}
```

## Algorithm Problem:Swap the left and right sub-tree in a binary tree without recursion

Just swap the tree nodes’ left and right child, in the post traversal order.

Code

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void swapLeftAndRight(TreeNode *root) {
bool forward = true;
TreeNode *pre = NULL;
stack trace;
if(root) trace.push(root);

while(trace.size()) {
TreeNode *cur = trace.top();
if(forward) {
if(cur->left && pre != cur->left) {
trace.push(cur->left);
} else {
forward = false;
}
} else {
if(cur->right && pre != cur->right) {
trace.push(cur->right);
forward = true;
} else {
//all the child has finished visit, then swap the left and right of cur
TreeNode *t = cur->left;
cur->left = cur->right;
cur->right = t;

trace.pop();
}
}
pre = cur;
}
}
};
```

## How to make a call using iOS SDK

It’s pretty simple, just one line of code:

```[[UIApplication sharedApplication] openURL:[NSURL URLWithString:@"tel:1101101110"]];
```

## Algorithm Problem:Intersection of Sorted Array

Binary search every element of arr1 in arr0, if find, append it to the output. And at each step, shrink the search range.

Intersection of Sorted Array
Find out the intersection of two sorted array

Code

<

pre>

//
// main.cpp
// Intersection of two Sorted Array
//
// Created by Qiu Xiangyu on 12-12-16.
//
// Find out the intersection of two sorted array.

# include

using namespace std;

vector getIntersection(vector &arr0, vector &arr1) {
vector ret;
if (arr0.size() == 0 || arr1.size() == 0) {
return ret;
}

```size_t low = 0;
for (size_t i1 = 0; i1 < arr1.size(); ++i1) {
int v1 = arr1[i1];
//1.find the arr1[0] in arr0 using binary search
{
size_t l = low,h = arr0.size() - 1;
while (l <= h) {
size_t m = (l + h) /2;
if (arr0[m] < v1) {
l = m + 1;
} else if (arr0[m] > v1) {
h = m - 1;
} else {
i0 = m;
break;
}
}
}
if (i0 == -1) {
continue;
} else {
//2.in case there is repeat values in arr0, move i0 towards 0 while arr0[i0] == arr1[0]
while (i0 > low && arr0[i0-1] == arr1[0]) {
--i0;
}
low = i0 + 1;
ret.push_back(v1);
}
}

return ret;```

}

int main(int argc, const char * argv[])
{

```vector<int> arr0 = {0,1,2,3,4,5,5,6,7,8,9,10};
vector<int> arr1 = {5,5,7,9};
vector<int> inte = getIntersection(arr0, arr1);
for (int i = 0; i < inte.size(); ++i) {
cout<<inte[i]<<",";
}
cout<<endl;
return 0;```

}

## LeetCode Problem:Flatten Binary Tree to Linked List

We can notice that in the flattened tree, each sub node is the successor node of it’s parent node in the pre-order of the original tree. So, we can do it in recursive manner, following the steps below:
1.if root is NULL return;
2.flatten the left sub tree of root, if there is left sub-tree;
3.flatten the right sub-tree of root, if has;
4.if root has no left sub-tree, then root is flattened already, just return;
5.we need to merge the left sub-tree with the right sub-tree, by concatenate the right sub-tree to the last node in left sub-tree.
5.1.find the last node in the left sub tree, as the left is flattened, this is easy.
5.2.concatenate the right sub-tree to this node’s right child.
5.3.move the left sub-tree to the right for root.
5.4.clear the left child of root.
6.done.

<br>
Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
For example,
Given

```         1
/ \
2   5
/ \   \
3   4   6
```

The flattened tree should look like:

```   1
\
2
\
3
\
4
\
5
\
6
```

Code:48ms to accept with large test set.

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void flatten(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (root == NULL) return;
//1.flat the left subtree
if (root->left)
flatten(root->left);
//2.flatten the right subtree
if (root->right)
flatten(root->right);
//3.if no left return
if (NULL == root->left)
return;
//4.insert left sub tree between root and root->right
//4.1.find the last node in left
TreeNode ** ptn = & (root->left->right);
while (*ptn)
ptn = & ((*ptn)->right);
//4.2.connect right sub tree after left sub tree
*ptn = root->right;
//4.3.move left sub tree to the root's right sub tree
root->right = root->left;
root->left = NULL;

}
};
```

Code rewrite at 2013-2-20, non-recursive version

```class Solution {
public:
void flatten(TreeNode *root) {
bool f = true;
stack t;
TreeNode *pre = NULL;
if(root) {
t.push(root);
}

while(t.size()) {
TreeNode *cur = t.top();
if(f) {
if(cur->left && cur->left != pre) {
t.push(cur->left);
} else {
f = false;
}
} else {
if(cur->right && cur->right != pre) {
t.push(cur->right);
f = true;
} else {
t.pop();
//at this time, the sub-tree of cur is flattened, so just flatten the cur
TreeNode *left = cur->left;
if(left) {
TreeNode *lastLeft = left;
while(lastLeft->right) {
lastLeft = lastLeft->right;
}
lastLeft->right = cur->right;
cur->right = left;
cur->left = NULL;
}
}
}
pre = cur;
}
}
};
```

## Algorithm Sqrt for Double

The binary divide is straight forward solution, but some times slow.

The Newtown solution is better, but must careful for the mathematic detail. The equation is:
xk+1 = xk – (F(xk) / F'(xk) )

PS:slope(斜率), first derivative(一阶导数)

code

<

pre>
//
// main.cpp
// Sqrt
//
// Created by Qiu Xiangyu on 12-12-16.
//

# include <math.h>

using namespace std;

//max error to guide the algorithms
const double _err = 0.000001;

//binary divide version
double mySqrtBinary(double num) {
if (num < 0) {
return NAN;
} else if (num == 0) {
return 0;
}
double sqmax = num > 1 ? num : 1.0;
double sqmin = num > 1 ? 1.0 : num;
double s = 0.5 * (sqmax + sqmin);
while (true) {
double ss = s * s;
if (fabs(ss – num) < _err) {
break;
}
if (ss > num) {
sqmax = s;
} else {
sqmin = s;
}
s = 0.5 * (sqmax + sqmin);
}
return s;
}

//newtown
double mySqrtNewtown(double num) {
if (num < 0) {
return NAN;
}
double s = num;
while (true) {
double ss = s * s;
double f0 = ss – num;
if (fabs(f0) < _err) {
break;
}
cout<<s<<endl;
s = s – f0 / (2.0 * s);
}
return s;
}

int main(int argc, const char * argv[])
{
// insert code here…
std::cout << mySqrtNewtown(0);
return 0;
}

## Algorithm Problem: Coins,Integer Bag Problem using Dynamic Programming

We can calculate the result by dynamic programming.

When there is only one coin valued 1, there is only one way to sum up to the money.
How about the coin valued 2 is available ? We can use the coin2 by count of 0,1,…,Sum/2, and using coin1 for the rest of money which is already calculated by the former step.
Generally, when we already calculated the ways with using the first k types of coins for the money 0,1,…,Sum. When the k+1 types of coin is available, the ways for a certain sum of money tSum is the sum ways of using 0 of new coins, 1 of new coins, 2 of new coins,… and handle the rest of money by first k types of coins, while the rest of money is none-negative.

Then we can get the code below.

Coins or Bags
There are some coins valued 1,2,5,20,50,100. Given a sum of money Sum, how many ways are there by using these coins to sum up to the given money.
The classic integer bag problem is similar to this problem.

Codes:Recur version and Dynamic version

<

pre>

//
// main.cpp
// 背包问题
//
// Created by Qiu Xiangyu on 12-12-15.
//

// 类似背包问题
// 有一些面值的硬币，1 2 5 20 50 100，要求给出凑足某个数目的钱，总共多少方法

# include

using namespace std;

static const int types = 6;
const int coins[types] = {1,2,5,20,50,100};
int waysRecur(int total, int maxAllowType) {
if (maxAllowType <= 0) {
return 1;
}
int maxCoin = coins[maxAllowType];
int ways = 0;
for (int i = 0; i <= total / maxCoin; ++i) {
ways += waysRecur(total – i * maxCoin, maxAllowType – 1);
}
return ways;
}

int waysDp(int sum) {
if (sum <= 0) {
return 1;
}
//1.build a 2-d array to hold the results
int * ways[types];
for (int it = 0 ; it < types; ++it) {
ways[it] = new int[sum + 1];
}
for (int is = 0; is <= sum; ++is) {
ways[0][is] = 1;
}
//2.dp from types 1 to types – 1 to calculate the ways
for (int it = 1; it < types; ++it) {
int coinValue = coins[it];
for (int is = 0; is <= sum; ++is) {
ways[it][is] = 0;
for (int itime = 0; itime * coinValue <= is; ++itime) {
int remain = is – itime * coinValue;
ways[it][is] += ways[it-1][remain];
}
}
}
//3.return the result
int ret = ways[types – 1][sum];
for (int it = 0 ; it < types; ++it) {
delete ways[it];
}
return ret;
}

int main(int argc, const char * argv[])
{
int total = 111;
int ways = waysRecur(total, types – 1);
int wdp = waysDp(total);
cout<<“ways from recur:”<<ways<<endl;
cout<<“ways from dp:”<<wdp<<endl;
return 0;

```/*
5:{1,1,1,1,1},{1,1,1,2},{1,2,2},{5}
it=0:{1,1,1,1,1}
it=1:{1,1,2,2,3}
it=2:{1,1,2,2,4}
*/```

}

## LeetCode Problem:Distinct Subsequences

(2013-1-5更新了动态规划版本，见下面)

1·先试试看从T的size上简化看看。写一个例子S = aaaaa,T = a，很简单，数数就行。然后T=aa，发现没有太好的方法，怎么弄也算不出来最后结果。但是如果第一步查找记录下了所有的位置的话，只需要看该位置后面还有没出现T[1]就好了。比如S=aaba,T=ab，那么第一步查找得到{0,1,3}，第二步只需要在这个集合内查看，S[0]后面有没有b，S[1]后面有没有b，S[3]后面有没有b。最后得到{02,12}两个结果。这样有了一个初步的算法，只不过非常消耗内存。小集合可以过，大集合内存超过限制。
2·内存如何超限的呢？比如当S=aaaa,T=aaa，的时候，第一轮结果{0,1,2,3},第二轮就变成了{01,02,03,12,13,23}，可以看到，如果S再长一点的话，是很恐怖的。但是实际上从这里也能看出一点问题，就是02，12是可以合并的，因为下次它两个都会去查找S[2]之后有没有T[2]，而且得到的结果是一样的。如果合并的话，不仅空间省了，时间也省了。所以就可以用一个int数组，记录在当前时刻（查找过程中T的下标），在S的某个位置结束的成功匹配个数。比如这个数组叫做matches，和S等大。那么第一轮下来matches[i] = (S[i] == T[0])。第二轮开始，针对每一个j = 1 … T.size() – 1，对matches中记录的每一个结束点去往后查找T[j]，找到的话（比如在S[ii] == T[j])，那么新的matches[ii] += matches[i]。所以这里需要两个数组来回倒腾。最后写出代码220ms过了大集合测试。空间复杂度O(S.size())，时间复杂度O(S.size() * S.size() * T.size())。而且在查找的时候还可以简化，这样整体时间复杂度可以变成O(S.size() * T.size())

Distinct Subsequences
Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ACE” is a subsequence of “ABCDE” while “AEC” is not).
Here is an example:
S = “rabbbit”, T = “rabbit”
Return 3.

```class Solution {
public:
int numDistinct(string S, string T) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (T.size() == 0 || S.size() == 0 || S.size() < T.size())
return 0;

//at each position i in S, how many matches could be found with the substring end at S[i]
int *matches = new int[S.size()];
//temporary array for updating matches.
int *mtemp = new int[S.size()];

//1.initialize
for(int i = 0; i < S.size(); ++i) {
matches[i] = (S[i] == T[0] ? 1 : 0);
mtemp[i] = 0;
}

for(int j = 1; j < T.size(); ++j) {
const char tj = T[j];//process the char T[j]
for(int ilast = 0; ilast < S.size(); ++ilast) {
if (matches[ilast] == 0)//no possible matches
continue;
for(int i = ilast + 1; i < S.size(); ++i) {
if(S[i] == tj) {
mtemp[i] += matches[ilast];//and the match count in ilast to new location
}
}
}
for(int ilast = 0; ilast < S.size(); ++ilast) {
matches[ilast] = 0;
}
int * t = matches;//switch matches and mtemp
matches = mtemp;
mtemp = t;
}

int sum = 0;
for(int i = 0; i < S.size(); ++i) {
sum += matches[i];
}
return sum;
}
};
```

```class Solution {
public:
int numDistinct(string S, string T) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (T.size() == 0 || S.size() == 0)
return 0;
queue pls;//possible location start index in S

//1.inite pls by searchin T[0] in S
for(int i = 0; i < S.size(); ++i) {
if (S[i] == T[0]) {
pls.push(i);
}
}
//2.one by one search T[j] in S, update the loast match index in pls or remove if no match fould
const int levelEnd = -1;
int j = 1;
if(pls.size() && j < T.size()) pls.push(levelEnd);
while(pls.size() && j < T.size()) {
if(pls.size() > 1000) return 1000;
char tj = T[j];
int lasti = pls.front();
pls.pop();
if (lasti == levelEnd) {
++j;
if (j == T.size())
break;
if(pls.size()) pls.push(levelEnd);
} else {
for(int i = lasti + 1; i < S.size(); ++i) {
if(S[i] == tj) {
pls.push(i);
}
}
}
}

//3.finished
return pls.size();
}
};
```

<br>
Code rewrite at 2013-1-5

```class Solution {
public:
int numDistinct(string S, string T) {
if(S.size() < T.size()) return 0;
if(T.size() == 0) return 0;
vector > ways (S.size(), vector(T.size(),0));
//the first column
ways[0][0] = (S[0] == T[0] ? 1 : 0);
for(int is = 1; is < S.size(); ++is) {
ways[is][0] = ways[is-1][0];
if(T[0] == S[is]) {
ways[is][0] += 1;
}
}
//the remaining triangle
for(int it = 1; it < T.size(); ++it) {
//the item on the diagonal
ways[it][it] = (S[it] == T[it] ? ways[it-1][it-1] : 0);
//the items below
for(int is = it + 1; is < S.size(); ++is) {
ways[is][it] = ways[is-1][it];
if(S[is] == T[it]) {
ways[is][it] += ways[is-1][it-1];
}
}
}
return ways[S.size()-1][T.size()-1];
}
};
```

```class Solution {
public:
int numDistinct(string S, string T) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(S.size() < T.size()) return 0;
if(T.size() == 0) return 0;
int *ways = new int[S.size()];
int *waysTemp = new int[S.size()];
//the first charactor for T
ways[0] = (S[0] == T[0] ? 1 : 0);
for(int is = 1; is < S.size(); ++is) {
ways[is] = ways[is-1];
if(T[0] == S[is]) {
ways[is] += 1;
}
}
//the remaining charactors in T
for(int it = 1; it < T.size(); ++it) {
//the item on the diagonal
waysTemp[it] = (S[it] == T[it] ? ways[it-1] : 0);
//the items below
for(int is = it + 1; is < S.size(); ++is) {
waysTemp[is] = waysTemp[is-1];
if(S[is] == T[it]) {
waysTemp[is] += ways[is-1];
}
}
int *temp = ways;
ways = waysTemp;
waysTemp = temp;
}
int ret = ways[S.size()-1];
delete ways;
delete waysTemp;
return ret;
}
};
```

code rewrite at 2013-1-14, 36ms pass the large test

```/*
Let ways(x,y) denote that from first x characters in S to first y characters in T needs ways(x,y) distinct ways.
then if we knew ways(i,j), i < n, i < m, then
ways(n,m) = S[n-1] == T[m-1] ? ways(n-1,m-1) + ways(n-1,m) : ways(n-1,m)
ways(x,0) = x; x = 0,...,S.size()
ways(y,y) = S[y-1] == T[y-1] ? ways(y-1,y-1) : 0; y = 1,...,T.size()
*/
class Solution {
public:
int numDistinct(string S, string T) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(S.size() < T.size()) return 0;
int *ways = new int[S.size() + 1];
int *waystemp = new int[S.size() + 1];
for(int i = 0; i <= S.size(); ++i) {
ways[i] = 1;
}
for(int lent = 1; lent <= T.size(); ++lent) {
waystemp[lent] = (S[lent-1] == T[lent-1] ? ways[lent-1] : 0);
for(int lens = lent + 1; lens <= S.size(); ++ lens) {
waystemp[lens] = waystemp[lens - 1];
waystemp[lens] += (S[lens-1] == T[lent-1] ? ways[lens-1] : 0);
}
int *temp = ways;
ways = waystemp;
waystemp = temp;
}
int ret = ways[S.size()];
delete ways;
delete waystemp;
return ret;
}
};
```

## 题目：Max Ascending

<

pre>
//
// main.cpp
// MaxAscend
//
// Created by Qiu Xiangyu on 12-12-14.
//

//一个数组a[n] 求max(ai-aj), i<j

# include

using namespace std;
int maxAscend(vector nums) {
if (nums.size() <= 1) {
return 0;
}
int ret = nums[1] – nums[0];//the result
int vmin = nums[0];//track the current min
for (int i = 1; i < nums.size(); ++i) {
int v = nums[i];
if (vmin > v) {
vmin = v;
}
if (ret < v – vmin) {
ret = v – vmin;
}
}
return ret;
}

int main(int argc, const char * argv[])
{
vector testarr = {1,4,2,5,7,0};
int md = maxAscend(testarr);
cout<<“Max difference is “<<md<<endl;
return 0;
}

## LeetCode题目：Convert Sorted List to Binary Search Tree

Convert Sorted List to Binary Search Tree
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

```/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
TreeNode *formTree(ListNode *head, int count) {
if(count <= 0) return NULL;
int rootIndex = count / 2;
ListNode *rootNode = head;
for(int ir = 0; ir < rootIndex; ++ir) {
rootNode = rootNode->next;
}
TreeNode *root = new TreeNode(rootNode->val);
root->right = formTree(rootNode->next, count - rootIndex - 1);
return root;
}
public:
TreeNode *sortedListToBST(ListNode *head) {
// Start typing your C/C++ solution below
// DO NOT write int main() function

//1. find the node count, takes O(n) time
int nodeCount = 0;
for(ListNode *cur = head; cur != NULL; cur = cur->next) {
++nodeCount;
}

//2. form the tree with the middle as the root
}
};
```

## LeetCode题目：Convert Sorted Array to Binary Search Tree

Convert Sorted Array to Binary Search Tree
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
TreeNode *sortedArrayToBST(vector &num,int si, int ei) {
if(si > ei) return NULL;
int mid = (ei + si) / 2;
TreeNode *root = new TreeNode(num[mid]);
root->left = sortedArrayToBST(num,si,mid - 1);
root->right = sortedArrayToBST(num,mid + 1,ei);
return root;
}

public:
TreeNode *sortedArrayToBST(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
return sortedArrayToBST(num,0,num.size() - 1);
}
};
```

## LeetCode题目：Construct Binary Tree from Inorder and Postorder Traversal

Construct Binary Tree from Inorder and Postorder Traversal
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode *buildTree(vector &iorder, int isi, int iei, vector &porder, int psi, int pei) {
if(iei - isi < 0 || iei - isi != pei - psi) {
return NULL;
}
//the porder[pei] is the root of this tree
TreeNode *root = new TreeNode(porder[pei]);
//find the root in the iorder to seperate it into left sub tree and right sub tree
int riii = -1;//root index in inorder array
for(int i = isi; i <= iei; ++i) {
if(iorder[i] == root->val) {
riii = i;
break;
}
}
if(riii == -1) return root;//error
int lnodes = riii - isi;
//for the left sub tree
//the isi to riii - 1 in inorder array will be it's inorder traversal
//and the psi to psi + lnodes - 1 in postorder array will be it's post order traversal
root->left = buildTree(iorder, isi, riii - 1, porder, psi, psi + lnodes - 1);
//for the right sub tree is similary to the left
root->right = buildTree(iorder, riii + 1, iei, porder, psi + lnodes, pei - 1);
return root;
}
TreeNode *buildTree(vector &inorder, vector &postorder) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
return buildTree(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() -1);
}
};
```

## LeetCode题目：Construct Binary Tree from Preorder and Inorder Traversal

```   1
/   \
2     3
\    /
4  5
```

Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
typedef TreeNode TN;
class Solution {
TN *buildTree(vector &preorder,int psi,int pei,
vector &inorder, int isi, int iei) {
if(pei - psi < 0 || pei - psi != iei - isi)
return NULL;
//root of sub tree
TN *root = new TN(preorder[psi]);
//find this value in inorder to locate the root in inorder
int riii = -1;//root index in inorder
for(int itemp = isi; itemp <= iei; ++ itemp) {
if(inorder[itemp] == root->val) {
riii = itemp;
break;
}
}
if(riii != -1) {
//calculate the nodes count in left tree
int leftCount = riii - isi;
TN *left = buildTree(preorder,psi + 1, psi + leftCount, inorder, isi, riii - 1);
root->left = left;
TN *right = buildTree(preorder,psi + leftCount + 1,pei, inorder, riii + 1, iei);
root->right = right;
}
return root;
}
public:
TreeNode *buildTree(vector &preorder, vector &inorder) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
TN *root = buildTree(preorder,0,preorder.size() - 1,inorder,0,inorder.size() - 1);
}
};
```

## LeetCode题目：Binary Tree Zigzag Level Order Traversal

Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree {3,9,20,#,#,15,7},

```    3
/ \
9  20
/  \
15   7
```

return its zigzag level order traversal as:

```[
[3],
[20,9],
[15,7]
]
```

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector > zigzagLevelOrder(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > ret;
if(NULL == root) return ret;

queue que;
que.push(root);
que.push(NULL);//level end point

bool l2r = true;//left to right

vector level;
while(true) {
TreeNode *cur = que.front();
que.pop();
if(cur) {
level.push_back(cur->val);
if(cur->left) que.push(cur->left);
if(cur->right) que.push(cur->right);
} else {
if(l2r) {
ret.push_back(level);
} else {
vector temp;
for(int i = level.size() - 1 ; i >= 0; --i) {
temp.push_back(level[i]);
}
ret.push_back(temp);
}
level.erase(level.begin(),level.end());
l2r = !l2r;

if(que.size() == 0) break;
que.push(NULL);
}
}

return ret;
}
};
```

## LeetCode题目：Binary Tree Maximum Path Sum

1.终止在这个节点上（往自己子树走）的最大路径值是多少
2.经过这个节点的最大值是多少？（从左子树走过自己到右子树）
3.不经过此节点的子树中可能获得的最大值是多少？

1.终止在此节点的最大路径，首先是自己的值包含进去，然后如果终止在左或右子树的根节点的最大路径值大于0的话，加上这个值。
2.经过这个节点的最大值，很简单了，左右子树的端点最大值加上自己的值。
3.不经过此节点的最大值，直接查看左右子树中的这个值（如果有左右子树的话），还有左右子树的端点最大值。

2013-1-18，更新了一个更简单的办法.

# Question: Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,

```       1
/ \
2   3
```

Return 6.

# 代码:

## 248ms过大集合

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Maxes{
public:
int tmax;//max of terminated in self
int pmax;//max of pass self
int nmax;//max of non-relative to self
Maxes() {tmax = pmax = 0; nmax = (1 << (sizeof(int) * 8 - 1));}
inline int getMax() {
int m = tmax;
if(m < pmax) m = pmax;
if(m < nmax) m = nmax;
return m;
}
};
class Solution {
public:
Maxes maxPath(TreeNode *root) {
Maxes m;
if(NULL == root)
return m;

Maxes l = maxPath(root->left);
Maxes r = maxPath(root->right);

//tmax is the max value which terminated at this node
//when all of it's children is negative, this is it's value
//or add the max value terminated at it's children
m.tmax = max(l.tmax,r.tmax);
if(m.tmax < 0) m.tmax = 0;
m.tmax += root->val;

//pmax is the max value which is pass this node
//that is it's value terminated at it's children (if have, or zero), add self value
m.pmax = l.tmax + r.tmax + root->val;

//nmax is the max value which not including current node
if(root->left)
m.nmax = l.getMax();
if(root->right) {
int rmax = r.getMax();
if(m.nmax < rmax) m.nmax = rmax;
}
return m;
}
int maxPathSum(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
Maxes m = maxPath(root);
int ma = m.getMax();
return ma;
}
};
```

## Code rewrite at 2013-1-18, 266ms pass large set, simpler

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
int _curMax;
//return the max path ending in root
//and refresh the _curMax with the path sum that go through from left to root to right child.
int maxWithRoot(TreeNode *root) {
if(NULL == root) return 0;
int leftmax = maxWithRoot(root->left);
int rightmax = maxWithRoot(root->right);

//the max from left child to right child, accross from root
int arcmax = root->val;
if(leftmax > 0) arcmax += leftmax;
if(rightmax > 0) arcmax += rightmax;
if(_curMax < arcmax) _curMax = arcmax;

//the max that end in root
int pathmax = root->val;
int submax = std::max(leftmax,rightmax);
if(submax > 0) pathmax += submax;
if(_curMax < pathmax) _curMax = pathmax;

return pathmax;
}
public:
int maxPathSum(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
_curMax = INT_MIN;
maxWithRoot(root);
return _curMax;
}
};
```

## LeetCode题目：Binary Tree Level Order Traversal II

Binary Tree Level Order Traversal II
Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree {3,9,20,#,#,15,7},

```    3
/ \
9  20
/  \
15   7
```

return its bottom-up level order traversal as:

```[
[15,7]
[9,20],
[3],
]
```

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector > levelOrderBottom(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
list > retTemp;

queue trace;
trace.push(root);
trace.push(NULL);

vector curLevel;
while(true) {
TreeNode *cur = trace.front();
trace.pop();
if(cur) {
curLevel.push_back(cur->val);
if(cur->left) trace.push(cur->left);
if(cur->right) trace.push(cur->right);
} else {
if(curLevel.size()) {
retTemp.push_front(curLevel);
curLevel.erase(curLevel.begin(),curLevel.end());
trace.push(NULL);
} else {
break;
}
}
}

vector > ret;
for(list >::iterator it = retTemp.begin(); it != retTemp.end(); ++it) {
ret.push_back(*it);
}
return ret;
}
};
```

## LeetCode题目：Binary Tree Level Order Traversal

Binary Tree Level Order Traversal
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,#,#,15,7},

```    3
/ \
9  20
/  \
15   7
```

return its level order traversal as:
[
[3],
[9,20],
[15,7]
]

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector > levelOrder(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > ret;
if(NULL == root) return ret;
queue trace;
trace.push(root);
trace.push(NULL);
vector levelVals;
while(true) {
TreeNode *cur = trace.front();
trace.pop();
if(NULL == cur) {
ret.push_back(levelVals);
levelVals.erase(levelVals.begin(),levelVals.end());
if(trace.size())
trace.push(NULL);
else
break;
} else {
levelVals.push_back(cur->val);
if(cur->left) trace.push(cur->left);
if(cur->right) trace.push(cur->right);
}
}
return ret;
}
};
```

Code rewrite at 2012-12-22, 24ms pass the large test set

```class Solution {
public:
vector > levelOrder(TreeNode *root) {
vector > ret;

queue q;
if(root) {
q.push(root);
q.push(NULL);
}

vector level;
while(q.size()) {
TreeNode *cur = q.front();
q.pop();
if(cur) {
level.push_back(cur->val);
if(cur->left) q.push(cur->left);
if(cur->right) q.push(cur->right);
} else {
ret.push_back(level);
level.erase(level.begin(),level.end());
if(q.size()) q.push(NULL);
}
}

return ret;
}
};
```

## LeetCode题目：Best Time to Buy and Sell Stock III，一维动态规划

Best Time to Buy and Sell Stock III
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

```class Solution {
public:
int maxProfit(vector &prices) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(prices.size() <= 1)
return 0;

//stores the max profit in [0, ... , i] subarray in prices
vector maxEndWith;
{//build the maxEndWith.
int lowest = prices[0];
int maxprofit = 0;
maxEndWith.push_back(0);
for(int i = 1; i < prices.size(); ++i) {
int profit = prices[i] - lowest;
if(profit > maxprofit) {
maxprofit = profit;
}
maxEndWith.push_back(maxprofit);
if(prices[i] < lowest) lowest = prices[i];
}
}

int ret = maxEndWith[prices.size() - 1];
{//reverse to see what is the maxprofit of [i, ... , n-1] subarray in prices
//and meanwhile calculate the final result
int highest = prices[prices.size() - 1];
int maxprofit = 0;
for(int i = prices.size() - 2; i >= 0; --i) {
int profit = highest - prices[i];
if(profit > maxprofit)  maxprofit = profit;
int finalprofit = maxprofit + maxEndWith[i];
if(finalprofit > ret) ret = finalprofit;
if(prices[i] > highest) highest = prices[i];
}
}

return ret;
}
};
```

## LeetCode题目：Best Time to Buy and Sell Stock II

Best Time to Buy and Sell Stock II
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

```class Solution {
public:
int maxProfit(vector &prices) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int p = 0;
for(int i = 1; i < prices.size() ; ++i) {
int delta = prices[i] - prices[i-1];
if(delta > 0 ) {
p += delta;
}
}
return p;
}
};
```

## LeetCode题目：Best Time to Buy and Sell Stock

O(n)

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.

```class Solution {
public:
int maxProfit(vector &prices) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (prices.size() <= 1)
return 0;
int low = prices[0];
int maxp = 0;
for(int i = 1; i < prices.size(); ++i) {
int profit = prices[i] - low;
if(maxp < profit) maxp = profit;
if(low > prices[i]) low = prices[i];
}
return maxp;
}
};
```