goood solutions for tree traversal

TracyJanuary 26, 2011 at 7:20 pm

@1337c0d3r:
I'm quite sure that my code of using one stack for post-order traversal works. You can use the same example above to go through it. I made iterative in-order, pre-order and post-order traversal as similar as possible:

void postorderNoR(const Node *root)
{
stack s;
const Node *itr = root;

while (itr || !s.empty()) {
if (!itr) {
while (!s.empty() &&
itr == s.top()->right) {
itr = s.top();
s.pop();
printf("%d ",itr->value);
}
itr = s.empty() ? NULL : s.top()->right;
}
else
{
s.push(itr);
itr = itr->left;
}
}
}

// *********************

void inorderNoR(const Node *root)
{
stack s;
const Node *itr = root;

while (itr || !s.empty()){
if (!itr){
itr = s.top();
s.pop();
printf("%d ",itr->value);
itr = itr->right;
}
else{
s.push(itr);
itr = itr->left;
}
}
}

// *********************

void preorderNoR(const Node *root)
{
stack s;
const Node *itr = root;

while (itr || !s.empty()){
if (!itr){
itr = s.top();
s.pop();
itr = itr->right;
}
else{
printf("%d ",itr->value);
s.push(itr);
itr = itr->left;
}
}
}

0

Pay Attention!!

Graph

directed graph or undirected graph?
The methods of graph traversal?
http://articles.leetcode.com/2012/05/clone-graph-part-i.html

Number
always consider if the algorithm will over flow!!!!!!
if negative or zero number will impact the final result!!!!!!
http://articles.leetcode.com/2012/01/palindrome-number.html

String
'a' to 'z'? Digits? Upper case letter? Does it contain ASCII characters only? Or even unicode character sets?
http://articles.leetcode.com/2011/05/longest-substring-without-repeating-characters.html

Tree
duplications? 
http://articles.leetcode.com/2011/04/construct-binary-tree-from-inorder-and-preorder-postorder-traversal.html

Longest Palindromic Substring

Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

--------------------- thinking -----------------------------

https://leetcode.com/discuss/32204/simple-c-solution-8ms-13-lines
http://articles.leetcode.com/2011/11/longest-palindromic-substring-part-i.html
http://articles.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
http://www.felix021.com/blog/read.php?2040

word ladder

Word Ladder

 Given two words (beginWord and endWord), and a dictionary, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

--------------- thinking -----------------------
A lot of optimizations are discussed in this post!!!! And why my codes is memory limit exceed!!!
http://www.cnblogs.com/linyx/p/3706688.html

Detect Cycle in a Directed Graph

Detect Cycle in a Directed Graph

Given a directed graph, check whether the graph contains a cycle or not. Your function should return true if the given graph contains at least one cycle, else return false. For example, the following graph contains three cycles 0->2->0, 0->1->2->0 and 3->3, so your function must return true.
Solution
Depth First Traversal can be used to detect cycle in a Graph. DFS for a connected graph produces a tree. There is a cycle in a graph only if there is a back edge present in the graph. A back edge is an edge that is from a node to itself (selfloop) or one of its ancestor in the tree produced by DFS. In the following graph, there are 3 back edges, marked with cross sign. We can observe that these 3 back edges indicate 3 cycles present in the graph.

For a disconnected graph, we get the DFS forrest as output. To detect cycle, we can check for cycle in individual trees by checking back edges.

----------------------- thinking ----------------------------------

rotate array

-------------------- thinking ----------------------
https://leetcode.com/discuss/30527/three-way-solve-this-problem-the-first-way-interesting-java

Uber

1， 在Uber做工程师体验如何？
Glassdoor上我们写的review非常详细，个人来说非常满意，技术规范前沿，代码多开
会少官僚无，impact大
http://www.glassdoor.com/GD/Reviews/Uber-San-Francisco-Reviews-

