Online Judge Solutions

Showing posts with label LeetCode Solutions. Show all posts
Showing posts with label LeetCode Solutions. Show all posts

Thursday, July 20, 2017

Contacts Detective

Given a list of contact information,
Each contact has name, phone and email. 
Contacts with same email are same person,
Contacts with same phone are also same person, 
each person may have multiple names, phones or emails.  
Task: Group contacts by person
public class Main {
    static public class Contact {
        public Contact(String name, String phone, String email) {
            this.name = name;
            this.phone = phone;
            this.email = email;
        }
        public String name;
        public String phone;
        public String email;

        @Override
        public int hashCode() {
            return phone.hashCode() ^ email.hashCode();
        }

        @Override
        public boolean equals(Object other) {
            if (this == other) {
                return true;
            }
            if (other == null || ! (other instanceof Contact)) {
                return false;
            }

            Contact o = (Contact) other;
            return this.phone == o.phone && this.email == o.email;
        }
    }

    static Set> merge(List input) {
        Map> map = new HashMap<>();
        Set> output = new HashSet<>();
        for (Contact contact: input) {
            Set sameContacts = new HashSet<>();
            Set differentEmails = new HashSet<>();
            Set differentPhones = new HashSet<>();

            sameContacts.add(contact);
            differentEmails.add(contact.email);
            differentPhones.add(contact.phone);

            if (map.containsKey(contact.phone)) {
                Set dupContacts = map.get(contact.phone);
                sameContacts.addAll(dupContacts);
                for (Contact c: dupContacts) {
                    differentEmails.add(c.email);
                    differentPhones.add(c.phone);
                }
            }

            if (map.containsKey(contact.email)) {
                Set dupContacts = map.get(contact.email);
                sameContacts.addAll(dupContacts);
                for (Contact c: dupContacts) {
                    differentEmails.add(c.email);
                    differentPhones.add(c.phone);
                }
            }

            // Make all phone keys point to the same set
            for(String phone: differentPhones) {
                map.put(phone, sameContacts);
            }

            // Make all email keys point to the same set
            for(String email: differentEmails) {
                map.put(email, sameContacts);
            }
        }

        output.addAll(map.values());
        return output;
    }

    static Set> merge2(List input) {
        Map> map = new HashMap<>();
        for (Contact contact: input) {
            if (map.containsKey(contact.phone)) {
                map.get(contact.phone).add(contact);
            } else {
                Set contacts = new HashSet<>();
                contacts.add(contact);
                map.put(contact.phone, contacts);
            }

            if (map.containsKey(contact.email)) {
                map.get(contact.email).add(contact);
            } else {
                Set contacts = new HashSet<>();
                contacts.add(contact);
                map.put(contact.email, contacts);
            }
        }

        Set> output = new HashSet<>();
        Set visited =  new HashSet<>();
        for (Contact contact: input) {
            if (!visited.contains(contact)) {
                Set sameContacts = new HashSet<>();
                getSameContacts(map, contact, sameContacts, visited);
                output.add(sameContacts);
            }
        }
       return output;
    }

    static void getSameContacts(Map> map, Contact contact, Set sameContacts,  Set visited) {
          if (!visited.contains(contact)) {
              sameContacts.add(contact);
              visited.add(contact);
              if (map.containsKey(contact.phone)) {
                  Set contactsSamePonne = map.get(contact.phone);
                  for (Contact c : contactsSamePonne) {
                      getSameContacts(map, c, sameContacts, visited);
                  }
              }
              if (map.containsKey(contact.email)) {
                  Set contactsSameEmail = map.get(contact.email);
                  for (Contact c : contactsSameEmail) {
                      getSameContacts(map, c, sameContacts, visited);
                  }
              }
          }
    }

