Thursday, July 30, 2015

LintCode (116) Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
Have you met this question in a real interview? 
Yes
Example
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    /**
     * @param A: A list of integers
     * @return: The boolean answer
     */
    bool canJump(vector<int> A) {
        // write you code here
        if (A.empty() || A[0]==0)
            return false;
        int n=A.size();
        vector<bool> tbl(n, false);
        tbl[0]=true;
        for (int i=1; i<n; i++){
            for (int j=i-1; j>=0; j--){
                if(tbl[j] && j+A[j]>=i ){
                    tbl[i]=true;
                    break;
                }
            }
        }
        return tbl[n-1];
    }
};
Posted by at No comments:
Labels:

Wednesday, July 29, 2015

LintCode (111) Climbing Stairs Show result

You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Have you met this question in a real interview? 
Yes

Example
Given an example n=3 , 1+1+1=2+1=1+2=3
return 3

斐波切那函数的变种题目。。。。难为出题的人了。。。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    /**
     * @param n: An integer
     * @return: An integer
     */
    int climbStairs(int n) {
        // write your code here
        if (n==1)
            return 1;
        int prev=1;
        int cur=2;
        for(int i=3; i<=n; i++){
            int prepre=prev;
            prev=cur;
            cur=prepre+prev;
        }
        return cur;
    }
};
Posted by at No comments:
Labels:

LintCode (115) Unique Paths II

Follow up for "Unique Paths":
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
Have you met this question in a real interview? 
Yes
Example
For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
The total number of unique paths is 2.

Note
m and n will be at most 100.

这题没啥好讲的，handle好初始条件，其他和以前的一样



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    /**
     * @param obstacleGrid: A list of lists of integers
     * @return: An integer
     */ 
    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
        // write your code here
        if (obstacleGrid[0][0])
            return 0;
        int m=obstacleGrid.size();
        int n=obstacleGrid[0].size();
        vector<vector<int>> tbl(m, vector<int>(n, 0));
        tbl[0][0]=1;
        for (int i=1; i<m; i++){
            if (obstacleGrid[i][0] ==1){
                tbl[i][0]=0;
            } else{
                tbl[i][0]=tbl[i-1][0];
            }
        }
        for (int j=1; j<n; j++){
            if (obstacleGrid[0][j] ==1){
                tbl[0][j]=0;
            } else{
                tbl[0][j]=tbl[0][j-1];
            }
        }
        for (int i=1; i<m; i++){
            for (int j=1; j<n; j++){
                if (obstacleGrid[i][j])
                    continue;
                tbl[i][j]=tbl[i-1][j]+tbl[i][j-1];
            }
        }
        return tbl[m-1][n-1];
    }
};
Posted by at No comments:
Labels:

LintCode (114) Unique paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
Have you met this question in a real interview? 
Yes
Example
1,11,21,31,41,51,61,7
2,1





3,1




3,7

Above is a 3 x 7 grid. How many possible unique paths are there?

Note
m and n will be at most 100.

Dp:
求解得数目，走table, matrix dp
f[i][j] 为 从0,0走到i,j的路径数
转化方程 f[i][j]= f[i-1][j]+f[i][j-1]
解： f[m-1][n-1]


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    /**
     * @param n, m: positive integer (1 <= n ,m <= 100)
     * @return an integer
     */
    int uniquePaths(int m, int n) {
        // wirte your code here
        vector<vector<int>> tbl(m, vector<int>(n,1));
        for(int i=1; i<m; i++){
            for (int j=1; j<n; j++){
                tbl[i][j]=tbl[i-1][j]+tbl[i][j-1];
            }
        }
        return tbl[m-1][n-1];
    }
};
Posted by at No comments:
Labels:

LintCode (110) Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Have you met this question in a real interview? 
Yes
Example

Note
You can only move either down or right at any point in time.

求最小， 矩阵，-》 matrix dp。 
列方程：
f[i][j] = 从0,0 到 i,j的最小和。
转移方程 f[i][j] = min(f[i-1][j], f[i][j-1]) +grid[i][j]
初始条件， f[0][*], f[*][0]
解， f[m-1][n-1]


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    /**
     * @param grid: a list of lists of integers.
     * @return: An integer, minimizes the sum of all numbers along its path
     */
    int minPathSum(vector<vector<int> > &grid) {
        // write your code here
        int m = grid.size();
        int n = grid[0].size();
        // state f[i][j] is the minmum sum from [0][0] goes to here
        vector<vector<int> > tbl(m, vector<int>(n, 0));
        tbl[0][0]=grid[0][0];
        for (int i=1; i<m; i++){
            tbl[i][0]=tbl[i-1][0]+grid[i][0];
        }
        for (int i=1; i<n; i++){
            tbl[0][i]= tbl[0][i-1]+grid[0][i];
        }
        for (int i=1; i<m; i++){
            for (int j=1; j<n; j++){
                tbl[i][j]=min(tbl[i][j-1],tbl[i-1][j])+grid[i][j];
            }
        }
        return tbl[m-1][n-1];
    }
};
Posted by at No comments:
Labels:

LintCode (109) Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
Have you met this question in a real interview? 
Yes
Example
For example, given the following triangle
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

这个题是道老题了，可以选自顶向下，也可反过来，其实自顶向下更容易理解
DP 三板斧：
1. 求最小
2. 从某一各位移动到某一个位置 -》matrix dp
3. 列方程：
状态： f[i][j]为从[0][0] 到[i][j]的最小值
转化方程 f[i][j]= min(f[i-1][j-1], f[i-1][j])+a[i][j]. 注意corner case, 0和i=j的位置
初始化： f[0][0]=a[0][0]
结果： min(f[n-1][*])



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    /**
     * @param triangle: a list of lists of integers.
     * @return: An integer, minimum path sum.
     */
    int minimumTotal(vector<vector<int> > &triangle) {
        // write your code here
        int n=triangle.size();
        vector< vector<int> > table(n, vector<int> (n, 0));
        // initialize
        table[0][0]=triangle[0][0];
        // transfer function
        for (int i=1; i<n; i++){
            for (int j=0; j<=i; j++){
                if (j>0 && j!=i){
                    table[i][j]=min(table[i-1][j-1], table[i-1][j])+triangle[i][j];
                } else if (j==0){
                    table[i][j]=table[i-1][j]+triangle[i][j];
                } else{
                    table[i][j]=table[i-1][j-1]+triangle[i][j];
                }
            }
        }
        int result = INT_MAX;
        // final
        for (int i=0; i<n; i++){
            result=min(result, table[n-1][i]);
        }
        return result;
    }
    
};

这样的话是o(n^2)的空间和时间复杂度，把数组滚动一下，可以到o(n)



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    /**
     * @param triangle: a list of lists of integers.
     * @return: An integer, minimum path sum.
     */
    int minimumTotal(vector<vector<int> > &triangle) {
        // write your code here
        int n=triangle.size();
        vector< vector<int> > table(2, vector<int> (n, 0));
        // initialize
        table[0][0]=triangle[0][0];
        // transfer function
        for (int i=1; i<n; i++){
            for (int j=0; j<=i; j++){
                if (j>0 && j!=i){
                    table[i%2][j]=min(table[(i-1)%2][j-1], table[(i-1)%2][j])+triangle[i][j];
                } else if (j==0){
                    table[i%2][j]=table[(i-1)%2][j]+triangle[i][j];
                } else{
                    table[i%2][j]=table[(i-1)%2][j-1]+triangle[i][j];
                }
            }
        }
        int result = INT_MAX;
        // final
        for (int i=0; i<n; i++){
            result=min(result, table[(n-1)%2][i]);
        }
        return result;
    }
    
};
Posted by at No comments:
Labels:

Sunday, July 26, 2015

LintCode (87) Remove Node in Binary Search Tree

Given a root of Binary Search Tree with unique value for each node.  Remove the node with given value. If there is no such a node with given value in the binary search tree, do nothing. You should keep the tree still a binary search tree after removal.
Have you met this question in a real interview? 
Yes

Example
Given binary search tree:
          5
       /    \
    3          6
 /    \
2       4
Remove 3, you can either return:
          5
       /    \
    2          6
      \
         4
or :
          5
       /    \
    4          6
 /   
2

基础题，和那个插入node一个思路， 如果小于当前， 插入（删除）左面， 如果大于当前， 插入（删除）右面。如果（NULL)相等，插入删除当前。
在处理当前项的时候有这三种情况：
1. 无左孩子，那么返回右孩子并删除当前
2. 无右孩子，返回左孩子并删除当前
3. 都有， 交换当前与右孩子的最小值 （leaf），并从右子数中删除当前值


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param root: The root of the binary search tree.
     * @param value: Remove the node with given value.
     * @return: The root of the binary search tree after removal.
     */
    TreeNode* removeNode(TreeNode* root, int value) {
        // write your code here
        if (!root)
            return 0;
        if (value<root->val)
            root->left=removeNode(root->left, value);
        else if (value>root->val)
            root->right=removeNode(root->right, value);
        else{
            if (!root->right){
                TreeNode* tmp=root->left;
                delete root;
                return tmp;
            }
            if (!root->left){
                TreeNode* tmp=root->right;
                delete root;
                return tmp;
            }
            TreeNode* tmp=root->right;
            while(tmp->left)
                tmp=tmp->left;
            swap(root->val, tmp->val);
            root->right=removeNode(root->right, tmp->val);
        }
        return root;
    }
};
Posted by at No comments:
Labels: ,

LintCode (7) Binary Tree Serialization

Design an algorithm and write code to serialize and deserialize a binary tree. Writing the tree to a file is called 'serialization' and reading back from the file to reconstruct the exact same binary tree is 'deserialization'.
There is no limit of how you deserialize or serialize a binary tree, you only need to make sure you can serialize a binary tree to a string and deserialize this string to the original structure.
Have you met this question in a real interview? 
Yes