2，Bar有多高？
面试难度不同组差别可能较大，现在难进主要还是因为来面的太多。
喜欢招资深的，技术背景匹配的，要求马上能上手

3，待遇如何？
http://h1bdata.info/index.php?em=uber&job=
看2014年6月后数据

股票价值可观，大部分人拿到offer时的价值在四年10万(new grad)到80万(senior)间
现在已经是发RSU而不是option.另外进行过1:10和1:4两次拆股，当前股价32.5刀，所
以和以前offer对比
要注意

4，工作压力？
较大，但并不疯狂。大部分人，大部分时候都能在5天8小时内做完，偶尔加班
压力主要体现在所有project都有deadline
工程师相对于要做的事来说还是较少，我们组是1.5人负责一个service

5，发展前景如何？
简单说，很好。现在400亿估值，近3年还有2-5倍成长空间
团队执行力非常强

想理解业务模式，可以读读这两篇文章,简单说就是低价和更好的服务创造了更大的市
场，并且形成network effects不断强化竞争优势
https://hbr.org/2014/12/making-sense-of-ubers-40-billion-valuation
http://abovethecrowd.com/2014/07/11/how-to-miss-by-a-mile-an-al

至于我为什么选择uber，这篇文章有我的分析方法
http://www.mitbbs.com/article_t0/JobHunting/32722713.html

6， 从国内直接招吗？H1b政策？
凡是需要直接办H1B的现在都不招
美国毕业的学生办H1b，不过一般先从OPT开始
问过HR,主要因为需要h1b的话最早要2015年十月才能入职，拿到Offer时和入职时间差
太远，估值可能变化太多；
另外Uber的速度非常快，所以要尽快入职

7，绿卡政策？
没有明文的绿卡政策，无论是第一次申请还是transfer
据我知道拿到offer的时候多半承诺6个月办绿卡。
实际有多快取决于老板，我入职一个月就开始办，进展顺利

8, 福利如何？管三餐吗？
管午餐和晚餐；吃的是catering的，没有自己厨房；晚餐坑爹的是8:15开饭；早餐虽
然没有正式的，不过牛奶,面包,黄油，奶酪,麦片都有

没有401K Match

每月400刀Uber Credits,不过要交税的，用完了还有17%的折扣。用不完作废，不能累
积到下月

各种保险齐全

9，休假政策？
官方假期9天，此外的假期只要manager批准，不限时间

比较好玩的是有个Workation, 自愿参与；在圣诞后自己想点子组队，边度假边
hackthon, 公司补贴1000刀每人

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

// To execute C++, please define "int main()"
string encode(string input) {
  string result;
  if (input.size() == 0) {
    return result;
  }
  unsigned int start = 0;
  unsigned int next = 0;
  int count = 0;
  while (next < input.size()) {
    if (input[next] == input[start]) {
      count++;
    } else {
      result += string(1, input[start]);
      if (count > 1) {
        result += string(1, 'z' + count);
        count = 1;
      }
      start = next;
    }
    next++;
  }
  result += string(1, input[start]);
  if (start + 1 != next) {
    result += string(1, 'z' + count);
  }
  return result;
}
int main() {
  for (int i = 0; i < 5; i++) {
    cout << "Hello, World\n";
  }
  string input("adcaadbdde");
  string result = encode(input);
  cout << result << endl;
  return 0;
}


// 9000886209
// 00000000 11 000 11 0 111 00 1
// 8 zeros, 2 ones, 3 zeros, ..

// 0812031200130210
// 01010101010101
// 0//1010101010101


// aaaaabbbbccc11113335
// 5 a, 4 b, 3 c, 4 1, ...

// abc123 -> abc123
// aabbcc112233 -> a2b2c212232 
// -> abc123222222

// abaabdddc
// abc123

// a(z+2)b(z+2)c(z+2)

转载！ 熬过那三厘米！

学会厚积薄发：多少人，没熬过那三厘米！

 (2014-08-10 21:24:21)