    public static void main(String[] args) throws InterruptedException {
        List contacts = Arrays.asList(
            new Contact("name1", "phone1", "email1"),
            new Contact("name2", "phone2", "email2"),
            new Contact("name3", "phone3", "email3")
        );

        Set> out =  merge(contacts);
        Assert.isTrue(out.size() == 3);

        contacts = Arrays.asList(
            new Contact("name1", "phone1", "email1"),
            new Contact("name2", "phone2", "email2"),
            new Contact("name3", "phone3", "email3"),
            new Contact("name4", "phone1", "email2")
        );
        out =  merge(contacts);
        Assert.isTrue(out.size() == 2);

       contacts = Arrays.asList(
            new Contact("name1", "phone1", "email1"),
            new Contact("name2", "phone2", "email2"),
            new Contact("name3", "phone1", "email3"),
            new Contact("name123", "phone123", "email123"),
            new Contact("name4", "phone2", "email1")
        );
        out =  merge(contacts);
        Assert.isTrue(out.size() == 2);

        contacts = Arrays.asList(
            new Contact("name1", "phone1", "email1"),
            new Contact("name2", "phone2", "email2"),
            new Contact("name3", "phone1", "email3"),
            new Contact("name123", "phone123", "email123"),
            new Contact("name4", "phone5", "email2")
        );
        out =  merge(contacts);
        Assert.isTrue(out.size() == 3);
    }
 }
Class ContactGroup
{
      Public List<Contact> contact;
      Public Hashset<string> phone;

      Public ContactGroup()
      {
          contact= new List<Contact>();
          Phone = new HashSet<string>();
       }
}


List<List<Contact>> GroupContact(List<Contact> contacts)
{
 if(contacts == null) return null;
 
 Dictionary<string, ContactGroup>> contactDictionary = new Dictionary<string, ContactGroup>();

 foreach(Contact contact in contacts)
 {
    if(!contactDictionary.ContainsKey(contact.email))
    {
       contactDictionary[contact.email] = new ContactGroup();
    }
  
    contactDictionary[contact.email].Contact.Add(contact);
    contactDictionary[contact.email].Phone.Add(contact.phone);
 }
 
 List<ContactGroup> res = new List<ContactGroup>();
 foreach(var kvp in contactDictionary)
 {
      Bool bFound = false;
      foreach(var contactGroup in res)
      {
        if(contactGroup.phone.IntersetWith(kvp.phone).Any())
        {
            contactGroup.contact.Add(kvp.value.contact);
            contactGroup.Phone.Add(kvp.value.Phone);
            bFound = true;
            break;
         }
      }
      if(!bFound)
      {
          res.Add(kvp.value);
      }

   }

   List<List<Contact>> resContact = new List<List<Contact>>();
   foreach(ContactGroup group in res)
   {
      resContact.Add(group.contact);
   }
   return resContact;
}

static Set<Set<Contact>> merge5(List<Contact> contacts) { Map<String, String> map = new HashMap<>(); for (Contact c : contacts) { map.put(c.email, c.email); map.put(c.phone, c.phone); } for (Contact c : contacts) { union(map, c.phone, c.email); } Map<String, Set<Contact>> temp = new HashMap<>(); for (Contact c : contacts) { String key = find(map, c.email); temp.computeIfAbsent(key, x -> new HashSet<>()).add(c); } Set<Set<Contact>> output = new HashSet<>(); for (Map.Entry<String, Set<Contact>> entry : temp.entrySet()) { if (!entry.getValue().isEmpty()) { output.add(entry.getValue()); } } return output; } static void union(Map<String, String> map, String key1, String key2) { map.put(find(map, key1), find(map, key2)); } static String find(Map<String, String> map, String key) { if (key != map.get(key)) { map.put(key, find(map, map.get(key))); } return map.get(key); }

Wednesday, February 25, 2015

Rotate Array

Rotate an array of n elements to the right by k steps.
For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].
Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
class Solution {
    void rotateHelper(int A[], int k, int n)
    {
        int i = 0;
        while(i + k < n) 
        {
            int count = 0;
            for(; i+k < n; i++) {
                int t = A[i];
                A[i] = A[i+k];
                A[i+k] = t;
                count++;
            }   
            
            k = k - count % k; 
        }
    }


public:
    /**
     * param A: A string
     * param offset: Rotate string with offset.
     * return: Rotated string.
     */
     void rotate(int A[], int n, int k) {
        if (n < 2) return ;
        int K = n - k % n;
        
        rotateHelper(A, K, n); 
    }
};

Wednesday, January 28, 2015

Dungeon Game

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.
The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.
Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0's) or contain magic orbs that increase the knight's health (positive integers).
In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.
Write a function to determine the knight's minimum initial health so that he is able to rescue the princess.
For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.
-2 (K)-33
-5-101
1030-5 (P)

Notes:
  • The knight's health has no upper bound.
  • Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.
