月光睡在树梢上: 2012

Thursday, December 13, 2012

[leetcode] mimimum depth of binary tree

Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

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

if (!root)
return 0;

queue my_queue;
my_queue.push(root);
my_queue.push(NULL);
int depth = 0, min_depth = 9999;

while (!my_queue.empty())
{
TreeNode *front = my_queue.front();

my_queue.pop();

if (!front)
depth++;
else
{
if (!front->left && !front->right)
{
if (min_depth > depth)
min_depth = depth;
}
if (front->left) my_queue.push(front->left);
if (front->right) my_queue.push(front->right);
front = my_queue.front();
if (!front) my_queue.push(NULL);
}
}

min_depth++;

return min_depth;
}
};

[leetcode] maximum depth of binary tree

Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

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

if (!root)
return 0;

// level traversal

queue my_queue;

my_queue.push(root);
my_queue.push(NULL); // a dummy node

int depth = 0;

while (!my_queue.empty())
{
TreeNode *front = my_queue.front();
my_queue.pop();
if (!front)
{
depth++;
}
else
{
if (front->left) my_queue.push(front->left);
if (front->right) my_queue.push(front->right);
front = my_queue.front();
if (!front) my_queue.push(NULL);
}
}

// reduce by 1 because of the last dummy node
depth--;

return depth;
}
};

Wednesday, December 12, 2012

[leetcode] longest common prefix

Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

这个简单，差不多一遍通过：）

class Solution {
public:
string longestCommonPrefix(vector &strs) {
// Start typing your C/C++ solution below
// DO NOT write int main() function

if (strs.empty())
{
return string("");
}

// first find the minimum string length
int min_len = strs[0].length();

for (int i = 0; i < strs.size(); i++)
{
if (min_len > strs[i].length())
min_len = strs[i].length();
}

// compare staring at [min_len-1]
int length = 0;
for (int index = 0; index < min_len; index++)
{
bool all_equal = true;
for (int cur = 1; cur < strs.size(); cur++)
{
if (strs[cur-1][index] != strs[cur][index])
{
all_equal = false;
break;
}
}
if (all_equal)
length = index + 1;
else
break;
}

return strs[0].substr(0,length);
}
};

[leetcode] count and say

Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the n^th sequence.

Note: The sequence of integers will be represented as a string.

class Solution {
public:
string countAndSay(int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function

string str = "1";

if (n == 1)
return str;

for (int i = 1; i < n; i++)
{
string new_str = "";
int count = 0;
char ch, pre = '0';
bool flag = false;

for (int k = 0; k < str.length(); k++)
{
ch = str[k];

if (ch == pre || k == 0)
{
count++;
}

if ( (k > 0 && ch != pre ) || k == str.length()-1)
{
flag = true;
}

if (flag)
{
// update new_str
char tmp = '0' + count;
new_str += tmp;
if (k > 0)
new_str += pre;
else
new_str += ch;
count = 1;
flag = false;
}

// check the last character
if ( k > 0 && k == str.length()-1 && ch != pre)
{
// we know we have to process the
new_str += '1';
new_str += ch;
}

pre = ch;
}

// update str
str = new_str;
}

return str;
}
};

Monday, December 10, 2012

[leetcode] unique binary search trees

Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

class Solution {
public:
int numTrees(int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int cache[n];

for (int i = 0; i < n; i++)
cache[i] = 0;

cache[0] = 1;

for (int i = 1; i < n; i++)
{
// compute the count for N = i+1 nodes
int count = 0;
for (int k = 0; k <= i; k++)
{
// assume [0..i] is computed
// pick k as the root
int left_sum = 1, right_sum = 1;

if (k > 0)
left_sum = cache[k-1];

if (k < i)
right_sum = cache[i-k-1];

count += left_sum*right_sum;
}
cache[i] = count;
}

return cache[n-1];
}
};

[leetcode] flatten binary tree to linked list

Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

The flattened tree should look like:

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

// use a 'pre' pointer to track the predecessor of the current node
// use pre-order traversal

if (!root)
return;