转载▼

标签：  杂谈

学会厚积薄发：多少人，没熬过那三厘米！

竹子用了4年的时间，

仅仅长了3cm，

在第五年开始，

以每天30cm的速度疯狂的生长，

仅仅用了六周的时间就长到了15米。

其实，在前面的四年，

竹子将根在土壤里延伸了数百平米。

做人做事亦是如此，

不要担心你此时此刻的付出得不到回报，

因为这些付出都是为了扎根。

人生需要储备！多少人，没熬过那三厘米！

 国平点评：什么叫厚积薄发，这就是，我们在资本市场，很多时候也是如此，平时的储备和提升，就为了未来行情展开时的茁壮成长。朋友们，已经悄然来临了……

k Sum

k Sum

Given n distinct positive integers, integer k (k <= n) and a number target.

Find k numbers where sum is target. Calculate how many solutions there are?

Example

Given [1,2,3,4], k=2, target=5. There are 2 solutions:

[1,4] and [2,3], return 2.

------------------------ thinking -----------------------
there are two situation for each integer, either count it or not in the dp
http://tech-wonderland.net/blog/summary-of-ksum-problems.html
https://richdalgo.wordpress.com/2015/01/31/lintcode-k-sum/
----------------------- codes ----------------------------
class Solution {
public:
    /**
     * @param A: an integer array.
     * @param k: a positive integer (k <= length(A))
     * @param target: a integer
     * @return an integer
     */
    int kSum(vector<int> A, int k, int target) {
        // wirte your code here
        int dp[A.size()][k+1][target+1];
        for (int i = 0; i < A.size(); i++) {
            for (int j = 0; j <= k; j++) {
                for (int val = 0; val <= target; val++) {
                    dp[i][j][val] = 0;
                }
            }
        }
        for (int i = 0; i < A.size(); i++) {
            for (int j = 1; j <= k; j++) {
                for (int val = 1; val <= target; val++) {
                    if (j == 1 && A[i] == val) {
                        dp[i][1][val] = 1;
                    } else if (i > 0) {
                        if (A[i] <= val) {
                            dp[i][j][val] += dp[i-1][j-1][val-A[i]];
                        }
                        dp[i][j][val] += dp[i-1][j][val];
                    }
                }
            }
        }
        return dp[A.size() - 1][k][target];
    }
};

Word Ladder II

Word Ladder II

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start toend, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

Note

• All words have the same length.
• All words contain only lowercase alphabetic characters.

Example

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

--------------------------- thinking ----------------------------
Since we need to print all pathes, we cannot simply check if a node is visited or not to return
Instead, we need to check if a node is on the same depth of the shorted path.
--------------------------- codes -------------------------------
class Solution {
public:
    /**
      * @param start, a string
      * @param end, a string
      * @param dict, a set of string
      * @return a list of lists of string
      */
    vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
        // write your code here
        unordered_map<string, int> visited;
        unordered_map<string, vector<string>> parent;
        queue<string> que;
        que.push(start);
        visited[start] = 1;
        //BSF
        int min_depth = INT_MAX;
        while (!que.empty()) {
            string cur = que.front();
            que.pop();
            if (visited[cur] == min_depth) {
                break;
            } else {
                for (int i = 0; i < cur.size(); i++) {
                    for (char chr = 'a'; chr <= 'z'; chr++) {
                        if (chr != cur[i]) {
                            string str(cur);
                            str[i] = chr;
                            if (dict.find(str) == dict.end()) {
                                continue;
                            }
                            if (str.compare(end) == 0) {
                                min_depth = visited[cur] + 1;
                            }
                            if (visited.find(str) == visited.end() || visited[str] == visited[cur]+1) {
                                if (visited.find(str) == visited.end()) {
                                 //dont' push node several times, which will cause duplications          
                                    que.push(str);
                                    visited[str] = visited[cur]+1;
                                }
                                if (parent.find(str) == parent.end()) {
                                    vector<string> par(1, cur);
                                    parent[str] = par;
                                } else {
                                    parent[str].push_back(cur);
                                }
                            }
                        }
                    }
                }
            }
        }
        return buildResult(parent, start, end);
    }
    vector<vector<string>> buildResult(unordered_map<string, vector<string>> &parent, string &start, string &end) {
        vector<vector<string>> result;
        if (end.compare(start) == 0) {
            result.push_back(vector<string>(1, end));
            return result;
        }
        for (int i = 0; i < parent[end].size(); i++) {
            vector<vector<string>> tmp_result = buildResult(parent, start, parent[end][i]);
            for (int j = 0; j < tmp_result.size(); j++) {
                vector<string> ele = tmp_result[j];
                ele.push_back(end);
                result.push_back(ele);
            }
        }
        return result;
    }
};

