leetcode Question 102: Sqrt(x)

Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

Analysis:
According to Newton's Method(http://en.wikipedia.org/wiki/Newton's_method), we can use

to get the sqrt(x).

Code:

class Solution {
public:
    int sqrt(int x) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (x==0) {return 0;}
        if (x==1) {return 1;}
      
        double x0 = 1;
        double x1;
        while (true){
            x1 = (x0+ x/x0)/2;
            if (abs(x1-x0)<1){return x1;}
            x0=x1;
        }
        
    }
};

Another solution: the binary search approach is a more general way of solving this problem. One thing you need to consider is the length of the input, since taking the mid of a big value and computing its square may overflow the int type.
We can use "long long" , which have a max value 2^63-1.
The max of an int is 2^15-1
The max of a long is 2^31-1

class Solution {
public:
    int sqrt(int x) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        long long high = x;
        long long low = 0;
        if (x<=0) {return 0;}
        if (x==1) {return 1;}
        while (high-low >1){
            long long mid = low + (high-low)/2;
            if (mid*mid<=x){low = mid;}
            else {high = mid;}
        }
        return low;
    }
};

leetcode Question 74: Pow(x,n)

Pow(x,n)


Analysis:
If we just use the normal way of calculation, when face 1 to the power of 10000, the computation complexity is too high.

Consider this way:
If we want to get 2^10,

2^10  = 2^4 * 2^4 *2^2
2^4 = 2^2*2^2
2^2 = 2*2

Let's see this in a bottom-up way, totally it needs to loop n/2 > 0 times, first we have 2^1=2, then we can have 2^2 = 2*2=4, and again we have 2^4 = 4*4, (key point:) and if n%2==1, we need one more previous value, which is 2^2 here, so we have 2^4*2^4*2^2 = 2^10.

Details see the code below.


Source Code:

class Solution {
public:
    double pow(double x, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int sign = n>=0?1:-1;
        double y=1;
        for (int i=0;i<abs(n);i++){
            y=y*x;      
        }
        if (sign==-1) {return 1/y;}
        else {return y;}
    }
};

class Solution {
public:
    double pow(double x, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (x==0){
            if (n==0){return 1;}
            else {return 0;}
        }
        
        if (n==0){
            return 1;
        }
        
        bool pos=true;
        if (n<0){
            pos = false;
            n=abs(n);
        }
        
        double np=x;
        double res=1;
        while (n>0){
            if (n%2==1){
                res = res * np;
            }
            np=np*np;
            n=n/2;
        }
    
        return  pos? res:1/res; 
        
    }
};

leetcode Question 1: Two Sum

Two Sum

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Analysis:
The easiest way is to use 2 loops, search every pair of elements, find the result and return the index. The idea is simple but the complexity is high ( O(n^2) ).

Let's think in another way, the above idea tracks the forward way:   A[i]+A[j]==target.
What about the opposite way?   target-A[i]==A[j].

Yep! So for each element A[i], if we know there exists A[j]== target-A[i], and the i<j, then OK!

Thus, we use hash map to store the numbers, scan the whole table and use map.find() function to find the existence of the elements. Note that the question requires (1) the index order, (2) the index is the array number +1.


Code: (O(n^2))

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> res;
        for (int i=0;i<numbers.size()-1;i++){
            for (int j=i+1;j<numbers.size();j++){
                if (numbers[i]+numbers[j]==target){
                    res.push_back(i+1);
                    res.push_back(j+1);
                    return res;
                }
            }    
        }
        return res;
    }
};

Code(O(n)):

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> res;
        map<int,int>hmap;
        hmap.clear();
        for (int i=0;i<numbers.size();i++){
            hmap[numbers[i]]=i;
        }
        for (int i=0;i<numbers.size();i++){
            if (hmap.find((target-numbers[i]))!=hmap.end()){
                if (i<hmap[target-numbers[i]]){
                    res.push_back(i+1);
                    res.push_back(hmap[target-numbers[i]]+1);
                    return res;
                }
                if (i>hmap[target-numbers[i]]){
                    res.push_back(hmap[target-numbers[i]]+1);
                    res.push_back(i+1);
                    return res;
                }
            }
        }
    }
};

Python Version:

class Solution:
    # @return a tuple, (index1, index2)
    def twoSum(self, num, target):
        mp={}
        #construct the dict, with multiple values
        for idx, val in enumerate(num):
            mp.setdefault(val,[]).append(idx+1) 
        
        for idx,val in enumerate(num):
            if (target-val!=val and mp.has_key(target-val)): 
                return sorted((mp[target-val][0],mp[val][0]))
            if (target-val==val and len(mp[val])>1):
                return (mp[val][0],mp[val][1])

leetcode Question 75: Recover Binary Search Tree

Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

Analysis:

The question requires O(1) space, let's first consider the case without this.
How to traverse BST?
Yep! The inOrder tree traversal.  (left->root->right)
So the easiest way is inorder traverse the BST and find the element pair (two elements) which are not consistent with the definition of BST. In order to get the order, a queue is needed, which is O(n).

