My life

Category: Coding

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

  • Leetcode: Container With Most Water

    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

    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

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