Print a Binary Tree in Vertical Order

Print a Binary Tree in Vertical Order | Set 1

Given a binary tree, print it vertically. The following example illustrates vertical order traversal.

           1
        /    \
       2      3
      / \    / \
     4   5  6   7
             \   \
              8   9 
               
     
The output of print this tree vertically will be:
4
2
1 5 6
3 8
7
9 

-------------------------- thinking --------------------------
http://www.geeksforgeeks.org/print-binary-tree-vertical-order/
------------------------ codes --------------------------

struct my_pair{

    TreeNode *node;

    int       hd;

    my_pair(TreeNode *n, int d): node(n), hd(d){}

};

class Solution {

public:

    vector<vector<int>> printVirtical(TreeNode *root){

        // write your code here

        int start = 0;

        int end = 0;

        findMinMax(root, 0, start, end);

        vector<vector<int>> result(end-start+1, vector<int>());

        queue<my_pair> que;

        if (root == NULL) return result;

        my_pair pair(root, 0);

        que.push(pair);

        while (!que.empty()) {

            my_pair cur = que.front();

            que.pop();

            result[cur.hd - start].push_back(cur.node->val);

            if (cur.node->left) {

                my_pair pair(cur.node->left, cur.hd-1);

                que.push(pair);

            }

            if (cur.node->right) {

                my_pair pair(cur.node->right, cur.hd+1);

                que.push(pair);

            }

        }

        return result;

    }

    void findMinMax(TreeNode *root, int hd, int &start, int &end) {

        if (root->left) {

            if (start > hd - 1) {

                start = hd - 1;

            }

            findMinMax(root->left, hd - 1, start, end);

        }

        if (root->right) {

            if (end < hd + 1) {

                end = hd + 1;

            }

            findMinMax(root->right, hd + 1, start, end);

        }

    }

};

Binary Representation

Binary Representation

Given a (decimal - e g  3.72) number that is passed in as a string,return the binary representation that is passed in as a string.If the number can not be represented accurately in binary, print “ERROR”

Example

n = 3.72, return ERROR

n = 3.5, return 11.1

----------------- thinking --------------------------------
http://www.cnblogs.com/EdwardLiu/p/4273813.html
------------------ codes ---------------------------------
class Solution {
public:
    /**
     *@param n: Given a decimal number that is passed in as a string
     *@return: A string
     */
    string binaryRepresentation(string n) {
        // wirte your code here
        //split integer and decimal
        size_t npoint = n.find('.');
        int integer = 0;
        double decimal = 0.0;
        if (npoint != string::npos) {
            decimal = strtod(n.substr(npoint, n.size()).c_str(), NULL);
            integer = atoi(n.substr(0, npoint).c_str());
        } else {
            integer = atoi(n.c_str());
        }
        // convert integer part
        string intbuf;
        if (integer > 0) {
            while (integer > 0) {
                intbuf.append(integer%2==1?"1":"0");
                integer /= 2;
            }
            reverse(intbuf.begin(), intbuf.end());
        } else {
            intbuf.append("0");
        }
        // convert decimal part
        string decbuf;
        if (decimal > 0.0) {
            while (decimal > 0.0) {
                if (decbuf.size() > 32) {
                    return "ERROR";
                }
                decimal *= 2;
                if (decimal >= 1.0) {
                    decbuf.append("1");
                    decimal -= 1.0;
                } else {
                    decbuf.append("0");
                }
            }
        }
        //combine and return
        return decbuf.size() > 0 ? intbuf + "." + decbuf : intbuf;
    }
};

