Showing posts with label binary search. Show all posts
Showing posts with label binary search. Show all posts

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 (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: ,

LintCode(68) Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values.
Have you met this question in a real interview? 
Yes
Example
Given binary tree {1,#,2,3},
   1
    \
     2
    /
   3

return [3,2,1].

Challenge
Can you do it without recursion?


最头疼了，比那尼玛word ladder还难理解。。干脆贴个答案吧，碰到就听天由命了。。。

 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
class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> result;
        stack<TreeNode *> myStack;
        
        TreeNode *current = root, *lastVisited = NULL;
        while (current != NULL || !myStack.empty()) {
            while (current != NULL) {
                myStack.push(current);
                current = current->left;
            }
            current = myStack.top(); 
            if (current->right == NULL || current->right == lastVisited) {
                myStack.pop();
                result.push_back(current->val);
                lastVisited = current;
                current = NULL;
            } else {
                current = current->right;
            }
        }
        return result;
    }
};
Posted by at No comments:
Labels:

LintCode (86) Binary Search Tree Inorder Traversal Iterator

Design an iterator over a binary search tree with the following rules:
  • Elements are visited in ascending order (i.e. an in-order traversal)
  • next() and hasNext() queries run in O(1) time in average.
Have you met this question in a real interview? 
Yes
Example
For the following binary search tree, in-order traversal by using iterator is [1, 6, 10, 11, 12]
   10
 /    \
1      11
 \       \
  6       12
Challenge
Extra memory usage O(h), h is the height of the tree.


这题和上一题，inorder traversal without recursion是一样的，做会了那题这题就好说了。

总是保持当前stk存的指针为最左， 所以判断has next就是判断stk是不是空，而获取next的时候，则返回stk最顶，但返回前需要继续向右孩子的最左遍历以保持最左面。 所以思想和上题是一致的。



 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
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 * Example of iterate a tree:
 * Solution iterator = Solution(root);
 * while (iterator.hasNext()) {
 *    TreeNode * node = iterator.next();
 *    do something for node
 */
class Solution {
public:
    //@param root: The root of binary tree.
    Solution(TreeNode *root) {
        // write your code here
        while(root){
            stk.push(root);
            root=root->left;
        }
    }

    //@return: True if there has next node, or false
    bool hasNext() {
        // write your code here
        return !stk.empty();
    }
    
    //@return: return next node
    TreeNode* next() {
        // write your code here
        if (stk.empty())
            return 0;
        TreeNode* tmp=stk.top();
        stk.pop();
        TreeNode* cur;
        cur=tmp->right;
        while(cur){
            stk.push(cur);
            cur=cur->left;
        }
        return tmp;
    }
    
    stack<TreeNode*> stk;
};
Posted by at No comments:
Labels:

Thursday, July 23, 2015

LintCode(95) Validate binary search tree

Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than the node's key.
  • Both the left and right subtrees must also be binary search trees.
Have you met this question in a real interview? 
Yes

Example
An example:
  2
 / \
1   3
   /
  4
   \
    5
The above binary tree is serialized as {2,1,3,#,#,4,#,#,5} (in level order).

分治，看看左右孩子是不是，然后看看当前是不是，按照post order走一圈就是了



 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
/**
 * 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 binary tree.
     * @return: True if the binary tree is BST, or false
     */
    bool isValidBST(TreeNode *root) {
        // write your code here
        if (!root)
            return true;
        if (!isValidBST(root->left))
            return false;
        if (!isValidBST(root->right))
            return false;
        if (root->left && root->left->val>=root->val)
            return false;
        if (root->right && root->right->val<=root->val)
            return false;
        return true;
    }
};



更正一下，这个解释错的。。。有一个test case没过，检查了一下发现是这样的：


上面的解法只是检查local的结构符合不符合，但是整体不对，




所以换一个思路，用inorder， 保证单调递增， 即， 保证当前大于左孩子，且，当前大于所有之前遍历过得最大值












 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
/**
 * 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 binary tree.
     * @return: True if the binary tree is BST, or false
     */
    bool isValidBST(TreeNode *root) {
        // write your code here
        long val;
        long m=LONG_MIN;
        return inorder(root, val,m);
    }
    
    bool inorder(TreeNode* root, long& val, long &m){
        if (root==0){
            return true;
        }
        long left=LONG_MIN;
        if (!inorder(root->left, val,m))
            return false;
        if (root->val<=left || root->val<=m)
            return false;
        val=root->val;
        m=max(m,val);
        return inorder(root->right, val, m);
    }
};