Now how to do this procedure in O(1)?
What we need is actually two pointers, which point to 2 tree nodes where is incorrect. Therefore, we only need to store these two pointers, and, we also need another pointer to store the previous element, in order to  compare if the current element is valid or not.

In the code below, you will find, the last step is to replace the wrong pair's value. And the inOrder function is to search the whole BST and find the wrong pairs.

Note that, (1)the previous element is NOT the root node of the current element, but the previous element in the "inOrder" order; (2) To store the wrong pair, the first found wrong element is stored in first pointer, while the next is stored in the second pointer.

e.g. The correct BST is below:

The inorder traversal is :  1 3 4 6 7 8 10 13 14

If we change the value 4 and 8:  1 3 8 6 7 4 10 13 14, when it goes to the node 6, now the pre->val = 8, check if pre<current node, which is wrong here (8>6). So we store the first pointer pointing to the node 6 and second pointer pointing to the node 8. To do so, we have stored the wrong nodes, if every other node keep the correct order, then swapping these nodes is enough for the problem. In other words, after the whole traversal, what we need to do is just changing the values of the first and second. Continue our example here, when the traversal goes to the node 4, now the node 7 is its pre, which is also wrong, so the second wrong node is found, and we change the second pointer pointing to node 4.

Code(C++):

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *first;
    TreeNode *second;
    TreeNode *pre;
    
    void inOrder(TreeNode *root){
        if (root==NULL){return;}
        else{
            inOrder(root->left);
            if (pre == NULL){pre = root;}
            else {
                if (pre->val > root->val){
                    if (first==NULL) {first = pre;}
                    second = root;
                }
                pre = root;
            }
            inOrder(root->right);
            
        }
    }
    void recoverTree(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        pre = NULL;
        first = NULL;
        second= NULL;
        inOrder(root);
        int val;
        val = first->val;
        first->val=second->val;
        second->val=val;
        return;
    }
};

Code(Python):

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return a tree node
    prev = None
    p1 = None
    p2 = None
    
    def inOrder(self, root):
        if root == None:
            return
        else:
            self.inOrder(root.left)
            if self.prev == None:
                self.prev = root
            else:
                if root.val <= self.prev.val:
                    if self.p1 == None:
                        self.p1 = self.prev
                    self.p2 = root
                self.prev = root
            self.inOrder(root.right)
    
    def recoverTree(self, root):
        self.prev = None
        self.p1 = None
        self.p2 = None
        self.inOrder(root)
        tmp = self.p1.val
        self.p1.val = self.p2.val
        self.p2.val = tmp
        return root
        

leetcode Question 81: Remove Element

Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Analysis:
Idea is to use double pointer (i and j ), i goes from 1st to the last element in the array, think i scan all the array, and j stores the final result. e.g.
A = 1 2 3 4 5 3 6 7;
i j are set to start position.
i goes from 1 to 7, if this element is not the element requested,A[j]=A[i] (no change at start because i and j are same.), then i ++, j++, otherwise, i++, means to skip this element,but j stays, from next element, continue the above step, when set A[j]=A[i], which means A[j] was originally stored the removed element but now stores the next one.
A = 1 2 3 4 5 3 6 7,  elem=3
       i   i  i
       j   j  j

then
A = 1 2 3 4 5 3 6 7
       i  i      i
       j  j  j

and A = 1 2 4 4 5 3 6 7
                          i
                      j
finally, A= 1 2 4 5 6 7


Code:

class Solution {
public:
    int removeElement(int A[], int n, int elem) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int i=0;
        int j=0;
        while (i<n){
            if (A[i]!=elem){
                A[j]=A[i];
                j++;
            }
                i++;
        }
        return j;
    }
};

leetcode Question 80: Remove Duplicates from Sorted List II

 Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

Analysis:

To solve this problem, one pointer is needed to store the previous element. See example to get a better understanding.

p is the current element (now its value is 2 in e.g.), p2 is the next element after p, for each p, we check the elements after p (3 3 4), and find the non-duplicate position (4), and remove the duplicates(3->3).

Note. To handle the first is duplicate element, we put another node ahead the head.

e.g.
1 2 3 3 4 4 5
go through, 1 and 2,
                  1->2->3->3->4
                        p->p2             check if p2.val==p2.next.val
                        p->     p2        go to next element and check
                        p-------->      if all duplicates found, let p.next=p2.next, in order to remove the duplicates.


Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if ((head==NULL) || (head->next == NULL) ){return head;}
        ListNode* pre = new ListNode(0);
        pre->next = head;
        head =pre;
        ListNode* p = head;
                    
        while(p->next!=NULL){
            ListNode *p2 = p->next;
            while ((p2->next!=NULL)&&(p2->val==p2->next->val)){
                p2=p2->next;
            }
            if (p2!=p->next){
                p->next=p2->next;
            }else{
                p=p->next;
            }
        }  
        return head->next;
    }
};