转载：如何在面试中写出好的代码

一下都是我面试的经验和教训，欢迎各位大牛指正或者补充

1. 写代码之前，大脑里面要有个whole picture，不能想到哪儿写到哪儿。是你的大脑
在写代码，而不是白板上你的手在代码。你的手只是一个printer里面的喷头而已，是
它把你大脑里面的代码print到白板上，你的大脑才是控制那个喷头的芯片。所以，写
之前，你要看着那个白板打个腹稿，想想一下白板上可能有哪些代码，比如定义哪些变
量，哪些if else，哪里退出，call哪几个function，等等。(write some pseudo code)

2. 要端正观念，写代码只是最后一步，是在对方完全理解了你的意图之后的最终表
述，所以，在写代码之前，一定要跟对方把你的意图表述清楚，一定不要在对方不懂你
的想法的情况下就开始写代码，大忌，大忌！(ask: Do you think this is OK?)

3. 你在白板或者纸上写代码的过程中，一定要跟面试官交流，让他知道自己在干什
么。每次提笔之前，告诉他，我前面写了啥，然后我准备写啥，这个写的过程，是前面
跟面试官讨论问题结束之后的具体反映。

4. 切记，切记，写完了一定不要很快跟面试官说，我写完了，然后就转过身去了
。你写的code一定一定一定一定有问题的，一定一定一定一定要写几个test case自己
跑一边，一定一定不要怕改自己的代码，这个时候当着面试官改自己的代码，一定加分
，不会减分的。我们小时候考试的时候都知道做完题目了要检查，这里写code也是一样
的啊，更何况小时候只要答案，这个code还要看过程呢！

