Category Archives: Coding

Leetcode: Subsets II (also work with no dups)

Posted on by

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

Posted on by

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

Posted on by

不是最快的，但是很简单
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

Posted on by

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

Posted on by

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

Posted on by

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

Posted on by

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

Leetcode: Container With Most Water

Posted on by

public class Solution {
    public int maxArea(int[] height) {
        int i=0,j=height.length-1;
        int result=0;
        while(i<j){
            if(result<Math.min(height[i],height[j])*(j-i)){
                result=Math.min(height[i],height[j])*(j-i);
            }
            if(height[i]<height[j])i++;else j--;
        }
        return result;
    }
}

Leetcode: First Missing Positive

Posted on by

public class Solution {
    public int firstMissingPositive(int[] A) {
        for(int i=0;i<A.length;i++){
            while(A[i]-1>=0&&A[i]<=A.length&&A[A[i]-1]!=A[i]){
                int t=A[i];
                int temp=A[t-1];
                A[t-1]=A[i];
                A[i]=temp;
            }
        }
        int i=0;
        for(i=0;i<A.length;i++){
            if(i+1!=A[i])break;
        }
        return i+1;
    }
}

Leetcode: Jump Game

Posted on by

    public boolean canJump(int[] A) {
        int i=A.length-1;
        while(i>0){
            int j=0;
            boolean hasNext=false;    
            for(j=0;j<i;j++){
                if(A[j]+j>=i){
                    i=j;
                    hasNext=true;
                    break;
                }
            }
            if(!hasNext)return false;
        }
        return true;
    }