class Solution {
public:
    int calculateMinimumHP(vector<vector<int> > &dungeon) {
        int M = dungeon.size();
        int N = dungeon[0].size();
        
        dungeon[M-1][N-1] = max(-dungeon[M-1][N-1], 0);
        
        for(int j = N-2; j >= 0; j--) 
           dungeon[M-1][j] = max(dungeon[M-1][j+1] - dungeon[M-1][j], 0);
        
        for(int i = M-2; i >= 0; i--) 
           dungeon[i][N-1] = max(dungeon[i+1][N-1] - dungeon[i][N-1], 0); 
        
        for(int i = M-2; i >=0; i--)
          for(int j = N-2; j >= 0; j--) 
             dungeon[i][j] = max(min(dungeon[i+1][j], dungeon[i][j+1]) - dungeon[i][j], 0); 
        
        return dungeon[0][0] + 1 ;
    }
};

Tuesday, January 27, 2015

Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.
For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.
Note: The result may be very large, so you need to return a string instead of an integer.
bool myCompare (string i, string j) 
{ 
    return (i+j) > (j+i); 
}

class Solution {
public:
    string largestNumber(vector<int> &num) {
        vector<string> tmp;
        bool allZero = true;
        for(int i : num) {
           allZero = allZero && i == 0;
           tmp.push_back(to_string(i));
        }
        
        if (allZero) return "0";
        
        sort(tmp.begin(), tmp.end(), myCompare);
        string output = "";
        
        for(string s : tmp)
           output+=s;
           
        return output;
    }
};

Tuesday, December 16, 2014

Fraction to Recurring Decimal

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.
If the fractional part is repeating, enclose the repeating part in parentheses.
For example,
  • Given numerator = 1, denominator = 2, return "0.5".
  • Given numerator = 2, denominator = 1, return "2".
  • Given numerator = 2, denominator = 3, return "0.(6)".
 
class Solution {
public:
    
    string fractionToDecimal(int numerator, int denominator) {
       
       bool isNeg = false;
       
       if ((numerator >0 && denominator < 0) || (numerator < 0 && denominator > 0))
          isNeg = true;
       string output = to_string(num / den);
       
       long long rem = num % den;
       if (rem != 0) {       
           output.push_back('.');
           unordered_map<int, int> map;
           
           map[rem] = output.length();
           while(rem > 0) {
               rem *= 10;
               output.push_back('0' + rem/den);
               rem = rem % den;
               if (map.count(rem) == 1) {
                  output.insert(map[rem], "(");
                  output.push_back(')');
                  break;
               }
               map[rem] = output.length();
           }
       }
       
       if (isNeg) output.insert(0, "-");
       
       return output;
    }
};

Monday, December 15, 2014

Compare Version Numbers

Compare two version numbers version1 and version1.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.

For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.

Here is an example of version numbers ordering:
0.1 < 1.1 < 1.2 < 13.37
 
class Solution {
public:
    int compareVersion(string version1, string version2) {
        int i = 0, j = 0;
        int va = 0;
        int vb = 0;
        
        while(i < version1.length() || j < version2.length()) {
           while(i < version1.length() && version1[i] != '.')
             va = 10*va + version1[i++] - '0';
           i++; // skip '.'
           
           while(j < version2.length() && version2[j] != '.')
             vb = 10*vb + version2[j++] - '0';
           j++; // skip '.'
           
           if (va != vb) break;
           
           // reset to start new pair of numbers
           va = 0;
           vb = 0;
        }
        
        if (va == vb) return 0;
        return va > vb ? 1 : -1;
    }
};

Sunday, December 14, 2014

Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space. Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

For example, the following array
 3 5 1 2 9
After sort it becomes 1 2 3 5 9
The max gap is 9-5 = 4

class Solution {
public:
    int maximumGap(vector &num) {
        int mx = INT_MIN;
        int mn = INT_MAX;
        for(int i : num) {
            mx = max(mx, i);
            mn = min(mn, i);
        }
        
        // all element's are the same or there is less than 2 elements
        if (mx == mn || mx == INT_MIN) return 0;
        
        int n = num.size();
        int dist = (mx - mn + n - 1) / n;
        
        vector maxs(n, -1);
        vector mins(n, -1);
        
        for(int i : num) {
            int idx = (i-mn)/dist;
            maxs[idx] = maxs[idx] == -1 ? i : max(maxs[idx], i);
            mins[idx] = mins[idx] == -1 ? i : min(mins[idx], i);
        }
        
        int prevMX = mn;
        int ret = 0;
        for(int i = 0; i < n; i++)
        {
            if (mins[i] != -1) {
                ret = max(ret, mins[i]-prevMX);
                prevMX = maxs[i];
            }
        }
        
        return ret;
    }
};