(let me double check if I have overlooked sth, consider all the cases... maybe I'll write a test case)

(This part I did what what what...顺便自我检查)



5. input一定要check，哪怕面试官说不需要check，你写代码的时候也要check，这
是告诉他你知道这个point



6. 不要指望一次性把代码写完，要学会使用手中的erase，边写边改，比如我前
面提到的一些代码的优化问题，写着写着，你就会知道哪儿重复代码可以归并，哪儿可
以写一个function来代替了，碰到这样的情况，一定要改，让面试官知道，我懂这个。



7. 如果中途面试官打断你，你要大胆的交流，要么告诉他他指出的bug我知道，
要么及时改正那个bug，所以，前面第一第二条非常重要，因为只有你自己知道自己在
干什么后，就不怕面试官打断，哪怕有bug，也是一个改正的问题。



8. test case 跑完了，修改一些问题，转过身来，跟面试官说，你看，我最开始
准备干啥，我现在干了啥，这个是干啥，那个是干啥，也就是把前面我说的第一条第二
条给面试官解释一遍，告诉他，我的代码真实准确高效的反映了我最开始跟你解释的算
法问题。

9，如果有重复的代码，一定要用一个变量或者一个function表示。本来面试的代码
就不长，还有重复的代码会很ugly。比如类似current->next要使用很多次的话，可以
定义一个新的local的指针；再比如在for或者while循环里面，要check什么值de时候，
千万不要用计算公式，因为会反复计算；你要delete一个node的时候，可能很多ifelse
里面都有delete p，应该拿到最后一行去delete。

10. 某个单独的过程，能够用function表示就用function表示，比如在一个for循环
里面做一件什么事情，如果这个过程很长，比如大于5行，你最好就写一个单独的
function，然后这个function里面去具体定义这5行。这样有几个好处，思路清晰，方
便修改，你在这里写一个function表示前面这个主function就算写完了，这也可以保证
你写的function都很短。

11. for while循环里面的early return，如果for while循环里面有条件不满足，可
以直接return，不要等到循环结束了，再来check那个值后判断return啥


12. 一般面试官会写一个signature，但是那个signature不是你想要的怎么办？比如
他给你一个input只有一个string，但是你平时练习的function需要长度，比如要你
check是否bst，只给了一个一个root，这些你都要大胆的定义一个helper function，
然后在他给de那个function里面call你自己定义的。不光是如此，helper function可
以很直观的把题目de意义表示出来。

13. 一定要注意哪些变量是index，那些是size，一般lai讲index操作起来更加简单
，不用考虑加减1的问题，但是size转换成index，都或多或少会涉及到加减1的问题。

14. 要大胆的使用递归，面试的问题不可能很难，也不可能很长，当你stuck的时
候，就思考递归。递归最大的好处就是简单直接方便理解，比如基本所有tree的问题，
都是递归，还有不少数组问题，search问题等等。使用递归de时候，要大胆的使用前面
第九条说的helper function，很多时候多传一个参数会让问题很简单。

15. 写完了之后，如果可能，你自己拍个照片纪录一下方便以后学习。


一口气总共写了16条，各位大牛见笑了，欢迎大家交流，指正和补充！

Subarray Sum Closest

Subarray Sum Closest

Given an integer array, find a subarray with sum closest to zero. Return the indexes of the first number and last number.

Example

Given [-3, 1, 1, -3, 5], return [0, 2], [1, 3], [1, 1], [2, 2] or [0, 4]

Challenge

O(nlogn) time

------------------ thinking ------------------------
http://www.cnblogs.com/lishiblog/p/4187961.html
[INT_MAX]
----------------- codes ---------------------------

struct my_pair {
    int sum;
    int index;
    my_pair(int s, int i): sum(s), index(i) {}
};
bool myfunction(my_pair i, my_pair j) {return i.sum < j.sum;}
class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return: A list of integers includes the index of the first number
     *          and the index of the last number
     */
    vector<int> subarraySumClosest(vector<int> nums){
        // write your code here
        vector<my_pair> arr;
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            my_pair pair(sum, i);
            arr.push_back(pair);
        }
        my_pair pair(0, -1);
        arr.push_back(pair);
        sort(arr.begin(), arr.end(), myfunction);
        unsigned int diff = INT_MAX;
        vector<int> result(2, 0);
        for (int i = 0; i < arr.size() - 1; i++) {
            if (diff >= abs(arr[i].sum - arr[i+1].sum)) {
                diff = abs(arr[i].sum - arr[i+1].sum);
                result[0] = arr[i].index;
                result[1] = arr[i+1].index;
            }
        }
        sort(result.begin(), result.end());
        result[0] += 1;
        return result;
    }
};

Word Segmentation

Word Segmentation

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Example

Given

s = "lintcode",

dict = ["lint", "code"].

Return true because "lintcode" can be segmented as "lint code".

------------------------- thinking ---------------------------------
"", [] -> both empty, return true;
"", ["a"]->string empty, return true;
"a", []-> dict empty, return false;

