Thursday, September 25, 2014

[Leetcode] Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,
    1
   / \
  2   3
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.
Analysis:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    
    void helper(TreeNode *root, int& sum, int s)
    {
        if (root == NULL)
            return;
        else if (root->left == NULL && root->right == NULL)
            sum += (s*10 + root->val);
        else
        {
            helper(root->left, sum, s*10 + root->val);
            helper(root->right, sum, s*10 + root->val);
        }    
    }
    
    int sumNumbers(TreeNode *root) {
        int sum = 0;
        helper(root, sum, 0);
        
        return sum;
    }
};


[Leetcode] Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
Analysis:

  • If s has only character, s could be break if s[0] is a word.
  • If s has two characters, s could be break if both s[0] and s[1] are the word or s.substr(0,2) is a word.
  • if s has If s has two characters, s could be break if there exist a j (0<=j<i) such that s.substr(0, j) could be break and s.substr(j, i-j+1) is a word. Notice that we only need to know whether  s.substr(0, j) could be break and don't care how it is break.

Let canBreak[i] to indicate whether s.substr(0,i) could be break


    bool wordBreak(string s, unordered_set<string> &dict) {
        //indicate whether the substr(s, 0, i) could be breaked into words
        vector<bool> canBreak(s.size(), false);
        for(int i=0; i<s.size(); i++)
        {
            //either the whole string is a word
            if(dict.find(s.substr(0, i+1)) != dict.end())
                canBreak[i] = true;
            else
            {
                //or substr1 can be breaked and substr2 is a word
                for(int j=0; j<i; j++)
                {
                    if (canBreak[j] && dict.find(s.substr(j+1, i-j)) != dict.end())
                    {
                        canBreak[i] = true;
                        break;
                    }
                }
            }
        }
        
        return canBreak[s.size()-1];
    }

Wednesday, September 24, 2014

[Leetcode] Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
Analysis:
If there are duplicate characters closed to current position than j, the substring without repeating characters should start from pos+1

    int lengthOfLongestSubstring(string s) {
        map<char, int> m;
        int j = 0;
        int maxLen = 0;
        for(int i=0; i<s.size(); i++)
        {
            if (m.find(s[i]) != m.end() && m[s[i]] >= j)
            {
                j = m[s[i]] + 1;
            }
            m[s[i]] = i;
            maxLen = max(maxLen, i-j+1);
        }
        return maxLen;
    }

[Leetcode] Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.
Analysis:
Let p be the product of all numbers in the array.
If p > 0, the largest product is p.
If p == 0, there must be at least one 0 in the array. The array should be something like [x1, 0, x2, 0, x3...], where x1, x2, x3 is a subarray containing no 0s. So, the largest product is maximum of largest product of x1, x2, x3 and 0. We can iterate the array and maintain the product of numbers and reset the product to be 1 when an 0 encountered. 
If p < 0, there must be odd number of negative elements.  The array should be something like [x1, -y1, x2, -y2, x3...], where x1, x2, x3 is a subarray containing no negative numbers. Since the number of negative element is odd in the array, product of x1 and product of [x2, -y2, x3, ...] must be positive and could be the potential largest product. Product of x1 could be calculated by iterating x1 and product of [x2, -y2, x3, ...] could be calculated by reverse iterating. 
Thus, the largest product must be the product of subarray between 0s (if there are 0s) and the left and right subarray of the negative elements. 

    int maxProduct(int A[], int n) {
        int maxProd = INT_MIN;
        int prod = 1;
        for(int i=0; i <n; i++)
        {
            prod = prod * A[i];
            maxProd = max(maxProd, prod);
            if (A[i] == 0)
                prod = 1;
        }
        
        prod = 1;
        for(int i=n-1; i >=0; i--)
        {
            prod = prod * A[i];
            maxProd = max(maxProd, prod);
            if (A[i] == 0)
                prod = 1;
        }
        
        return maxProd;
    }

Monday, September 22, 2014