Saturday, December 13, 2014

Binary Tree Upside Down

Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.
For example:
 Given a binary tree {1,2,3,4,5},
 1
 / \
 2 3
 / \
 4 5
return the root of the binary tree [4,5,2,#,#,3,1].
 4
 / \
 5 2
 / \
 3 1
 
class Solution {
public:
    TreeNode * newRoot=NULL;
    bool found=false;
    TreeNode *upsideDownBinaryTree(TreeNode *root) {
        if(root==NULL) return NULL;
        if(root->left==NULL) return root;
        recursive(root);
        return newRoot;
    }
    void recursive(TreeNode *root){
        if(root->left==NULL) return;
        recursive(root->left);
        if(root->left->left==NULL){
            if(!found){newRoot=root->left; found=true;}
            root->left->left=root->right;
            root->right=NULL;
            root->left->right=root;   
            root->left=NULL;
        }
    }
};
 
public class Solution {
    public TreeNode UpsideDownBinaryTree(TreeNode root) {
        TreeNode p = root, parent = null, parentRight = null;
        while (p!=null) {
            TreeNode left = p.left;
            p.left = parentRight;
            parentRight = p.right;
            p.right = parent;
            parent = p;
            p = left;
        }
        return parent;
    }
}
 
/** 
 * 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 *upsideDownBinaryTree(TreeNode *root) { 
        //using a dummy node to help to store the new tree       
        TreeNode dummy(0); 
        TreeNode *head =  &dummy, *left=NULL, *right=NULL; 


        while ( root!=NULL ) { 
            //find the right & left 
            left = root->right; 
            right = root; 
             
            //move root the next 
            root = root->left; 
             
            //replace the right with current root 
            right->left = head->left; 
            right->right = head->right; 
             
            //move the dummy to the root 
            dummy.right = right; 
            dummy.left = left; 
             
            //reset the head to the root 
            head = &dummy; 
     
        } 
         
        return head->right; 
    } 
}; 

Friday, December 12, 2014

Binary Tree Preorder Traversal

 
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

/*Method 1
    vector preorderTraversal(TreeNode *root) {
        vector output;
        if (!root) return output;
        
       stack st;
       st.push(root);
       while(!st.empty())
       {
           root = st.top();
           st.pop();
           output.push_back(root->val);
           if (root->right)
               st.push(root->right);
           if (root->left)
               st.push(root->left); 
       }
       
       return output;
    }
    */
    
    /*
    //Method 2
    vector preorderTraversal(TreeNode *root) {
       vector output;
       stack st;
       while(!st.empty() || root)
       {
           if (!root)
           {
              root = st.top();
              st.pop();
              root=root->right; 
           }
           else 
           {
               output.push_back(root->val);
               st.push(root);
               root = root->left; 
           }
       }
       
       return output;
    }
    */
    
     // Simple coder's solution
    vector preorderTraversal(TreeNode *root) {
       vector output;
       stack st;
     
       pushLeft(root, st, output);
       while (!st.empty()) {
            root = st.top();
            st.pop();
            pushLeft(root->right, st, output);
        }

       return output;
    }
    
    void pushLeft(TreeNode *root, stack &st, vector & output) {
       while(root) {
           output.push_back(root->val);
           st.push(root);
           root = root->left;
       }
   }
};

Saturday, November 22, 2014

Decode Ways

Decode Ways
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.

 

1. Dynamic Programming
class Solution {
public:
   
    int numDecodings(string s) {
       int n = s.length();
       if (n < 1) return 0;
       if (s[0] == '0') return 0;
       
       vector<int> ways(n+1, 0);
      
        ways[0] = 1, ways[1] = 1;
        
        for(int i = 2; i <= n; i++) {
            ways[i] = ways[i-1];
            if (s[i-1] == '0') {
                if (s[i-2] == '0' || s[i-2] > '2')
                  return 0;
                else
                  ways[i] = ways[i-2];
            }
            else {
                if ((s[i-2] == '1') || (s[i-2] == '2' && s[i-1] < '7')) ways[i] += ways[i-2];
            }
        }
       
        return ways[n];
    }
};