Example
An example of testdata: Binary tree {3,9,20,#,#,15,7}, denote the following structure:
  3
 / \
9  20
  /  \
 15   7
Our data serialization use bfs traversal. This is just for when you got wrong answer and want to debug the input.
You can use other method to do serializaiton and deserialization.


binary tree有三种traversal: inorder ,preorder and postorder.只有preorder和postorder才能保存结构的信息。所以考虑pre order和post order. 但是还是有区别， postorder走的是自底向上的路线，而preorder走的是自顶向下的路线。 逻辑好理解程度， 或者说在deserialize的时候preorder比较容易些。 所以这道题算是写两遍preorder，考察地方也就是to_string和stringstream了。。。lol


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * This method will be invoked first, you should design your own algorithm 
     * to serialize a binary tree which denote by a root node to a string which
     * can be easily deserialized by your own "deserialize" method later.
     */
    string serialize(TreeNode *root) {
        // write your code here
        string result;
        serializeHelper(root, result);
        return result;
    }

    void serializeHelper(TreeNode *root, string& result){
        if (!root){
            result += "# ";
            return;
        }
        result= result+to_string(root->val)+" ";
        serializeHelper(root->left, result);
        serializeHelper(root->right, result);
    }
    /**
     * This method will be invoked second, the argument data is what exactly
     * you serialized at method "serialize", that means the data is not given by
     * system, it's given by your own serialize method. So the format of data is
     * designed by yourself, and deserialize it here as you serialize it in 
     * "serialize" method.
     */
    TreeNode *deserialize(string data) {
        // write your code here
        stringstream ss(data);
        return deserializeHelper(ss);
    }
    
    TreeNode* deserializeHelper(stringstream& ss){
        string val;
        ss>>val;
        if (val=="#")
            return 0;
        int value=atoi(val.c_str());
        TreeNode* root= new TreeNode(value);
        root->left=deserializeHelper(ss);
        root->right=deserializeHelper(ss);
        return root;
    }
};
Posted by at No comments:
Labels: ,

LintCode (72) Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.
Have you met this question in a real interview? 
Yes
Example
Given inorder [1,2,3] and postorder [1,3,2], return a tree:
  2
 / \
1   3

Note
You may assume that duplicates do not exist in the tree.


和上题inorder 和 preorder一起的解法一样， 其实这种题目的关键在于找到谁是root,


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
 

class Solution {
    /**
     *@param inorder : A list of integers that inorder traversal of a tree
     *@param postorder : A list of integers that postorder traversal of a tree
     *@return : Root of a tree
     */
public:
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        // write your code here
        return helper(inorder, postorder ,0, inorder.size()-1, 0, inorder.size()-1);
    }
    TreeNode* helper(vector<int>& in, vector<int>& post, int ibeg, int iend,
                     int pbeg, int pend)
    {
        if (pbeg>pend)
            return 0;
        int val=post[pend];
        int i;
        for (i = ibeg; i <= iend; i++ ){
            if (in[i]==val)
                break;
        }
        TreeNode* root = new TreeNode(val);
        root->left = helper(in, post, ibeg, i-1, pbeg, pbeg+i-1-ibeg);
        root->right = helper(in, post, i+1, iend, pend-iend+i,pend-1);
        return root;
    }
};
Posted by at No comments:
Labels: ,

LintCode (73) Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.
Have you met this question in a real interview? 
Yes
Example
Given in-order [1,2,3] and pre-order [2,1,3], return a tree:
  2
 / \
1   3

Note
You may assume that duplicates do not exist in the tree.


画一下preorder和postorder就可以了

preorder:
|root|  .... left subtree ....| ... right subtree...|
inorder:
|...left subtree ...| root | .... right subtree ...|

所以我们可以用preorder的第一个元素来创建root, 而用 preorder, inorder的左子数创建左孩子，， 右子树创建右孩子， 这个过程是个recursive call


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
 

class Solution {
    /**
     *@param preorder : A list of integers that preorder traversal of a tree
     *@param inorder : A list of integers that inorder traversal of a tree
     *@return : Root of a tree
     */
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        // write your code here
        return buildHelper(preorder, inorder, 0, preorder.size()-1, 0, inorder.size()-1);
    }
    
    TreeNode *buildHelper(vector<int>& preorder, vector<int>& inorder,
                         int pbeg, int pend, int ibeg, int iend)
    {
        if (pbeg>pend)
            return 0;
        int val=preorder[pbeg];
        int i;
        for ( i=ibeg; i<=iend; i++){
            if (inorder[i]==val)
                break;
        }
        TreeNode* root=new TreeNode(val);
        root->left= buildHelper(preorder, inorder, pbeg+1, pbeg+i-ibeg,ibeg, i-1);
        root->right=buildHelper(preorder, inorder, pend+i-iend+1,pend,i+1, iend);
        return root;
    }
};
Posted by at No comments:
Labels: ,
Subscribe to: Posts (Atom)