[Leetcode] Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):
  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"
Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
Analysis:
From the example, we observed that the permutations can be divided into n groups, each beginning with degit 1 <=i <=n and the first digit must be i = k/(n-1)!
Similarly, the position of k in the group is k % (n-1)! and the remaining numbers are divided into n-1 groups and the first digit must be i = (k % (n-1)!)/(n-2)!.
Loop until all the numbers are set.

    string getPermutation(int n, int k) {
     vector<int> nums;
     //set an array with all numbers
     for (int i = 0; i<n; i++)
      nums.push_back(i + 1);
        
        //get (n-1)!
     int nn = 1;
     for (int i = 1; i < n; i++)
      nn = nn * i;
    
     string str;
     int kk = k - 1;
     while (n > 1)
     {
         //the kth permutation is at (k-1)/(n-1)! group
      int pos = kk / nn;
      str.push_back(nums[pos] + '0');
      //the number has been used, removed it from the array
      nums.erase(nums.begin() + pos);
      //the position in the group is at (k-1) % (n-1)!
      kk = kk % nn;
      //the number of permutations in the group is (n-2)!
      n = n - 1;
      nn = nn / n;
     }
     str.push_back(nums[0] + '0');
     return str;
    }

[Leetcode] Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.
Analysis:
  • Take the given example, we know the length of the list is 5 and the position to split the list is 3, then we can rotate the list by splitting the list between 3 and 4 and linking the tail and head of the list. The steps would be:

  1. Get the length of the list, l and the tail of the list tail
  2. Get the position p1 and p2 to split the list at l - k%l since k may be greater than l
  3. Get the new head by setting p1->next = NULL, tail->next = head and newhead = p2
  4. Note: if k%l == 0, simply return the head

ListNode *rotateRight(ListNode *head, int k) {
        if (head == NULL)
            return head;
        int len = 0;
        ListNode* curr = head;
        ListNode* tail = NULL;
        while(curr != NULL)
        {
            len++;
            tail = curr;
            curr = curr->next;
        }
        //Note:len could not be 0
        int pos = len - k % len;
        if (pos == len)
            return head;
        curr = head;
        ListNode* prev = NULL;
        for(int i=0; inext;
        }
        
        ListNode* newhead = curr;
        if (prev != NULL) {
            prev->next = NULL;
            tail->next = head;
        }
        
        return newhead;
    }

Sunday, September 21, 2014

[Leetcode] 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
Analysis:
Let f[i][j] be the minimum number of steps required to convert word1 of size i to word2 of size j. The last character of word1 may or may not be equal to the one of word2. 
Case1: considering word1 (Xa) and word2 (Ya). Since the last character of word1 is equal to the last character of word2, deleting the last character of both would not change the steps converting word1 to word2, that is, f[i][j] = f[i-1][j-1].
Case 2: Considering word1 (Xa) and word2 (Yb). Since last character of word1 is NOT equal to the last character of word2, to convert word1 to word2, there are 3 ways to convert word1 to word2 and the minimum one is the one we wanted:
  • Replace the character a with b of word1, so that word1(Xb) and word2(Yb). so the steps will become f[i][j] = f[i-1][j-1] + 1
  • Insert character b to word1, so that word1(Xab) and word2(Yb) and according to case1, so deleting b would make the steps become f[i][j] = f[i][j-1] + 1
  • Insert character a to word2, so that word1(Xb) and word2(Yba) and according to case1, so deleting a would make the steps become f[i][j] = f[i-1][j] + 1

We have f[i][j] = min(min(f[i][j-1], min(f[i-1][j]), f[i-1][j-1])
If word1 is empty, f[0][j] = j and if word2 is empty, f[i][0] = i
Given the above equation, it is pretty easy to have the code.  


    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        vector<vector<int> > f(m+1, vector<int>(n+1, 0));
        for(int i=0; i<=m; i++)
        {
            for(int j=0; j<=n; j++)
            {
                if (i == 0)
                    f[i][j] = j;
                else if (j == 0)
                    f[i][j] = i;
                else
                {
                    if (word1[i-1] == word2[j-1])
                        f[i][j] = f[i-1][j-1];
                    else
                        f[i][j] = min(min(f[i][j-1], f[i-1][j]), f[i-1][j-1]) + 1;
                }
            }
        }
        
        return f[m][n];
        
    }