2. Notice we look up from no more than two previous result. We can use something similar to calculating Fibonacci series:
class Solution {
public:
    int numDecodings(string s) {
       int n = s.length();
       if (n < 1) return 0;
       int T_2 = 1, T_1 = 1;
        
       for(int i =0 ; i < n; i++) {
          int T = T_1;
          if (s[i] == '0') {
              if (i == 0 ||(s[i-1] == '0' || s[i-1] > '2'))
                return 0;
              else
                T = T_2;
          }
          else if (i > 0 && (s[i-1] == '1' || (s[i-1] == '2' && s[i] < '7')))
            T+= T_2;
         
          T_2 = T_1;
          T_1 = T;
       }
       
       return T_1;
    }
};

Regular Expression Matching

Implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

 
Solution 1, Recursion:

 bool isMatch(const char *s, const char *p) {
        if (!*p) return !*s;
       
        if (*(p+1) != '*') { return (*p == *s ||(*s && *p == '.')) && isMatch(s+1, p+1);}
       
        while(*s == *p || (*p == '.' && *s)) {
            if (isMatch(s, p+2)) return true;
            s++;
        }
        return isMatch(s, p+2);
    }

Solution 2. DP

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
       if (!*p) return !*s;
       int m = strlen(p);
       int n = strlen(s);
      
       vector<vector<bool>> match(m+1, vector<bool>(n+1, false));
      
       match[0][0] = 1;
       match[1][1] = s[0] == p[0] || p[0] == '.';
      
       // When s is empty, but p = '.*', p matches s
       for(int i = 2; i <=m; i++)
           match[i][0] = p[i-1] == '*'? match[i-2][0] : false;
       // starting from second char in p
       for(int i = 2; i <= m; i++)
           for(int j = 1; j <= n; j++)
              if (p[i-1]== '*')
                match[i][j] = isSame(s[j-1], p[i-2])? match[i-2][j] || match[i-2][j-1] || match[i-1][j-1] || match[i][j-1] : match[i-2][j];
             else 
                match[i][j] = isSame(s[j-1], p[i-1]) && match[i-1][j-1];
          
       
        return match[m][n];
    }
   
    bool isSame(char a, char b){
        return (a == b || b=='.');
    }
};

Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
 
//
//   D[i][j] = | D[i-1][j-1])  A[i] == A[j]
//             |
//             | 1 + min(D[i][j-1], D[i-1][j], D[i-1][j-1])   A[i] != A[j]
//
class Solution {
public:
    int minDistance(string A, string B) {
       
        int m = A.size();
        int n = B.size();
        vector<int> D(n + 1, 0);
       
        for(int j = 0; j <=n; j++)
           D[j] = j;
       
        for(int i = 1; i <= m; i++) {
          int D_i_1_j_1 = i-1; // D[i-1][0]
          D[0] = i;  // D[i][0]
         
          for(int j = 1; j <= n; j++) {
              int T = A[i-1] == B[j-1] ? D_i_1_j_1 : 1 + min(D[j-1], min(D[j], D_i_1_j_1));
              D_i_1_j_1 = D[j];
              D[j] = T;
          }
        }
        return D[n];
    } 
};

// DP2
class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.length();
        int n = word2.length();
        if(m == 0) return n;
        if(n==0) return m;
       
        vector<vector<int>> map(m+1);
        for(int i = 0;i  < m+1; i++)
           map[i] = vector<int>(n+1, 0);
        for(int i = 0; i <=m; i++)
   map[i][0] =i;
  for(int i = 0; i <=n; i++)
   map[0][i] =i;
        for (int i = 1; i <=m; i++)
         for (int j = 1; j <=n; j++)   
          {
              if (word1[i-1] == word2[j-1])
                 map[i][j] = map[i-1][j-1];
              else {
                 map[i][j] = min(map[i-1][j], map[i][j-1]);
                 map[i][j] = min(map[i][j], map[i-1][j-1]);
                 map[i][j] +=1;
              }
          }
            
        return map[m][n];
   
    }
};

// DP 3

class Solution {
public:
    int minDistance(string word1, string word2) {
        int l1 = word1.size();
        int l2 = word2.size();
        vector<int> f(l2+1, 0);
        for (int j = 1; j <= l2; ++j)
            f[j] = j;
        for (int i = 1; i <= l1; ++i)
        {
            int prev = i;
            for (int j = 1; j <= l2; ++j)
            {
                int cur;
                if (word1[i-1] == word2[j-1]) {
                    cur = f[j-1];
                } else {
                    cur = min(min(f[j-1], prev), f[j]) + 1;
                }
                f[j-1] = prev;
                prev = cur;
            }
            f[l2] = prev;
        }
        return f[l2];
    } 
};

