My life

Month: April 2013

  • Leetcode: Add Binary

    public class Solution {
        public String addBinary(String a, String b) {
            StringBuilder sb=new StringBuilder();
            int i=a.length()-1,j=b.length()-1;
            boolean carry=false;
            while(i>=0||j>=0){
                if((i<0||a.charAt(i)=='0')&&(j<0||b.charAt(j)=='0')){
                    if(carry)sb.insert(0,'1');
                    else sb.insert(0,'0');
                    carry=false;
                }else if(i>=0&&j>=0&&a.charAt(i)=='1'&&b.charAt(j)=='1'){
                    if(carry)sb.insert(0,'1');
                    else sb.insert(0,'0');
                    carry=true;
                }else{
                    if(carry)sb.insert(0,'0');
                    else sb.insert(0,'1');
                }
                i--;j--;
            }
            if(carry)
                sb.insert(0,'1');
            return sb.toString();
        }
    }

  • Leetcode: Minimum Window Substring

    public class Solution {
        public String minWindow(String S, String T) {
            HashMap<Character,Integer>needToFind=new HashMap<Character,Integer>();
            for(char c:T.toCharArray()){
                if(needToFind.containsKey(c)){
                    needToFind.put(c,needToFind.get(c)+1);
                }else{
                    needToFind.put(c,1);
                }
            }
            int found=0;
            int min=Integer.MAX_VALUE;
            int rstart=0,rend=0;
            HashMap<Character,Integer>foundMap=new HashMap<Character,Integer>();
            int begin=0;
            for(int end=0;end<S.length();end++){
                char c=S.charAt(end);
                if(!needToFind.containsKey(c))continue;
                if(foundMap.containsKey(c)){
                    foundMap.put(c,foundMap.get(c)+1);
                }else{
                    foundMap.put(c,1);
                }
                if(foundMap.get(c)<=needToFind.get(c))
                    found++;
                if(found==T.length()){
                    c=S.charAt(begin);
                    while(!needToFind.containsKey(c)||
                        foundMap.get(c)>needToFind.get(c)){
                        if(needToFind.containsKey(c)){
                            foundMap.put(c,foundMap.get(c)-1);
                        }
                        begin++;
                        c=S.charAt(begin);
                    }
                    if(min>end-begin){
                        min=end-begin;
                        rstart=begin;
                        rend=end;
                    }
                }
               
            }
            if(found==T.length())return S.substring(rstart,rend+1);
            return "";
        }
    }

  • Leetcode: remove duplicates from sorted array II

    public class Solution {
        public int removeDuplicates(int[] A) {
            if (A.length == 0) return 0;
            int len = 1;
            int dup = 1;
            for(int i = 1; i < A.length; i++) {
                if(A[i] != A[len - 1]) {
                    A[len++] = A[i];
                    dup=1;
                // dup less than the max allow here, 1 mean no dup allow
                } else if (dup<2) {
                    A[len++] = A[i];
                    dup ++;
                }
            }
            return len;
        }
    }

  • Leetcode: Subsets II (also work with no dups)

    public class Solution {
        public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] S) {
            // Sort first
            Arrays.sort(S);

            ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
            // create a boolean array to track progress
            boolean[] b = new boolean[S.length];
            while (true) {
                // output a good subset
                result.add(getR(b, S));
                int i = 0;
                while (i < S.length) {
                    if (b[i] == false) {
                        // if current position is false, just market it true and break;
                        b[i] = true;
                        break;
                    } else {
                        // see if next position has same character
                        int k=i+1;
                        while(k<S.length&&S[k]==S[i]&&b[k]==true){
                            k++;
                        }
                        if(k==S.length){
                            // reach the end, break;
                            i=k;
                            break;
                        }
                        if(S[k]==S[i]){
                            // found a dup character that has false, just mark it true and break;
                            b[k]=true;
                            break;
                        }else{
                            // all same dup is true, mark everything false and go on
                            while(i<k){
                                b[i] = false;
                                i++;
                            }
                        }
                    }
                }
                if (i == S.length)
                    break;
            }
            return result;
        }
       
        public ArrayList<Integer> getR(boolean[]b,int[]S) {
            ArrayList<Integer> r=new ArrayList<Integer>();
            for(int i=0;i<b.length;i++){
                if(b[i])r.add(S[i]);
            }
            return r;
        }
    }

  • Leetcode: Scramble String

    public class Solution {
        public boolean isScramble(String s1, String s2) {
            if(s1.length()!=s2.length())return false;
            int x1=0,x2=0;
            for(char c:s1.toCharArray()){
                x1=x1^(int)c;
            }
            for(char c:s2.toCharArray()){
                x2=x2^(int)c;
            }
            if(x1!=x2)return false;
           
            if(s1.length()==1)return s1.equals(s2);
           
            for(int i=1;i<s1.length();i++){
                if((isScramble(s1.substring(0,i),s2.substring(0,i))&&
                    isScramble(s1.substring(i),s2.substring(i)))||
                    (isScramble(s1.substring(0,i),s2.substring(s2.length()-i))&&
                    isScramble(s1.substring(i),s2.substring(0,s2.length()-i))))
                        return true;
            }
            return false;
        }
    }

  • Leetcode: Search a 2D Matrix

    不是最快的，但是很简单
    public class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            int i=matrix.length-1;
            int j=0;
            while(i>=0&&j<matrix[0].length){
                if(matrix[i][j]>target)i--;
                else if(target>matrix[i][j])j++;
                else return true;
            }
            return false;
        }
    }

  • Leetcode Combinations

    public class Solution {
        public ArrayList<ArrayList<Integer>> combine(int n, int k) {
            return combine(1,n+1,k);
        }
       
        public ArrayList<ArrayList<Integer>> combine(int low,int upper, int k) {
            ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>> ();
            if(k==1) {
                for(int i=low;i<upper;i++){
                    ArrayList<Integer>r=new ArrayList<Integer>();
                    r.add(i);
                    result.add(r);
                }            
                return result;
            }
            for(int i=low;i<upper;i++){
                ArrayList<ArrayList<Integer>>r=combine(i+1,upper,k-1);
                for(ArrayList<Integer> a:r){
                    a.add(0,i);
                }
                result.addAll(r);
            }
            return result;
        }
    }

  • Leetcode Permutations

    Using linked list:

    public class Solution {
        public ArrayList<ArrayList<Integer>> permute(int[] num) {
            // if need to be unique, sort it first
            // Arrays.sort(num);
            LinkedList<Integer>l=new LinkedList<Integer>();
            for(int i:num){
                l.add(i);
            }
            return permute(l);
        }
       
        public ArrayList<ArrayList<Integer>> permute(LinkedList<Integer>l) {
            ArrayList<ArrayList<Integer>>result=new ArrayList<ArrayList<Integer>>();
           
            if(l.size()==0)return result;
            if(l.size()==1){
                ArrayList<Integer> n=new ArrayList<Integer>();
                n.add(l.get(0));
                result.add(n);
                return result;
            }
            for(int i=0;i<l.size();i++){
                // create a new array without i
                int current=l.get(i);
                // if need to be unique, add following line:
                // if(i>0&&current==l.get(i-1))continue;
                l.remove(i);
               
                ArrayList<ArrayList<Integer>>tresult=permute(l);
               
                for(ArrayList<Integer>rr:tresult){
                    rr.add(0,current);
                }
                result.addAll(tresult);
                l.add(i,current);
            }
            return result;
        }
    }

    Just use array:
        public ArrayList<ArrayList<Integer>> permute(int[] num) {
            // Start typing your Java solution below
            // DO NOT write main() function
            ArrayList<ArrayList<Integer>>result=new ArrayList<ArrayList<Integer>>();
           
            if(num.length==0)return result;
            if(num.length==1){
                ArrayList<Integer> n=new ArrayList<Integer>();
                n.add(num[0]);
                result.add(n);
                return result;
            }
            for(int i=0;i<num.length;i++){
                // create a new array without i
                int[]newnum=new int[num.length-1];
                int j=0;
                while(j<newnum.length){
                    newnum[j]=num[j<i?j:j+1];
                    j++;
                }
                ArrayList<ArrayList<Integer>>tresult=permute(newnum);
               
                for(ArrayList<Integer>rr:tresult){
                    rr.add(0,num[i]);
                }
                result.addAll(tresult);
            }
            return result;
        }

  • LeetCode: Interleaving String

    public class Solution {
        public boolean isInterleave(String s1, String s2, String s3) {
            if(s1.length()+s2.length()!=s3.length())return false;
            boolean[][]c=new boolean[s1.length()+1][s2.length()+1];
            c[0][0]=true;
            for(int i=0;i<s1.length();i++){
                if(s1.charAt(i)==s3.charAt(i))
                    c[i+1][0]=true;
                else break;
            }
            for(int i=0;i<s2.length();i++){
                if(s2.charAt(i)==s3.charAt(i))
                    c[0][i+1]=true;
                else break;
            }
            for(int i=1;i<s1.length()+1;i++){
                for(int j=1;j<s2.length()+1;j++){
                    char c3=s3.charAt(i+j-1);
                    if(s1.charAt(i-1)==c3){
                        c[i][j]=c[i-1][j];
                    }
                    if(s2.charAt(j-1)==c3){
                        c[i][j]=c[i][j-1]||c[i][j];
                    }
                }
            }
            return c[s1.length()][s2.length()];
        }
    }

  • Leetcode: Regular Expression Matching

    public class Solution {
        public boolean isMatch(String s, String p) {
            //simple match
            if(p.length()==0&&s.length()>0)return false;
            if(p.length()==0&&s.length()==0)return true;
            if(s.length()==0){
                if(p.length()>1&&p.charAt(1)=='*')
                    return isMatch(s,p.substring(2));
                else return false;
            }

            // p and s must has length great than 0 from here  
            if(p.length()==1){
                if(p.charAt(0)==s.charAt(0)||p.charAt(0)=='.')
                    return isMatch(s.substring(1),p.substring(1));
                else return false;
            }else{
                if(p.charAt(1)=='*'){
                    if(p.charAt(0)==s.charAt(0)||p.charAt(0)=='.')
                        return isMatch(s.substring(1),p.substring(0))||
                            isMatch(s.substring(0),p.substring(2));
                    else
                        return isMatch(s.substring(0),p.substring(2));
                }else{
                    if(p.charAt(0)==s.charAt(0)||p.charAt(0)=='.')
                        return isMatch(s.substring(1),p.substring(1));
                    else return false;
                }
            }
        }
    }