stack my_stack;
TreeNode *pre = NULL;

my_stack.push(root);
while (!my_stack.empty())
{
TreeNode *p = my_stack.top();

// visit p
if (pre)
{
pre->right = p;
pre->left = NULL;
}

pre = p;

// pop current node
my_stack.pop();

// push right and left children into stack
if (p->right) my_stack.push(p->right);
if (p->left) my_stack.push(p->left);
}
}
};

[leetcode] search for a range

Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

class Solution {
public:
vector searchRange(int A[], int n, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function

// binary search in the given array
int start = 0, end = n-1, mid;
vector result;
bool is_found = false;
int c1 = -1, c2 = -1;

while (start <= end)
{
mid = (start + end) / 2;

if (target == A[mid])
{
is_found = true;
break;
}
else if (target > A[mid])
start = mid + 1;
else
end = mid - 1;

}

if (is_found)
{
// move cursors
c1 = mid, c2 = mid;
while (A[c1] == target && c1 >= 0)
c1--;
while (A[c2] == target && c2 < n)
c2++;
c1++;
c2--;
}

result.push_back(c1);
result.push_back(c2);

return result;
}
};

Sunday, December 9, 2012

用栈操作遍历二叉树的方法

先序遍历。将根节点入栈，考察当前节点（即栈顶节点），先访问当前节点，然后将其出栈（已经访问过，不再需要保留），然后先将其右孩子入栈，再将其左孩子入栈（这个顺序是为了让左孩子位于右孩子上面，以便左孩子的访问先于右孩子；当然如果某个孩子为空，就不用入栈了）。如果栈非空就重复上述过程直到栈空为止，结束算法。

中序遍历。将根节点入栈，考察当前节点（即栈顶节点），如果其左孩子未被访问过（有标记），则将其左孩子入栈，否则访问当前节点并将其出栈，再将右孩子入栈。如果栈非空就重复上述过程直到栈空为止，结束算法。

后序遍历。将根节点入栈，考察当前节点（即栈顶节点），如果其左孩子未被访问过，则将其左孩子入栈，否则如果其右孩子未被访问过，则将其右孩子入栈，如果都已经访问过，则访问其自身，并将其出栈。如果栈非空就重复上述过程直到栈空为止，结束算法。

[leetcode] binary tree maximum path sum

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.

Here I consider a recursive solution. We update the 'val' field of each node with the path sum ending at that node (starting from any one of its descendants). We keep a 'max_sum' variable to save the current maximum path sum. We update this variable using paths going through the node, paths ending at this node, and the single-node path. We traverse the binary tree once, so the time complexity is O(n).