Friday, November 21, 2014

Valid Number

Valid Number
Validate if a given string is numeric.
Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

 
// Sol1 http://www.mitbbs.com/article_t1/JobHunting/32787241_0_2.html
class Solution {
public:
    bool isNumber(const char *s) {
       if (!s) return false;
      
       while(*s == ' ')
         s++;
       
       // sign
       if (*s == '+' || *s == '-')
         s++;
        
       int n = getDigits(s);
      
       if (*s == '.') {
           s++;
           n += getDigits(s);
       }
      
       // digits before and after '.' must > 0, ".1" is valid
       if (n < 1) return false;
      
       if (*s == 'e') {
          s++;
          if (*s == '+' || *s == '-')
            s++;
          n = getDigits(s);
          if (n < 1) return false;
       }
      
       // trailing spaces is fine.
       while(*s == ' ') s++;
       return *s == NULL;
    }
   
    // count valid digits and move pointer
    int getDigits(const char *&s){
        int count = 0;
        while (*s >='0' && *s <='9'){
            count++;
            s++;
        }
        return count;
    }
};

// http://n00tc0d3r.blogspot.com/2013/06/valid-number.html
class Solution {
public:
    bool isNumber(const char *s) {
       int fsm[][9] = { 
                     {0, 8, -1, -1, 8, -1, -1, 8, 8}, 
                     {2, -1, -1, -1, -1, 6, -1, -1, -1}, 
                     {1, 1, 1, 4, 4, 7, 7, 7, -1}, 
                     {3, 4, 3, -1, -1, -1, -1, -1, -1}, 
                     {-1, 5, -1, -1, 5, -1, -1, -1, -1} 
                   }; 
        int state = 0;
        while(*s)
        {
            int in = getInput(s);
            if (in < 0) return false;
            state = fsm[in][state];
            if (state < 0) return false;
            s++;
        }
        return state == 1 || state == 4 || state == 7 || state == 8;
    }
   
    // Space(0), Sign(1), Digit(2), Dot(3), Exp(4), Else(-1); 
    int getInput(const char *s) {
        int out = -1;
        switch (*s) {
            case ' ': return 0;
            case '+':
            case '-': return 1;
            case '.': return 3;
            case 'e': return 4;
        }
       
        if (*s >='0' && *s <='9') return 2;
       
        return -1;
    }
};

Thursday, November 20, 2014

Wildcard Matching

Wildcard Matching
Implement wildcard pattern matching with support for '?' and '*'.
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

 
// Solution 1
class Solution {
public:
    bool isMatch( const char *s, const char *p) {
       while(*s && *p != '*') {
           if (*s != *p && *p != '?') return false;
           s++;
           p++;
       }
      
       const char *ps = NULL;
       const char *pp = NULL;
       while(*s) {
           if (*p == '*') {
               if (!*++p) return true;
               ps = s;
               pp = p;
           }
           else if (*s == *p || *p== '?') {
               s++; p++;
           }
           else {
               s = ++ps;
               p = pp;
           }
       }
      
       while(*p == '*') p++;
      
       return !*p;
    }
};

 


// Solution 2 similar to 1 but a little more concise
 bool isMatch( const char *s, const char *p) {
        const char *ps = NULL;
        const char *pp = NULL;
       
        while(*s) {
            if (*p == '*') {
                if (!*++p)  return true;
                ps = s + 1;
                pp = p;
            }
            else if (*s == *p || *p == '?') {
                s++;
                p++;
            }
            else if (ps)
            {
               s = ps++;
               p = pp;
            }
            else return false;
        }
       
        while(*p == '*') p++;
       
        return !*p;
    }

Tuesday, November 11, 2014

