[Leetcode] Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

    string addBinary(string a, string b) {
        string ret;
        int i = a.size() - 1;
        int j = b.size() - 1;
        int carry = 0;
        while(i >= 0 || j >= 0 || carry > 0)
        {
            int da = i < a.size() ? a[i] - '0' : 0;
            int db = j < b.size() ? b[j] - '0': 0;
            //the value
            int d = (da + db + carry) % 2;
            //the carry
            carry = (da + db + carry) / 2;
            ret.insert(ret.begin(),1, d + '0');
            i--;
            j--;
        }
        
        return ret;
    }

[Leetcode] Plus One

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

vector<int> plusOne(vector<int> &digits) {
        
        int carry = 0;
        vector<int> nums;
        for(int i=digits.size()-1; i >=0; i--)
        {
            int one = i == digits.size()-1 ? 1 : 0;
            int d = (digits[i] + one + carry) % 10;
            carry =  (digits[i] + one + carry) / 10;
            nums.insert(nums.begin(), d);
        }
        //don't forget carry for case {9}
        if (carry > 0)
            nums.insert(nums.begin(), 1);
        
        return nums;
    }

[Leetcode] Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

<pre class="prettyprint linenums:1"><code class="language-cpp"> int sqrt(int x) { int b = 0; int e = x/2 + 1; while(b <= e) { long long mid= (b+e)/2; long long sl = mid * mid; long long sh = (mid+1) * (mid+1); if (sl <= x && sh > x) return mid; else if (sl < x) b = mid + 1; else e = mid - 1; } return -1; } </code></pre>

[Leetcode] Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

int climbStairs(int n) {
        vector<int> f(n+1,0);
        for(int i=0; i<=n; i++)
        {
            if (i == 0)
                f[i] = 1;
            else if (i == 1)
                f[i] = 1;
            else
                f[i] = f[i-1] + f[i-2];
        }
        return f[n];
    }

[Leetcode] Simplify Path

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

click to show corner cases.

Corner Cases:

• Did you consider the case where path = "/../"?
  In this case, you should return "/".
• Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
  In this case, you should ignore redundant slashes and return "/home/foo".

vector<string> splitPath(string path)
    {
        vector<string> ret;
        int i=0;
        while(i < path.size())
        {
            while(i < path.size() && path[i] != '/')
                i++;
            int j = i;
            i++;
            while(i < path.size() && path[i] != '/')
                i++;
                
            if (j != path.size())
                ret.push_back(path.substr(j+1, i-(j+1)));
        }
        return ret;
    }

    string simplifyPath(string path) {
        vector<string> paths = splitPath(path);
        stack<string> s;
        for(int i=0; i<paths.size(); i++)
        {
            //case: "/.."
            if (paths[i] == "..")
            {
                if (!s.empty())
                    s.pop();
            }
            //case: "////"
            else if (paths[i] != "." && paths[i].size() > 0)
                s.push(paths[i]);
        }
        
        string outPath;
        while(!s.empty())
        {
            string p = s.top();
            s.pop();
            outPath.insert(0, p);
            outPath.insert(0,"/");
        }
        
        if (outPath.size() == 0)
            outPath = "/";
            
        return outPath;
        
    }

[Leetcode] Set Matrix Zeroes

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

click to show follow up.

Follow up:

Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