/**
* 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 max_path_helper(TreeNode *root, int &max_sum)
{
if (!root) return;
else
{
max_path_helper(root->left, max_sum);
max_path_helper(root->right, max_sum);

int left_sum = 0, right_sum = 0;
if (root->left)
left_sum = (root->left)->val;
if (root->right)
right_sum = (root->right)->val;

// update max sum
int sum = left_sum + right_sum + root->val;
int sum_left = left_sum + root->val;
int sum_right = right_sum + root->val;

if (max_sum < sum)
max_sum = sum;

if (max_sum < sum_left)
max_sum = sum_left;

if (max_sum < sum_right)
max_sum = sum_right;

if (max_sum < root->val)
max_sum = root->val;

// compare with child sums and single value at this node
int tmp = 0;
if (left_sum > right_sum)
tmp = root->val + left_sum;
else
tmp = root->val + right_sum;

// update value
if (tmp > root->val)
root->val = tmp;
}

}

int maxPathSum(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function

// current max sum
int max_sum = -999;

// for each node, compute the max sum of the path starting at this node
// update max_sum using the max_sum's of its two subtrees
if (!root)
return 0;

max_path_helper(root, max_sum);

// finally compare the current max sum with the path sum ending at root
if (max_sum < root->val)
max_sum = root->val;

return max_sum;
}
};

Saturday, December 8, 2012

[leetcode] binary tree level 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},

return its level order traversal as:

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

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

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

// initialize the result
vector > result;

if (!root)
return result;

queue my_queue;

my_queue.push(root);
// push a dummy node into the queue
my_queue.push(NULL);

// initialize a tmp array
vector tmp;

while (!my_queue.empty())
{
TreeNode *front = my_queue.front();

if (!front)
{
// process a dummy
if (tmp.size() > 0)
result.push_back(tmp);
tmp.erase(tmp.begin(), tmp.end());
my_queue.pop();
continue;
}
else
{
tmp.push_back(front->val);
my_queue.pop();
}

if (front->left) my_queue.push(front->left);
if (front->right) my_queue.push(front->right);

// check if the next node is dummy
front = my_queue.front();
if (!front)
{
// initialize another dummy into the queue
my_queue.push(NULL);
}
}

return result;
}
};

[leetcode] binary tree inorder traversal

Binary Tree Inorder Traversal

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

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

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Wednesday, November 28, 2012

Mark Cuban 演讲小结

刚刚去听了Mark Cuban的演讲，Mark Cuban是Indiana的校友，美国商界的精英，曾经已59亿美金的天价将自己的一个IT公司卖给了雅虎，现在是小牛队的老板。和Mark近距离接触的感觉和屏幕上看到的很相似，非常地passionate，言谈举止非常地坚定，说话也非常风趣幽默。简单总结一下这次地收获吧：

1. 创业远远不是只有idea就行的，绝对不是你和一帮兄弟喝着啤酒海阔天空地扯扯淡就能做好的。创业需要的是preparation，也就是说你要对你所要做的东西了解地非常透彻，要做到比任何人都要懂你做地东西。这一点李开复演讲地时候也是常强调的。

2. 有个学生提问时说，“failures are necessary for success”，然后问Mark经历过什么样的失败，才成就了今天的成功。Mark很可爱地说他似乎没经历过什么failure，然后哈哈大笑说“Failures only belong to losers”！其实不管是成功还是失败，最重要地是你从这段经历中学到了什么，有什么样的教训，让你有了怎样地成长。另外，所谓“failure”，可能从来都不存在于“成功”的字典里；相信自己会成功的人才会真正成功。

3. 关于人生理想和自身定位。Mark说自己当时创建公司时，自己的目标就是在35岁之前把公司做大，然后在35岁的时候退休，去做自己喜欢做的事情（比如说现在经营NBA小牛队）。永远不要让你后悔自己的人生，人生每个阶段都有需要去做的事情，不要到老的时候去后悔。

4. 中间有个小插曲。Mark在开场的时候说他曾经投资过无数个公司，别人一封email，即使甚至连人都没见过，他也可能会投资给那个人。演讲快到最后的时候，有个美国学生站起来说，我现在在做怎样怎样的business，目前的情况是blablabla，问Mark有没有兴趣给他投资。。。得到的答案当然是BIG NO，呵呵。不过还是祝愿他能成功。

5. 真正成功的人是自己能把生活过的有滋有味的，热爱生活的人才会活的自信开心，才散发魅力会吸引周围的人。所以一个人的事业和生活是分不开的，要build好自己的personality，要热爱生活，要有强烈的passion，要有改变未来的勇气。

我正在努力：）

Saturday, November 17, 2012

预防癌症的１４条膳食准则

　　１９９７年９月，由美国癌症研究所的世界癌症研究基金会联合推出了一本名为“食物、营养与癌症预防”的志著，该书由８个国家的１６位著名营养学、肿瘤学专家花了３年时间集体编写而成的。本专著是对近１５年间世界各地在此领域的文献资料进行的总结晶阐述了膳食模式与癌症的关系以及膳食与癌症的发生、发展过程的关系，分析了不同部位癌症与食物和营养的关系，然后描述不同癌症的危险性与各种膳食成分（食物、营养素）及食物加工的关系，最后根据上述科学依据，提出了一套全球性的预防癌症的１４条膳食准则，其内容如下：
　　食物供应和进食及相关因素
　　１·食物供应和进食：摄取以植物性食物为主的营养充分和多种食物品种的膳食，主要选择植物来源的食物，如蔬菜、水果、豆类和加工度比较低的谷类。
　　２·保持体重：成年人群的体质数范围在２１－２３，因此，个体的体质指数［体重kg／身高2(m2)］应保持在１８.５与２５之间，避免体重过低或超重，在成年期体重的增加应限制在５kg以内。
　　３·坚持体力活动：终身坚持体力活动，如果工作时体力较少，每天应进行１小时，或进行相类似的活动量。每周还应适当安排到少有较剧烈的活动１小时。
　　食物和饮料
　　４·蔬菜和水果：全年都吃各种不同的蔬菜和水果，每天量应在４００－８００g。
　　５·其它植物性食物：每天吃各种富含淀粉或富含蛋白质的加工较低的谷类、豆类、根茎类食物６００－８００g，其总能量应占４５％－６０％，少吃精制糖。
　　６·含酒精饮料：鼓励不饮酒或不过量饮酒，如果饮酒，男性每天限饮两份，女性限饮一份（每份酒的含义为啤酒２００ml、果酒１００ml、或烈性白酒２５ml）。
　　７·肉类：如果吃肉，每日红肉（如猪肉、牛羊肉等）的摄取量应少于８０g，最好选择鱼类禽类或非家禽动物代替肉类。
　　８·总脂肪和油类：限制摄入含脂肪较多的动物性食物，摄入适量的植物油，油脂的能量占总能量的１５％－３０％以下。
　　９·盐和腌制：减少食盐的总摄取量，成人限制在每天６g以下，减少烹调用食盐和摄入腌制食品。
　　１０·贮存：易腐败的食物应妥善贮存以减少霉菌。避免吃贮存期长、受霉菌污染的食物。
　　１１·保藏：易腐败的食物，如不能及时吃掉，应冷冻或冷藏。
　　１２·添加剂及农药残留量：建立和监测对食物中食品添加剂、农药及残留量和其它化学污染物的限量，保证在规定范围内的食物添加剂和农药残留量不致产生有害作用，在发展中国家尤应注意这方面的临监测。
　　１３·烹调：不要吃烧焦的食物。避免将肉和鱼烧焦，尽量少吃火焰上直接熏烤的食物，鼓励用比较低的温度烹调食品。
　　１４·膳食补充剂：采用有利于减少癌症的危险的膳食模式，而不用膳食补充剂。如果能遵循上述膳食建议，很可能没必要用膳食补充剂，而且膳食补充剂对减少癌症危险并无帮助。

Monday, November 12, 2012

[ZZ] 自学算法之路

现在真的在自学算法，努力按照以下阶段复习中，争取做到倒背如流

第一阶段：练经典常用算法，下面的每个算法给我打上十到二十遍，同时自己精简代码，

因为太常用，所以要练到写时不用想，10-15分钟内打完，甚至关掉显示器都可以把程序打

出来.

1.最短路(Floyd、Dijstra,BellmanFord)

2.最小生成树(先写个prim,kruscal要用并查集，不好写)

3.大数（高精度）加减乘除

4.二分查找. (代码可在五行以内)

5.叉乘、判线段相交、然后写个凸包.

6.BFS、DFS,同时熟练hash表(要熟，要灵活,代码要简)

7.数学上的有：辗转相除（两行内），线段交点、多角形面积公式.

8. 调用系统的qsort, 技巧很多，慢慢掌握.

9. 任意进制间的转换

第二阶段：练习复杂一点，但也较常用的算法。

如：

1. 二分图匹配（匈牙利），最小路径覆盖

2. 网络流，最小费用流。

3. 线段树.

4. 并查集。

5. 熟悉动态规划的各个典型：LCS、最长递增子串、三角剖分、记忆化dp

6.博弈类算法。博弈树，二进制法等。

7.最大团，最大独立集。

8.判断点在多边形内。

9. 差分约束系统.

10. 双向广度搜索、A*算法，最小耗散优先.

月光睡在树梢上