Binary Tree Postorder Traversal

 
 
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  /*
  class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root) {
      vector<int> output;
      if (!root) return output;
       
       TreeNode *prev = NULL;   
       stack<TreeNode *> st;
       st.push(root);
       while(!st.empty())
       {
           TreeNode *cur = st.top();
           
           if (prev == NULL || prev->left == cur || prev->right == cur)
           {
               if (cur->left) {
                    st.push(cur->left);
                  } else if (cur->right) {
                    st.push(cur->right);
                  } else {
                     output.push_back(cur->val);
                    st.pop();
                  }
           }
           else if (cur->right == prev) {
               st.pop();
               output.push_back(cur->val);
              
           }
           else if (cur->left == prev) {
               if (cur->right) {
                   st.push(cur->right);
               }
               else {
                   st.pop();
                   output.push_back(cur->val);
                   
               }
           }
            prev = cur;
       }
       
       return output;
    }
};
*/

    /*Method 1
    vector<int> postorderTraversal(TreeNode *root) {
      vector<int> output;
      if (!root) return output;
       
       TreeNode *prev = NULL;   
       stack<TreeNode *> st;
       st.push(root);
       while(!st.empty())
       {
           TreeNode *cur = st.top();
           if (!cur->left && !cur->right) {
               output.push_back(cur->val);
               st.pop();
           }
           if (cur->right) {
              st.push(cur->right);
              cur->right= NULL;
           }
           if (cur->left) {
              st.push(cur->left);
              cur->left = NULL;
           }
       }
       
       return output;
    } 
    
    // Method 2
    vector<int> postorderTraversal(TreeNode *root) {
      vector<int> output;
      if (!root) return output;
       
       TreeNode *prev = NULL;   
       stack<TreeNode *> st;
       stack<TreeNode *> st2;
       st.push(root);
       while(!st.empty())
       {
           TreeNode *cur = st.top();
           st.pop();
           st2.push(cur);
           if (cur->left) 
              st.push(cur->left);
           if (cur->right)
              st.push(cur->right);
       }
       
       while(!st2.empty()){
           TreeNode *cur = st2.top();
           st2.pop();
           output.push_back(cur->val);
       }
       return output;
    }
    
    // Method 3
    vector<int> postorderTraversal(TreeNode *root) {
      vector<int> output;
       stack<TreeNode *> st;
       while(!st.empty() || root)
       {
           if (!root)
           {
              while(!st.empty() && root==st.top()->right)
              {
                  root= st.top();
                  st.pop();
                  output.push_back(root->val);
              } 
              root= st.empty()? NULL : st.top()->right;
           }
           else 
           {
               st.push(root);
               root = root->left; 
           }
       }
       
       return output;
    }
    */
    
    // Simple coder's solution
    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> output;
        stack<TreeNode*> st;
      
        TreeNode *prev = NULL;  
        pushLeft(root, st);
        while (!st.empty()) {
            root = st.top();
            if (prev == root->left && root->right)
            {
               pushLeft(root->right, st);
               prev = NULL;
            }
            else
            {
                output.push_back(root->val);
                st.pop();
                prev = root;
            }
        }

        return output;
    }
    
   void pushLeft(TreeNode *root, stack<TreeNode *> &st)
   {
       while(root) {
           st.push(root);
           root = root->left;
       }
   }
};

Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization: Nodes are labeled uniquely.
We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.
  1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
  2. Second node is labeled as 1. Connect node 1 to node 2.
  3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:
       1
      / \
     /   \
    0 --- 2
         / \
         \_/ 

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (!node) return NULL;
       
        unordered_map<UndirectedGraphNode *, UndirectedGraphNode *> map;
        queue<UndirectedGraphNode *> que;
        que.push(node);
        map[node] = new UndirectedGraphNode(node->label);
        while(!que.empty()) {
            UndirectedGraphNode *current = que.front();
            que.pop();
           
            for(auto iter : current->neighbors) {
                if (map.find(iter) == map.end()) {
                    map[iter] = new UndirectedGraphNode(iter->label);
                    que.push(iter);
                }


                map[current]->neighbors.push_back(map[iter]);
            }
        }
        return map[node];
    }
};
 
class Solution {
public:
    void BFS(UndirectedGraphNode *node, unordered_map<UndirectedGraphNode *, UndirectedGraphNode *> &map)
    { 
        if (map[node]) return;         map[node] = new UndirectedGraphNode(node->label);
        
        for(UndirectedGraphNode *child : node->neighbors)
            BFS(child, map);
    }
    
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (!node) return NULL;
        unordered_map<UndirectedGraphNode *, UndirectedGraphNode *> map;
        BFS(node, map); 
        
        for(auto iter:map)
            for(UndirectedGraphNode *child : iter.first->neighbors)
                iter.second->neighbors.push_back(map[child]);
        