Posted by



at





No comments:
  

















Labels:
,
















          

        

          

        

Wednesday, July 22, 2015


          

        









LintCode (63) Search in Rotated Array II














Search in Rotated Sorted Array II











40%

Accepted





Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?



Would this affect the run-time complexity? How and why?



Write a function to determine if a given target is in the array.











和find min in rotated array with dup是一样的，如果有dup，判断左旋和右旋无法判断的时候，移动beg,这样，最差复杂度为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
34
35
36
37
class Solution {
    /** 
     * param A : an integer ratated sorted array and duplicates are allowed
     * param target :  an integer to be search
     * return : a boolean 
     */
public:
    bool search(vector<int> &A, int target) {
        // write your code here
        if (A.empty())
            return false;
        int beg=0; 
        int end=A.size()-1;
        while(beg+1<end){
            int mid=beg+(end-beg)/2;
            if (A[mid]==target)
                return true;
            if (A[mid]>A[beg]){
                if (A[mid]>=target && target>=A[beg]){
                    end=mid-1;
                } else{
                    beg=mid+1;
                }
            } else if (A[mid]<A[beg]){
                if (A[mid]<=target && target<=A[end]){
                    beg=mid+1;
                } else{
                    end=mid-1;
                }
            } else{
                beg++;
            }
        }
        return (A[beg]==target || A[end]==target);
    }
    
};










Posted by



at





No comments:
  

















Labels:
,
,
























