Sunday, August 23, 2015

Different Ways to Add Parentheses -- Leetcode

Question:
Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +,- and *.
Example 1

Input: "2-1-1".
((2-1)-1) = 0
(2-(1-1)) = 2
Output: [0, 2]
Example 2
Input: "2*3-4*5"
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
Output: [-34, -14, -10, -10, 10]
https://leetcode.com/problems/different-ways-to-add-parentheses/
Answer:

public class Solution {
    public Integer compute(Integer a, Integer b, char op){
        if(op=='+') return a+b;
        else if(op=='-')return a-b;
        else if(op=='*')return a*b;
        return 0;
    }
   
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> res = new ArrayList<Integer>();
        int len = input.length();
       
        if(Character.isDigit(input.charAt(0))){
                int i=0;
                int number = input.charAt(i) - '0';
                while(i+1<len && Character.isDigit(input.charAt(++i))){
                    number = number*10 + input.charAt(i)-'0';
                }
                      //edge case for recusrion, input is just a number, no operator.
                if(i==len-1){
                    res.add(number);
                    return res;
                }
        }
   
           //recursion dp, res(i,j) = res(i,k) op res(k+2,j), op = input[k+1].
        for(int k=0;k<len;++k){
             if(Character.isDigit(input.charAt(k)) == false){
                 List<Integer> left = new ArrayList<Integer>();
                 List<Integer> right = new ArrayList<Integer>();
               
                 left = diffWaysToCompute(input.substring(0,k));
                 right = diffWaysToCompute(input.substring(k+1));
               
                 for(int i=0;i<left.size();++i){
                     for(int j=0;j<right.size();++j){
                         char op = input.charAt(k);
                         Integer subres = compute(left.get(i), right.get(j), op);
                         res.add(subres);
                     }
                 }
             }
        }
        return res;
    }
}

Basic Calculator -- Leetcode

Question:
Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .
You may assume that the given expression is always valid.
Some examples:
"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23
Note: Do not use the eval built-in library function.
Answer:
public class Solution {  
    // "1 + 1 = 2"  
    public int calculate(String s) {  
        if(s==null || s.length() == 0) return 0;  
        
        int res = 0;
        int sign = 1;
        int len = s.length();
        Stack<Integer> stack = new Stack<Integer>();
        
        for(int i=0;i<len;++i){
            char c = s.charAt(i);
            if(Character.isDigit(c)){
                       //calculate number here.
               int number = 0;
               number = c-'0';
               while(i+1<len && Character.isDigit(s.charAt(i+1))){
                   number = number*10 + s.charAt(++i) - '0';
               }
               res = res + sign * number;
            }
            else if(c=='+'){
               sign = 1;
            }
            else if(c=='-'){
               sign = -1;
            }
            else if(c=='('){
                stack.push(res);
                stack.push(sign);
                       //recalculate in the '(xxx)' wrapper now.
                res=0;
                sign=1;
            }
            else if(c==')'){
                if(stack.empty()==false){
                    sign = stack.pop();
                }
                if(stack.empty()==false){
                    res = stack.pop() + sign * res;
                }
            }
        }
        return res;
    }  
} 

Basic Calculator II -- Leetcode

Question:
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.
You may assume that the given expression is always valid.
Some examples:
"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5
Note: Do not use the eval built-in library function.
Answer:
[java]

public class Solution {
    //"3+2*2=7
    public int calculate(String s) {
        if(s==null || s.length() == 0) return 0;

        int len = s.length();
        int res = 0, sign = 1, term = 1, number = 0;
        char op ='+';
        Stack<Integer> stack = new Stack<Integer>();
     
        for(int i=0;i<len;++i){
            char c = s.charAt(i);
            if(Character.isDigit(c)){
                //calculate number for current operand.
               number = c-'0';
               while(i+1<len && Character.isDigit(s.charAt(i+1))){
                   number = number*10 + s.charAt(++i) - '0';
               }
             
               if(op=='+' || op=='-'){
                   term = number;
               }
               else if(op=='*'){
                   term *= number;
               }
               else if(op=='/'){
                   term /= number;
               }
            }
            else if(c=='+'){
                res = res + sign * term;
                op = '+';
                sign = 1;
            }
            else if(c=='-'){
                res = res + sign * term;
                op='-';
                sign = -1;
            }
            else if(c=='*'){
                op = '*';
            }
            else if(c=='/'){
                op = '/';
            }
        }
        //calculate for the final res at last step.
        res = res + sign * term;
        return res;
    }
}