        return map[node];
    }
};
 
class Solution {
public:
    UndirectedGraphNode *DFS(UndirectedGraphNode *node, unordered_map<UndirectedGraphNode *, UndirectedGraphNode *> &map)
    { 
        if (map[node]) return map[node]; 
        
        UndirectedGraphNode *nn = new UndirectedGraphNode(node->label);
        map[node] = nn;
        
        for(UndirectedGraphNode *child : node->neighbors)
            nn->neighbors.push_back(DFS(child, map));
            
        return nn;
    }
    
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (!node) return NULL;
        unordered_map<UndirectedGraphNode *, UndirectedGraphNode *> map;
        return DFS(node, map); 
    }
};

Sunday, November 9, 2014

String to Integer (atoi)

Implement atoi to convert a string to an integer.
Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.
Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Requirements for atoi:
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

 
 
class Solution {
public:
    int atoi(const char *str) {
        while(*str && *str == ' ') str++;
        int sign = 1;
        if (*str == '+' || *str=='-') {
            sign = *str == '+'? 1 : -1;
            str++;
        }
       
        long val = 0;
        while(*str >= '0' && *str <='9') {
           if (sign == 1 && ((*str >= '8' && val == INT_MAX/10) || val > INT_MAX/10) ) return INT_MAX;
           if (sign == -1 && ((*str >= '8' && val == INT_MAX/10) || val > INT_MAX/10) ) return INT_MIN;
          
           val = val *10 + *str -'0';
           str++;
        }
       
        val *=sign;
        return val;
    }
};

Saturday, November 8, 2014

ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P   A   H   N
A P L S I I G
Y   I   R
And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:
string convert(string text, int nRows);
convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

 
class Solution {
public:
    string convert(string s, int nRows) {
        if (nRows < 2) return s;
        int n = s.length();
        int groupLen = 2*nRows-2;
        int groups = 1 + n / groupLen;
         
        string output;
        for(int i = 0; i < nRows; i++)
        {
            for(int j = 0; j < groups; j++ )
            {
                if (i == 0 || i == nRows-1)
                {
                    if (j * groupLen + i <n)
                       output.push_back(s[j * groupLen + i]);
                }
                else {
                    if (j * groupLen + i <n)
                       output.push_back(s[j * groupLen + i]);
                    if ((j+1) * groupLen - i <n)
                       output.push_back(s[(j+1) * groupLen - i]);
                }
            }
        }
        return output;
    }
};

class Solution {
public:
    string convert(string s, int nRows) {
        if (nRows < 2) return s;
       
        vector<string> map(nRows, "");
        int groupLen = 2*nRows-2;
       
        for(int i = 0; i < s.length(); i++)
        {
            int index = i % groupLen;
            if (index <nRows)
               map[index].push_back(s[i]);
            else
               map[groupLen-index].push_back(s[i]);
        }
       
        string output = "";
        for(string str:map)
           output += str;
        return output;
    }
};

StrStr: Find substring by using KMP algorithm

 
// http://www.mitbbs.com/article_t/JobHunting/32823417.html
// http://www.matrix67.com/blog/archives/115
class Solution {
public:
    vector<int> KMPpreprocessing(char *needle) {
         int m = strlen(needle);
         // assume j = match[i]: needle[i-j:i] == needle[0:j]
         vector<int> match(m,-1);
         int j = -1;
         for(int i=1; i<m; i++) {
             while(j>=0 && needle[i]!=needle[j+1]) j = match[j];
             if(needle[i]==needle[j+1]) j++;
             match[i] = j;
         }
         return match;
     }

     int strStr(char *haystack, char *needle) {
         if(!*needle) return 0;
         if(!*haystack) return -1;  
         int n = strlen(haystack);
         int m = strlen(needle);
         vector<int> match = KMPpreprocessing(needle);
         int j = -1;
         for(int i=0; i<n; i++) {
             while(j>=0 && haystack[i]!=needle[j+1]) j = match[j];
             if(haystack[i]==needle[j+1]) j++;
             if(j==m-1) return i-m+1;
         }
         return -1;
     }
};

Thursday, November 6, 2014

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.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.

 
class Solution {
public:
    bool canJump(int A[], int n) {
        int current = 0;
        int reach = A[0];
       
        while(current <= reach) {
            if (reach >= n-1) return true;
            reach = max(reach, current+A[current]);
            current++;
        }
       
        return false;
    }
};