optimization codes:
when dict doesn't contain all string's character, return false directly
------------------------- codes --------------------------------
class Solution {
public:
    /**
     * @param s: A string s
     * @param dict: A dictionary of words dict
     */
    bool wordSegmentation(string s, unordered_set<string> &dict) {
        // write your code here
        if (s.size() < 1 && dict.size() == 0) return true;
        if (s.size() < 1) return false;
        int chrs[256] = {0};
        for (unordered_set<string>::iterator it = dict.begin(); it != dict.end(); ++it) {
            string cur = *it;
            for (int i = 0; i < cur.size(); i++) {
                chrs[cur[i]]++;
            }
        }
        for (int i = 0; i < s.size(); i++) {
            if (chrs[s[i]] == 0) {
                return false;
            }
        }
        vector<bool> dp(s.size()+1, false);
        dp[0] = true;
        for (int i = 0; i < s.size(); i++) {
            for (int j = i-1; j >= -1; j--) {
                if (dp[j+1] && dict.find(s.substr(j+1, i - j)) != dict.end()) {
                    dp[i+1] = true;
                    break;
                }
            }
        }
        return dp[s.size()];
    }
};

First Missing Positive

First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

Example

Given [1,2,0] return 3, and [3,4,-1,1] return 2.

Challenge

Your algorithm should run in O(n) time and uses constant space.

----------------- thinking -----------------
e.g. [1,1] --> duplications
e.g. [-1, 4, 2, 1, 9, 10] ->larger than A's size() numbers
------------------ codes -------------------
class Solution {
public:
    /**  
     * @param A: a vector of integers
     * @return: an integer
     */
    int firstMissingPositive(vector<int> A) {
        // write your code here
        if (A.size() == 0) return 1;
        // re-arrage A by index
        for (int i = 0; i < A.size(); i++) {
            while (A[i] != i + 1 && A[i] > 0 && A[i] <= A.size() && A[A[i] - 1] != A[i]) {
                int tmp = A[i];
                A[i] = A[A[i] - 1];
                A[tmp-1] = tmp;
            }
        }
        int i = 0;
        while (A[i] == i + 1) {
            i++;
        }
        return i+1;
    }
};

Delete Digits

Delete Digits

Given string A representative a positive integer which has N digits, remove any k digits of the number, the remaining digits are arranged according to the original order to become a new positive integer. Make this new positive integers as small as possible.

N <= 240 and k <=N, 

Example

Given an integer A = 178542, k = 4

return a string "12"

------------------------------ thinking -----------------------------------
This is quite like calculating the biggest area of histogram, we need to keep a increasing array by using stack
------------------------------ codes -------------------------------------
class Solution {
public:
    /**
     *@param A: A positive integer which has N digits, A is a string.
     *@param k: Remove k digits.
     *@return: A string
     */
    string DeleteDigits(string A, int k) {
        // wirte your code here
        stack<int> stk;
        stk.push(0);
        int i = 1;
        while (k > 0) {
            if (i < A.size()) {
                if (stk.empty() || A[i] >= A[stk.top()]) {
                    stk.push(i);
                    i++;
                } else {
                    stk.pop();
                    k--;
                }
            } else {
                stk.pop();
                k--;
            }
        }
        string result = A.substr(i, A.size() - i);
        while (!stk.empty()) {
            result = A.substr(stk.top(), 1) + result;
            stk.pop();
        }
        while (result.size() > 1 && result[0] == '0') {
            result.erase(0, 1);
        }
        return result;
    }
};

Fast Power

Fast Power

Calculate the an % b where a, b and n are all 32bit integers.

Example

For 231 % 3 = 2

For 1001000 % 1000 = 0

Challenge

O(logn)

------------------- thinking -----------------------------------------
result * base & base * base might overflow, so please use long long as the type of these two variables
-------------------- codes -------------------------------------------
class Solution {
public:
    /*
     * @param a, b, n: 32bit integers
     * @return: An integer
     */
    int fastPower(int a, int b, int n) {
        // write your code here
        if (n == 0) {
            return 1 % b;
        }
        if (n == 1) {
            return a % b;
        }
        long long base = a % b;
        long long result = 1;
        int bit_n = n;
        while (bit_n > 0) {
            if (bit_n % 2) {
                result = (result * base) % b;
            }
            bit_n = bit_n/2;
            base = (base * base) % b;
        }
        return result;
    }
};