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.
上一题LeetCode Problem: Populating Next Right Pointers in Each Node, Level traversal of binary tree的答案对这个题目仍然是适用的。



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.
题目相对简单,用一个队列来进行广度优先遍历就可以了,用一个NULL来指示每一层的结束。



Populating Next Right Pointers in Each Node
Given a binary tree
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}
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.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

include

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
//  AddTwoUnsingedInteger
//
//  Created by Qiu Xiangyu on 12-12-21.
//  Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

#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.
  11. Make a url link on your website like”itms-services://?action=download-manifest&url=http://somedomain.com/appname.plist
  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.
//  Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

#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;
        }
    }
};

iOS开发和服务器通讯遇到的编码问题

今天遇到一个bug,是服务器那边传过来的用UTF8编码之后的Json字符串,解UTF8之后,Json解析失败。

然后打印源字符串,其中会遇到很多的\200\213\123这样的内容导致解析失败。

其实这是假象。

在突发奇想将每个遇到的\替换成\\之后,问题解决了,解决了了···

但是再后来,发现这个做法有点过,就是其实还有一些正常的\不应该被变成\\,于是想到用正则表达式去匹配和替换。

用前向断言正则匹配\\(?=\d{3})去匹配,发现没有一个被匹配出来,而眼睁睁的看着打出的log里面确实是有\ddd\ddd\ddd这样的内容的,也确实就是这样的内容导致了json解析失败。

然后百思不得其解,千思也不得其解。终于忍了,自己写了一个字符串匹配替换,才发现问题的根源不在与\ddd\ddd\ddd,而在于\&,在debug窗口打出来的log和源字符串是不一样的····完全没有一个斜杠跟着3个数字的问题,出现的只有两种斜杠,\n\&。。。

后来吧\&替换成\\&就ok了。

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.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//
// Find out the intersection of two sorted array.

include

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 i0 = -1;//not found
    {
        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.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

include

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.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

// 类似背包问题
// 有一些面值的硬币,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.



代码:220ms过大集合

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;
    }
};



代码1:小集合可以过,大集合内存超过

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
重写一次,用了动态规划搞定,时间复杂度是O(S.size() * T.size())

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];
    }
};



上面的代码用了O(S.size() * T.size())的空间,实际上没有必要,只需要2 * S.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;
        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

问题比较简单,就是一个数组a[n] 求max(ai-aj), i<j.

从前往后扫描,记录下当前的最小值,每次计算aj – ai,然后更新这个最大值。扫描完就得到了结果,时间复杂度O(n)

<

pre>
//
// main.cpp
// MaxAscend
//
// Created by Qiu Xiangyu on 12-12-14.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

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

include

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

问题比上一个难一点,如果是可以用O(n)空间的话,倒是可以开一个数组放上这n个数,然后按上一个问题的解法去做。总体时间O(n),空间O(n)。

不过这题这样出应该不是这个意思。假如不用O(n)空间的话:
可以先数一下一共有多少个节点。O(n)时间。
然后去找到根节点(数数),然后根节点之前是左子树,之后是右子树,并且两个子树的节点个数都是可以直接计算出来的,递归解这个问题就可以了。
那么总体时间复杂度是O(n*logn),空间O(logn)



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.



代码:114ms过大集合

