Friday, October 10, 2014

[Leetcode] Search in Rotated Sorted Array II

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.


    bool search(int A[], int n, int target) {
        int b = 0;
        int e = n - 1;
        while(b <= e)
        {
            int m = (b + e) / 2;
            if (A[m] == target)
                return true;
   //right part duplicate, and move end backward as the end value could not be the target 
            else if (A[m] == A[e])
                e = e - 1;
   //left part duplicate, and move begin forward as the begin value could not be the target  
            else if (A[m] == A[b])
                b = b + 1;
   //if the right part is still sorted 
            else if (A[m] < A[e])
            {
    //if the target is in the right side range
                if (target > A[m] && target <= A[e])
                    b = m + 1;
                else
                    e = m - 1;
            }
   //left part must be sorted 
            else
            {
    //if the target is in the left side range
                if (target < A[m] && target >= A[b])
                    e = m - 1;
                else
                    b = m + 1;                
            }
        }
        
        return false;
    }

[leetcode] Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.


ListNode *deleteDuplicates(ListNode *head) {
        ListNode* curr = head;
        while(curr != NULL && curr->next != NULL)
        {
   //if curr node value is equal to the next node value, remove the next node
            if (curr->val == curr->next->val)
            {
                ListNode* tmp = curr->next;
                curr->next = curr->next->next;
                delete tmp;
            }
            else
            {
    //otherwise, move to next node
                curr = curr->next;
            }
        }
        return head;
    }

[Leetcode] 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:


class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
  //use dummy head to make it easy to handle head node which is duplicate
        ListNode* prev = dummyHead;
        ListNode* curr = head;
        while(curr != NULL)
        {
   //When find a node whose value is equal to its next node
            if (curr->next != NULL && curr->val == curr->next->val)
            {
    //remove all its next nodes
                while(curr != NULL && curr->next != NULL && curr->val == curr->next->val)
                {
                    ListNode* next = curr->next;
                    curr->next = curr->next->next;
                    delete next;
                }
    //then remove itself. 
                ListNode* tmp = curr;
                prev->next = curr->next;
                curr = curr->next;
                delete tmp;
            }
            else
            {
    //otherwise, move to next node
                prev = curr;
                curr = curr->next;
            }
        }
        
        return dummyHead->next;
    }
};

[Leetcode] Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.
Analysis:

  • Create left part of list for nodes less than x
  • create right part of list for nodes greater than or equal to x
  • concatenate them

class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        ListNode* dummyHead1 = new ListNode(0);
        ListNode* dummyHead2 = new ListNode(0);
        ListNode* p1 = dummyHead1;
        ListNode* p2 = dummyHead2;
        while(head != NULL)
        {
            if (head->val < x)
            {
                p1->next = head;
                p1 = p1->next;
            }
            else
            {
                p2->next = head;
                p2 = p2->next;
            }
            head = head->next;
        }
        
        p2->next = NULL;
        p1->next = dummyHead2->next;
        
        return dummyHead1->next;
    }
};

[Leetcode] Scramble String

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":
    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t
To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".
    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t
We say that "rgeat" is a scrambled string of "great".
Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".
    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a
We say that "rgtae" is a scrambled string of "great".
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
Analysis:
for "rgtae" and "great", compare the following Recursively
r|gtae, g|reat, r|gtae, grea|t, 
Rg|tae, gr|eat, rg|tae, gre|at, 
rgt|ae, gre|at, rgt|ae, gr|eat, 
Rgta|e, grea|t, rgta|e, g|reat 


    bool isScramble(string s1, string s2) {
            if (s1.size() != s2.size())
                return false;
            else if (s1 == s2)
                return true;
            else
            {
                unordered_map<char, int> m;
                for (int i=0; i<s1.size(); i++)
                    m[s1[i]]++;
                for (int i=0; i<s2.size(); i++)
                {
                    if (m.find(s2[i]) == m.end() || m[s2[i]] <= 0)
                        return false;
                    m[s2[i]]--;
        
                }
                
                for(int i=1; i<s1.size();i++)
                {
                    if ((isScramble(s1.substr(0,i),s2.substr(0,i)) && isScramble(s1.substr(i),s2.substr(i))) || 
                        (isScramble(s1.substr(0,i),s2.substr(s1.size() - i)) && isScramble(s1.substr(i),s2.substr(0,s1.size() - i))))
                        return true;
                }
                return false;                
            }
    }

[Leetcode] Merge Sorted Array

Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and nrespectively.


class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        int i = m -1;
        int j = n - 1;
        while(i >=0 && j >=0)
        {
            if (A[i] > B[j])
                A[i+j+1] = A[i--];
            else
                A[i+j+1] = B[j--];
        }
        
        while(j >=0)
        {
            A[i+j+1] = B[j--];
        }
    }
};

Thursday, September 25, 2014

[Leetcode] Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
00 - 0
01 - 1
11 - 3
10 - 2
Note:
For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.
Analysis:




    vector<int> grayCode(int n) {
  
        vector<int> codes(1,0);
        for (int i = 0; i<n; i++)
        {
            for (int j=codes.size()-1; j >=0 ; j--)
            {
                int code = 0x1 << i | codes[j];
                codes.push_back(code);
            }
        }
        
        return codes;
    }