Leetcode: Combination in C++

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],
]

Solution: 
void helper(vector<vector<int> >& result,vector<int> current, int k, int n, int cur )
    {
        if(current.size()==k)
        {
            result.push_back(current);
            return;
        }
        for(int i=cur;i<=n;i++)
        {
            current.push_back(i);
            helper(result,current,k,n,i+1);
            current.pop_back();
        }
    }
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int> > result;
        vector<int> solution;  
        helper(result,solution, k,n,1);
        return result;
    }

Leetcode: Palindrome Number in C++

Determine whether an integer is a palindrome. Do this without extra space.

Some hints:

Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

Solution:

bool isPalindrome(int x) {
        if(x<0)
        return false;
        int digit = 1;
        int tmp = x;
        while(x/digit>=10)
        {
        digit*=10;
        }
        while(x!=0)
        {
            if(x%10!=x/digit)
            return false;
            else
            {
                x = x%digit;
                x = x/10;
                digit = digit/100;
            }
        }
        return true;
    }

Leetcode: Remove Duplicates from Sorted List II in Java

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.
Solution:  
public ListNode deleteDuplicates(ListNode head) {
        if(head == null)
        return head;
        ListNode root = new ListNode(0);
        ListNode cur = head;
        ListNode pre = root;
       
        while(cur!=null)
        {
            boolean isDup = false;
            while(cur.next!=null&&cur.val==cur.next.val)
            {
                isDup = true;
                cur = cur.next;
            }
            if(isDup)
            {
                cur = cur.next;
            }
            else
            {
                pre.next = cur;
                pre = cur;
                cur = cur.next;
                pre.next = null;
               
            }
        }
        return root.next;

Leetcode: Merge Sorted Array in C++

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 to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.
Solution:
void merge(int A[], int m, int B[], int n) {
        int pos = m+n-1;
        m = m-1;
        n = n-1;
        while(n>=0&&m>=0)
        {
            if(A[m]>B[n])
            {
                A[pos] = A[m];
                m--;
            }
            else
            {
                A[pos] = B[n];
                n--;
            }
            pos--;
        }
        if(n>=0)
        {
            while(n>=0)
            {
                A[pos] = B[n];
                pos--;
                n--;
            }
        }
    }

Leetcode: Decode Ways in C++

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,

Solution: 

int numDecodings(string s) {
         if(s.size() == 0)
            return 0;
        vector<int> ways(s.size() + 1,0);
        ways[s.size()] =1;
        for(int i = s.size() - 1; i >= 0; --i)
        {
            //one digit number
            if(s[i] == '0')
                ways[i] = 0;
            else
                ways[i] = ways[i+1];
            
            //two digit number
            if( i + 1 < s.size() && ((s[i] == '1' || (s[i] == '2' && s[i + 1] <= '6')))) {
                ways[i] += ways[i + 2];
            }
        }
        return ways[0];
    }

Leetcode: Binary Tree Inorder Traversal in C++

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iterative?

Solution: 

Recursive:

void inorder(TreeNode* root, vector<int>& result)
    {
        if(!root)
        return;
        inorder(root->left, result);
        result.push_back(root->val);
        inorder(root->right, result);
    }
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> result;
        inorder(root, result);
        return result;
    }
Iterative:


vector<int> inorderTraversal(TreeNode *root) {
        vector<int> result;
        if(!root)
        return result;
        stack<TreeNode*> treestack;
        while(!treestack.empty()||root)
        {
            if(root)
            {
                treestack.push(root);
                root = root->left;
            }
            else
            {
                root = treestack.top();
                treestack.pop();
                result.push_back(root->val);
                root = root->right;
            }
        }
        return result;
    }

Leetcode: Unique Binary Search Trees II in C++

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Solution:

vector<TreeNode *> generate(int start, int end)
    {
        vector<TreeNode *> result;
        if(start>end)
        {
            result.push_back(NULL);
            return result;
        }
        for(int i=start;i<=end;i++)
        {
            vector<TreeNode *> leftsub = generate(start, i-1);
            vector<TreeNode *> rightsub = generate(i+1,end);
            for(int m=0;m<leftsub.size();m++)
            {
                for(int n=0;n<rightsub.size();n++)
                {
                    TreeNode* root = new TreeNode(i);
                    root->left = leftsub[m];
                    root->right = rightsub[n];
                    result.push_back(root);
                   
                }
            }
        }
        return result;
    }
    vector<TreeNode *> generateTrees(int n) {
        if(n==0)
        {
            vector<TreeNode *> result;
            result.push_back(NULL);
            return result;
        }
        return generate(1, n);
    }

Leetcode: Unique Binary Search Trees in C++

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Solution:
int numTrees(int n) {
        vector<int> count(n+1, 0);
        count[0] = 1;
        count[1] = 1;
        for(int i=2;i<=n;i++)
        {
            for(int j=0;j<i;j++)
            count[i] += count[j]*count[i-j-1];
        }
        return count[n];
    }

Leetcode: Plus One in C++