void setZeroes(vector<vector<int> > &matrix) {
        //borrow first row and first column as the temporary storage to indicate whether this row/col need to be zeroed
        //use two flag to indicate whether first row/col need to be zeroed 
        bool firstRowZero = false;
        bool firstColZero = false;
        for(int i=0; i<matrix.size(); i++)
        {
            for(int j=0; j<matrix[0].size(); j++)
            {
                if (matrix[i][j] == 0)
                {
                    //0 in the first row
                    if (i == 0)
                        firstRowZero = true;
                    if (j == 0)
                        firstColZero = true;
                    //the col j should be zeroed    
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        
        //begin from 1 because first row/col can be zero only if firstRowZero is true
        for(int i=1; i<matrix.size(); i++)
        {
            if (matrix[i][0] == 0)
            {
                for(int j =0; j<matrix[0].size(); j++)
                    matrix[i][j] = 0;
            }
        }

        for(int i=1; i<matrix[0].size(); i++)
        {
            if (matrix[0][i] == 0)
            {
                for(int j =0; j<matrix.size(); j++)
                    matrix[j][i] = 0;
            }
        }
        
        //zero first row if necessary
        if (firstRowZero)
        {
            for(int i =0; i<matrix[0].size(); i++)
                matrix[0][i] = 0;
        }

        if (firstColZero)
        {
            for(int i =0; i<matrix.size(); i++)
                matrix[i][0] = 0;
        }
    }

[Leetcode] Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        int b = 0;
        int e = matrix.size() * matrix[0].size() - 1;
        while(b <= e)
        {
            //treat the whole matrix as a long array and do the binary search
            int m = (b+e)/2;
            int row = m / matrix[0].size();
            int col = m % matrix[0].size();
            if (matrix[row][col] == target)
                return true;
            else if (target < matrix[row][col])
                e = m - 1;
            else
                b = m + 1;
        }
        
        return false;
    }

[Leetcode] Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.

click to show follow up.

    void sortColors(int A[], int n) {
        int i = 0;
        int j = 0;
        int k = n-1;
        while(i <= k)
        {
            if (A[i] == 0)
            {
                //swap 0 with the first 1 so that all 0s are before 1s
                swap(A[i], A[j]);
                i++;
                j++;
            }
            else if (A[i] == 1)
            {
                //do nothing if it is 1
                i++;
            }
            else
            {
                //swap 2 with the last element which is not 2
                //note A[k] could be 2 as well so we should not move i forward
                swap(A[i], A[k]);
                k--;
            }
        }
    }

[Leetcode] Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

void dfs(vector<vector<int> >& ret, int n, int k, int m, vector<int>& nums)
{
 if (nums.size() == k)
 {
  ret.push_back(nums);
 }
 else
 {
  for (int i = m; i <= n; i++)
  {
   nums.push_back(i);
   dfs(ret, n, k, i + 1, nums);
   nums.pop_back();
  }
 }
}

vector<vector<int> > combine(int n, int k) {
 vector<vector<int> > ret;
 vector<int> nums;
 dfs(ret, n, k, 1, nums);

 return ret;
}

[Leetcode] Subsets

Given a set of distinct integers, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

void helper(vector<int> S, vector<vector<int> >& ret, vector<int>& tmp, int k)
    {
        ret.push_back(tmp);
        for(int i=k; i<S.size(); i++)
        {
            tmp.push_back(S[i]);
            helper(S, ret, tmp, i+1);
            tmp.pop_back();
        }
    }

    vector<vector<int> > subsets(vector<int> &S) {
        sort(S.begin(), S.end());
        vector<vector<int> > ret;
        vector<int> tmp;
        helper(S, ret, tmp, 0);
        
        return ret;
    }

[Leetcode] Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

    bool helper(vector<vector<char> > &board, string word, int i, int j, int k)
    {
        //if all char in the word has been found in the board
        if (k == word.size())
            return true;
        //if not the correct way    
        else if (i <0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] == '#' || word[k] != board[i][j])
            return false;
        else 
        {
            char tmp = board[i][j];
            board[i][j] = '#';
            //if andy of all its neighbors matches, we found a solution
            if (helper(board, word, i +1, j, k+1) ||
                helper(board, word, i, j+1, k+1) ||
                helper(board, word, i-1, j, k+1) ||
                helper(board, word, i, j-1, k+1))
                return true;
            //otherwise, backtrack
            board[i][j] = tmp;
            
            return false;            
        }

    }

    bool exist(vector<vector<char> > &board, string word) {
        for(int i=0; i<board.size(); i++)
        {
            for(int j=0; j<board[0].size(); j++)
            {
                //find a char in the board match the first char of the word
                if (board[i][j] == word[0])
                {
                    if (helper(board, word, i, j, 0))
                        return true;
                }
            }
        }
        
        return false;
    }

[leetcode] Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

    int removeDuplicates(int A[], int n) {
        if (n <= 2)
            return n;
        int j = 1;
        int count = 1;
        for(int i=1; i<n; i++)
        {
            //copy to the dest if current element is equal to previous element and count <= 2
            if (A[i] == A[i-1] && count < 2)
            {
                A[j++] = A[i];
                count++;
            }
            //or current element is not equal to previous element 
            else if (A[i] != A[i-1])
            {
                A[j++] = A[i];
                count = 1;
            }
        }
        
        return j;
    }

[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--];
        }
    }
};