[C++]
class Solution { public: int calculate(string s) { istringstream in(s + "+"); long long total = 0, term, sign = 1, n; in >> term; char op; while (in >> op) { if (op == '+' || op == '-') { total += sign * term; sign = 44 - op; //op == '+' ? 1 : -1 in >> term; } 
else { in >> n; if (op == '*') term *= n; else term /= n; } } return total; } };

Friday, July 24, 2015

Merge K Sorted Lists -- Leetcode

Question:
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Answer:
Using Heap.
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
private:
    struct cmp{
        bool operator()(ListNode* lhs, ListNode *rhs){
            if(lhs->val < rhs->val) return false;
            else return true;
        }
    };
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        int K = lists.size();
        if (K == 0) return NULL;
        else if (K == 1) return lists[0];
         
        ListNode *listHead(NULL), *listRear(NULL);
        ListNode *node(NULL);
        priority_queue<ListNode*, vector<ListNode*>, cmp> h;
         
        // push K list heads into heap
        for(int i=0; i<K; ++i)
          if(lists[i] != NULL){
            h.push(lists[i]);
            lists[i] = lists[i]->next;
          }
             
        while(!h.empty()){
          //pop the min of k nodes
          node = h.top(); h.pop();
          if(node->next)
            h.push(node->next);
             
          //insert node into new list    
          if(listRear){
              listRear->next = node;
              listRear = listRear->next;
          }
          else{
              listHead = listRear = node;
          }
        }
         
        return listHead;
    }
};

Merge Sorted Array -- Leetcode

Question:
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1and nums2 are m and n respectively.
Answer:
class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
    int pos = m + n -1;
    while( m>0 && n>0)
    {
        if( A[m-1] < B[n-1])
        {
            A[pos] = B[n-1];
            pos--;
            n--;
        } 
        else
        {
            A[pos] = A[m-1];
            pos--;
            m--;
        }
    }
    while( n >0)
    {
        A[pos] = B[n-1];
        pos--;
        n--;
    }       
    }
};

Buffered Reader demo -- Java

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStream;
import java.io.InputStreamReader;

public class BufferedReaderDemo {
   public static void main(String[] args) throws Exception {
      
      InputStream is = null; 
      InputStreamReader isr = null;
      BufferedReader br = null;

      try{
         // open input stream test.txt for reading purpose.
         is = new FileInputStream("c:/test.txt");
         
         // create new input stream reader
         isr = new InputStreamReader(is);
         
         // create new buffered reader
         br = new BufferedReader(isr);
      
         // creates buffer
         char[] cbuf = new char[is.available()];
         
         // reads characters to buffer, offset 2, len 10
         br.read(cbuf, 2, 10);
         
         // for each character in the buffer
         for (char c:cbuf)
         {
            // if char is empty
            if(c == (char)0)
            {
               c='*';
            }
            // prints characters
            System.out.print(c);
         }
                  
      }catch(Exception e){
         e.printStackTrace();
      }finally{
         
         // releases resources associated with the streams
         if(is!=null)
            is.close();
         if(isr!=null)
            isr.close();
         if(br!=null)
            br.close();
      }
   }
}
Assuming we have a text file c:/test.txt, which has the following content. This file will be used as an input for our example program:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
Let us compile and run the above program, this will produce the following result:
**ABCDEFGHIJ**************

Thursday, July 23, 2015

permutations -- Leetcode

Question:
Given a collection of numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
Answer:
public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        ArrayList<Integer> subres = new  ArrayList<Integer>();
        ArrayList<Integer> num = new  ArrayList<Integer>();
        for(int i=0;i<nums.length;++i){
            num.add(nums[i]);
        }
        permuteRec(num,res,subres);
        return res;
    }
    public void permuteRec(ArrayList<Integer> nums, List<List<Integer>> res, List<Integer> subres){
        int len = nums.size();
        if(len ==0){
            //clone a new copy, then add!!!
            ArrayList<Integer> newcopy = new ArrayList<Integer>(subres);
            res.add(newcopy);
            return;
        }
        
        for(int i=0;i<len;++i){
            int n=nums.get(i);
            subres.add(n);
            nums.remove(i);
            permuteRec(nums,res,subres);
            //backtrack!!!
            nums.add(i,n);     //note: specific pos:i!!!
            subres.remove(subres.size()-1);
        }
        return;
    }
}