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

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

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

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

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

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

[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},

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

   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.

/**
 * 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 inorderTraversal(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        stack my_stack;
        TreeNode *p = root;
        vector result;
       
        if (!p)
            return result;
           
        while (p)
        {
            my_stack.push(p);
            p = p->left;
        }
       
        while (!my_stack.empty())
        {  
            TreeNode *top = my_stack.top();
            my_stack.pop();
            result.push_back(top->val);

            p = top->right;
           
            while (p)
            {
                my_stack.push(p);
                p = p->left;
            }
        }
       
        return result;
    }
};

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，要有改变未来的勇气。

我正在努力：） 

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

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