LintCode (160） Find Minimum in Rotated Array II












Suppose a sorted array is rotated at some pivot unknown to you beforehand.



(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).



Find the minimum element.



The array may contain duplicates.







如果有dup,会出现mid=beg的情况，二分不出来，只能移动beg了。。。












 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
class Solution {
public:
    /**
     * @param num: a rotated sorted array
     * @return: the minimum number in the array
     */
    int findMin(vector<int> &num) {
        if (num.empty()){
            return -1;
        }
        int beg=0; 
        int end=num.size()-1;
        if (num[beg]<num[end])
            return num[beg];
        int mid=0;
        
        while(beg+1<end){
            mid=beg+(end-beg)/2;
            if(num[mid]>num[beg]){
                beg=mid;
            } else if (num[mid]<num[beg]){
                end=mid;
            } else{
                beg++;
            }
        }
        return min(num[beg], num[end]);
    }
};










Posted by



at





No comments:
  

















Labels:
,
























LintCode (159) Find Minimum in Rotated array












Suppose a sorted array is rotated at some pivot unknown to you beforehand.



(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).



Find the minimum element.





Have you met this question in a real interview? 





Yes





Example



Given [4, 5, 6, 7, 0, 1, 2] return 0









Note



You may assume no duplicate exists in the array.







二分法， 和search一样。。。其实还要更简单。。。。














 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
class Solution {
public:
    /**
     * @param num: a rotated sorted array
     * @return: the minimum number in the array
     */
    int findMin(vector<int> &num) {
        if (num.empty())
            return -1;
        
        int beg = 0;
        int end = num.size()-1; 
        if (num[beg]<num[end])
            return num[beg];
        while(beg+1<end){
            int mid=beg+(end-beg)/2;
            if (num[mid]>num[beg])
                beg=mid;
            else
                end=mid;
        }
        return min(num[beg],num[end]);
    }
    
};










Posted by



at





No comments:
  

















Labels:
,
















          

        

          

        

Tuesday, July 21, 2015


          

        









LintCode (65) Median of two sorted array












There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays.





Have you met this question in a real interview? 





Yes





Example



Given A=[1,2,3,4,5,6] and B=[2,3,4,5], the median is 3.5.



Given A=[1,2,3] and B=[4,5], the median is 3.









Challenge



The overall run time complexity should be O(log (m+n)).







截一半，这题好难。。。就算刷过一次了，回过头来还是觉得难。。。。



不过用rotated array 的思路的话， 就好做些。







比如A 和B 等长， 求第k个， 比较A的第k/2和B的第k/2的值， 如果A[k/2] < B[ k/2] 那么久放弃A前k/2，反之，放弃B的前k/2， 但是具体操作的时候还是有出入。。。















 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
class Solution {
public:
    /**
     * @param A: An integer array.
     * @param B: An integer array.
     * @return: a double whose format is *.5 or *.0
     */
    double findMedianSortedArrays(vector<int> A, vector<int> B) {
        // write your code here
        int m=A.size();
        int n=B.size();
        int total=m+n;
        
        if (total%2==1){
            return findK(A,0,A.size(), B, 0, B.size(), total/2+1);
        } else{
            return (findK(A, 0, A.size(), B, 0, B.size(), total/2)
                    +findK(A, 0, A.size(), B, 0, B.size(), total/2+1))/2.;
        }
    }
    
    int findK(vector<int>& A, int begA, int lenA, vector<int>& B, int begB, int lenB, int k){
        if (lenA>lenB){
            return findK(B,begB, lenB, A, begA, lenA, k);
        }
        if (lenA==0)
            return B[begB+k-1];
        if (k==1){
            return min(A[begA], B[begB]);
        }
        int midA= min(lenA, k/2);
        int midB= k-midA;
        if (A[begA+midA-1]<=B[begB+midB-1]){
            return findK(A, begA+midA, lenA-midA, B, begB, lenB, k-midA);
        } else{
            return findK(A, begA, lenA, B, begB+midB, lenB-midB, k-midB);
        }
    }
};










Posted by



at





No comments:
  

















Labels:
























LintCode (62) Search in Rotated Sorted Array












Suppose a sorted array is rotated at some pivot unknown to you beforehand.



(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).



You are given a target value to search. If found in the array return its index, otherwise return -1.



You may assume no duplicate exists in the array.





Have you met this question in a real interview? 





Yes





Example



For [4, 5, 1, 2, 3] and target=1, return 2.



For [4, 5, 1, 2, 3] and target=0, return -1.









Challenge



O(logN) time







画一下图就好，比较一下rotate以后，会发现，只有中间transient的位置才需要特别处理，否则还是正常的bsearch. 二分法的话，就是区别左旋区间还是右旋区间， 左旋的话就是mid>beg, 右旋的话就是mid<beg



然后还要再分一次，就是递增递减区间还是位于transient 区间







      /                           /



    /                           /



  /                                    /    



/                                    /














 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
class Solution {
    /** 
     * 二分法， 只是分的时候只用bsearch找target在
     * [beg,end]的区间内，另一种情形用else来cover
     * 子情况为左旋右旋， 左旋和右旋各包括一种sorted
     * 和非sorted得情况
     * param A : an integer ratated sorted array
     * param target :  an integer to be searched
     * return : an integer
     */
public:
    int search(vector<int> &A, int target) {
        // write your code here
        if (A.empty())
            return -1;
        int beg=0;
        int end=A.size()-1;
        while(beg+1<end){
            int mid=beg+(end-beg)/2;
            if (A[mid]>A[beg]){
                if (A[mid]>=target && A[beg]<=target)
                    end=mid;
                else
                    beg=mid;
            } else{
                if (A[mid]<=target && A[end]>=target)
                    beg=mid;
                else
                    end=mid;
            }
        }
        if (A[beg]==target)
            return beg;
        if (A[end]==target)
            return end;
        return -1;
    }
    
};










Posted by



at





No comments:
  

















Labels:
,
















        

      









Subscribe to:
Posts (Atom)