Given a number represented as an array of digits, plus one to the number.
Solution:
vector<int> plusOne(vector<int> &digits) {
        int carry = 0;
        int len = digits.size();
        vector<int> result(len+1,0);
        for(int i=0;i<digits.size();i++)
        {
                if(i==0)
                result[len-i] = digits[len-1-i] + 1 +carry;
                else
                result[len-i] = digits[len-1-i]+carry;
                if(result[len-i]==10)
                {
                carry = 1;
                result[len-i] = 0;
                }
                else
                carry = 0;
        }
        if(carry==1)
        result[0] =1;
        else
        result.erase(result.begin());
        return result;
    }

Leetcode: Reverse Linked List II in C++

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 <= m <= n <=length of list.

Solution: Learn from discuss in Leetcode. Great Method.
 ListNode *reverseBetween(ListNode *head, int m, int n) {
    ListNode dummy(0);
    dummy.next = head;

    ListNode *start, *pre = &dummy;
    for (int i = 1; i <= n; ++i) {
        if (i == m) start = pre;
        if (i > m && i <= n) {
            pre->next = head->next;
            head->next = start->next;
            start->next = head;
            head = pre;
        }
        pre = head;
        head = head->next;
    }
    return dummy.next;
    }

Leetcode: Interleaving String in C++

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,

Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbbaccc", return false.

When s3 = "aadbbcbcac", return true.

Solution: 

bool isInterleave(string s1, string s2, string s3) {
        int len1= s1.size();
        int len2 = s2.size();
        int len3 = s3.size();
        if(len1+len2!=len3)
        return false;
        vector<vector<bool> > match(len1+1, vector<bool>(len2+1,false));
        match[0][0] = true;
        for(int i = 0;i<len1;i++)
        {
            if(s1[i]==s3[i])
            match[i+1][0] = true;

            else
            break;

        }
        for(int i = 0;i<len2;i++)
        {
            if(s2[i]==s3[i])
            match[0][i+1] = true;
            else
            break;
        }
        for(int i = 1;i<=len1;i++)
        {
            char c1 = s1[i-1];
            for(int j = 1;j<=len2;j++)
            {
               char c2 = s2[j-1];
               char c3 = s3[i+j-1];
               if(c1==c3) // one situation is related to its previous one and current situation.
               match[i][j] = match[i-1][j]||match[i][j];
               if(c2==c3)
               match[i][j] = match[i][j-1]||match[i][j];
            }
        }
        return match[len1][len2];
    }

Leetcode: Validate Binary Search Tree in C++

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.

• The right subtree of a node contains only nodes with keys greater than the node's key.

• Both the left and right subtrees must also be binary search trees.

   bool isBST(TreeNode* root,int& prev)
    {
      if(root)
 {
if(!isBST(root->left,prev))
return false;
if(root->val<=prev)
return false;
                prev = root->val;
return isBST(root->right,prev);
 }
 return true;
    }
    bool isValidBST(TreeNode *root) 
    {
        int prev =  INT_MIN;
        return isBST(root, prev);
    }

Leetcode: Recover Binary Search Tree in C++

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

Recover the tree without changing its structure.

Solution:

void preorder(TreeNode *root, TreeNode*& pre, TreeNode*& t1, TreeNode*& t2)
    {
        if(!root)
        return;
        if(root->left)
        preorder(root->left, pre, t1, t2);
        if(pre&&pre->val>root->val)
        {
            t2 = root;
            if(!t1)
            t1 = pre;
        }
        pre = root;
        if(root->right)
        preorder(root->right, pre, t1, t2);
    }
    void recoverTree(TreeNode *root) {
        if(!root)
         return;
        TreeNode* tmp1 = NULL;
        TreeNode* tmp2 = NULL;
        TreeNode* pre = NULL;
        preorder(root, pre, tmp1, tmp2); 
        if(tmp1&&tmp2)
        swap(tmp1->val, tmp2->val);
    }

Leetcode: Symmetric Tree in C++

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

Solution: recursively 
bool helper(TreeNode *first, TreeNode* second)
    {
        if(!first&&!second)
        return true;
        else if(first&&second)
        {
            if(first->val!=second->val)
            return false;
            return helper(first->left,second->right)&&helper(first->right,second->left);
        }
        else
        return false;
    }
    bool isSymmetric(TreeNode *root) {
        if(!root)
        return true;
        return helper(root->left,root->right);
    }

Tripadvisor Interview: Specify Number in Array in C++

Giving an array, let you find the numbers which is larger than its previous numbers and smaller or equal than the numbers behind it. Then you can return a random number in the specified number array.

Requirements:1, Implement this question.2, Using O(n) time complexity.3, Using O(n) space complexity.

int specificNum(vector<int> arr)
{
vector<int> result;
vector<int> m_vec;
int max = INT_MIN;
for(int i=0;i<arr.size();i++)
{
if(arr[i]>max)
{
max = arr[i];
}
m_vec.push_back(max);
}
int min = INT_MAX;
for(int i=arr.size()-1;i>=1;i--)
{
if(arr[i]<min)
{
min = arr[i];
}
if(arr[i]>m_vec[i-1]&&arr[i]<=min)
result.push_back(arr[i]);
}
if(arr[0]<=min)
result.push_back(arr[0]);
 assert(result.size()==0);
int n = result.size();
srand (time(NULL));
int r_num = rand()%n;
return result[n];
}