/**
 * 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->left = formTree(head,rootIndex);
        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
        return formTree(head, nodeCount);
    }
};

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.



代码:84ms过大集合

/**
 * 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

这题和上一道题类似,也是首先在postorder中,最后那一个肯定是整棵树的根,然后在inorder中查找这个根,找到之后就能确定左子树和右子树的后序遍历和中序遍历,然后递归求解。



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.



代码:120ms过大集合

/**
 * 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

这棵树好用,在于其中包含了所有的可能性,(2度,1度(左右),0度节点都有)。
它的preorder是:1,2,4,3,5
他的inorder是:2,4,1,5,3


那么递归的看这个问题,首先preorder的第一个必然是根(1),然后此节点在inorder中的下标是2,那么在inorder中,处于1之前的两个节点2,4是左子树的;反之5,3是右子树的。
针对左子树,2,4就是它的inorder,而在preorder中,除开第一个根,数两个节点的子序列正好是2,4,这是左子树的preorder。这样这个问题就自然变成递归了:
即,其左子树的preorder是(2,4),inorder是(2,4);类似有右子树preorder(3,5),inorder(5,3)。
然后边界情况是某数的preorder和inorder遍历的长度都是1,比如{x},那么这棵树就是以x为值的节点。
这样就可以写出代码了。



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.



代码:124ms过大集合

/**
 * 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

比较简单,广度优先变一下就可以了,用一个bool记录是从左到右还是从右到左,每一层结束就翻转一下。



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]
]



代码:28ms过大集合

/**
 * 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

这道题好难,因为在一颗二叉树中有多种情况,这条最长的路径有可能是从某个中间节点直接到某个叶子节点的,也有可能是两条上述路径连接在一个中间节点上(这个中间节点可能是root也可能不是),也有可能只是一个单独的节点。

情况太多导致问题很复杂,不好分析,这题花了我至少两个小时去解决。

一开始从自上而下的方法去想,想到了可以计算出每一个节点到root的最大值,然后最后拼一下最大值,得到整体最大。但是这里假设了路径都是过root的。显然不对。

然后想level优先遍历的话,如果知道了上面的情况,下面一层可解么?陷入死胡同至少30min,gg。

然后想自下而上,如果知道了左右子树的情况,自身的情况能得到么?很快就有了肯定回答。
但是这个solution也相对复杂,针对每个节点需要知道的是:
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

和上一题差不多,只不过最后输出的时候颠倒一下,另外:std::list才有push_front(),而std::vector没有这个方法。



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],
]



代码:40ms过大集合

/**
 * 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

题目简单,经典方法。只不过这题需要每一个level单独作为一个vector输出,因此在每一个level结束的时候插入一个NULL标记。每当遇到这个标记,就说明一层已经完全访问了。



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]
]



代码:28ms过大集合

/**
 * 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,一维动态规划

和前两道题比起来的话,这道题最难了,因为限制了交易次数。
解决问题的途径我想出来的是:既然最多只能完成两笔交易,而且交易之间没有重叠,那么就divide and conquer。
设i从0到n-1,那么针对每一个i,看看在prices的子序列[0,…,i][i,…,n-1]上分别取得的最大利润(第一题)即可。
这样初步一算,时间复杂度是O(n2)。


改进:
改进的方法就是动态规划了,那就是第一步扫描,先计算出子序列[0,…,i]中的最大利润,用一个数组保存下来,那么时间是O(n)。
第二步是逆向扫描,计算子序列[i,…,n-1]上的最大利润,这一步同时就能结合上一步的结果计算最终的最大利润了,这一步也是O(n)。
所以最后算法的复杂度就是O(n)的。



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).



代码:12ms过大集合,一次性bug free,很happy

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

这个更简单了,题目要求可以多次买卖,但是同一时间只能有一股在手里。
这样就可以在每次上升子序列之前买入,在上升子序列结束的时候卖出。相当于能够获得所有的上升子序列的收益。
而且,对于一个上升子序列,比如:5,1,2,3,4,0 中的1,2,3,4序列来说,对于两种操作方案:
一,在1买入,4卖出;
二,在1买入,2卖出同时买入,3卖出同时买入,4卖出;
这两种操作下,收益是一样的。


所以算法就是:从头到尾扫描prices,如果i比i-1大,那么price[i] – price[i-1]就可以计入最后的收益中。这样扫描一次O(n)就可以获得最大收益了。



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).



代码:44ms过大集合

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.



代码:52ms过大集合

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;
    }
};