Leetcode: Divide Two Integers in C++

Divide two integers without using multiplication, division and mod operator.Solution: O(log(a/b))
unsigned int unsigndivide(unsigned int dividend, unsigned int divisor, unsigned int& mod)
    {
        if(divisor == dividend)
        {
            mod = 0;
            return 1;
        }
        else if(divisor>dividend)
        {
            mod = dividend;
            return 0;
        }
        else
        {
            unsigned int addup = divisor+divisor;
            if(dividend>=addup)
            {
                unsigned int result1 = unsigndivide(dividend, addup, mod);
                unsigned int result2 = unsigndivide(mod, divisor, mod);
                return result1+result1+result2;
            }
            else
            {
                mod = dividend - divisor;
                return 1;
            }
        }
    }
    int divide(int dividend, int divisor) {
        bool flag = false;
        if((dividend>0&&divisor<0)||(dividend<0&&divisor>0))
          flag = true;
        unsigned int abs_dividend=abs(dividend);
        unsigned int abs_divisor =abs(divisor);
        unsigned int mod =0;
        unsigned int result = unsigndivide(abs_dividend, abs_divisor, mod);
        if(flag)
        return 0-result;
        return result;
    }

Leetcode/Google onsite: Binary Tree Zigzag Level Order Traversal in C++

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:

Given binary tree {3,9,20,#,#,15,7},
  3
  / \
 9 20
 / \
15 7
Return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]

Solution:
vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
        vector<vector<int> > result;
        if(!root)
        return result;
        stack<TreeNode*> s1,s2,s3;
        s1.push(root);
        TreeNode *tmp;
        int level =0;
        while(!s1.empty())
        {
            tmp = s1.top();
            if(result.size()==level)
            {
              vector<int> tmpvec;
              tmpvec.push_back(tmp->val);
              result.push_back(tmpvec);
            }
            else
              result[level].push_back(tmp->val);
            s1.pop();
            if(level%2==0) //odd level
            {
              if(tmp->left)
                s2.push(tmp->left);
              if(tmp->right)
                s2.push(tmp->right);
            }
            else   //even level
            {
              if(tmp->right)
                s2.push(tmp->right);
              if(tmp->left)
                s2.push(tmp->left);
            }
            if(s1.empty())  //after one level
            {
                s1 = s2;
                s2 = s3;
                level++;
            }
        }
        return result;
}

Leetcode: Binary Tree Level Order Traversal in C++

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

Solution: 
void helper(TreeNode *root, int level, vector<vector<int> >& result)
    {
        if(!root)
            return;
        if(result.size()==level)
        {
            vector<int> tmp;
            tmp.push_back(root->val);
            result.push_back(tmp);
        }
        else
           result[level].push_back(root->val);
        if(root->left)
           helper(root->left, level+1, result);
        if(root->right)
           helper(root->right, level+1, result);
    }
    vector<vector<int> > levelOrder(TreeNode *root) {
        vector<vector<int> > result;
        if(!root)
        return result;
        helper(root, 0, result);
        return result;
    }

Leetcode: Sort Colors in C++

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.
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.

Follow up:

Could you come up with an one-pass algorithm using only constant space?

Solution:

void sortColors(int A[], int n) {

        int pos0 = 0;
        int pos2 = n-1;
        int cur = 0;
        while(cur<=pos2)
        {  
            if(A[cur]==0)
            {
                swap(A[pos0],A[cur]);
                pos0++;
                cur++; // the way we do it here is because the element must be 1. Because if it is 2. we already put it into the end.
            }
            else if(A[cur]==2)
            {
                swap(A[pos2],A[cur]);
                pos2--;
            }
            else
                cur++;
        }
        
    }

Leetcode: Same Tree in C++

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Solution: 

bool isSameTree(TreeNode *p, TreeNode *q) {
         if(!p&&!q)
         return true;
         else if(!p||!q)
         return false;
         else
         {
            if(p->val==q->val)
            {
               return isSameTree(p->left, q->left)&&isSameTree(p->right, q->right);
               
            }
            else
                return false;
         }
    }

Leetcode: Convert Sorted List to Binary Search Tree in C++

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Solution:
TreeNode *ToBST(ListNode *& current,int start, int end)
    {
        if(start>end)
        return NULL;
        int mid = start + (end-start)/2;
        TreeNode* left = ToBST(current,start,mid-1);
        TreeNode* n1 =  new TreeNode(current->val);
        n1->left = left;
        current = current->next;
        n1->right = ToBST(current,mid+1,end);
        return n1;
    }
    TreeNode *sortedListToBST(ListNode *head) {
        if(!head)
        return NULL;
        ListNode* p = head;
        int count =0;
        while(p)
        {
            count++;
            p = p->next;
        }
        return ToBST(head,0,count-1);
        
    }