LeetCode : Combination

public class Solution {
   
    public void reorg(int [] p, int x, int k)
    {
        int c=p[x]+1;
        for(int i=x+1;i<k;i++,c++)
           p[i]=c;
        return;
    }
   
    public ArrayList<ArrayList<Integer>> combine(int n, int k) {
       int p[]=new int[k];
       p[0]=1;
       reorg(p,0,k);
       int bound=n-k+2;
     
       ArrayList<ArrayList<Integer>> all=new ArrayList<ArrayList<Integer>>();
     
       int kk=k-1;
       while(p[0]<bound&&kk>=0)
       {
           ArrayList<Integer> al=new ArrayList<Integer>();
           for(int i=0;i<k;i++)
             al.add(i,p[i]);
           all.add(al);
         
           kk=k-1;
           boolean reorgflag=false;
           while(kk>=0)
           {
               p[kk]++;

               if(reorgflag){
                   reorg(p,kk,k);
                   reorgflag=false;
               }
                       
               if(p[kk]>n-k+1+kk)
               {
                   kk--;
                   reorgflag=true;
               }
               else break;
           }
       }

        return all;
    }
}

LeetCode : Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

**通常找max的題目, 元素中有負值的話，計算cost時，千萬不要把負值的部份也加進去。因為答案是可以選擇性不包括負值部份。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int calcmaxbranch(TreeNode root,HashMap<TreeNode,Integer> maxbranch)
    {
        if(root==null)return 0;
        int llen=calcmaxbranch(root.left,maxbranch);
        int rlen=calcmaxbranch(root.right,maxbranch);
        int ext=(llen>rlen)?llen:rlen;
        int mylen=root.val+(ext>0)?ext:0;
        maxbranch.put(root,mylen);
        return mylen;
    }
    public int findMaxPathSum(TreeNode root,HashMap<TreeNode,Integer> maxbranch)
    {
        if(root==null)return 0;
        int sum2=Integer.MIN_VALUE;
        int sum3=Integer.MIN_VALUE;
        int sum11=0;
        if(root.left!=null)
        {
            sum11=maxbranch.get(root.left);
            sum2=findMaxPathSum(root.left,maxbranch);
        }
        int sum12=0;
        if(root.right!=null)
        {
            sum12=maxbranch.get(root.right);
            sum3=findMaxPathSum(root.right,maxbranch);
        }
        int sum1=root.val;
        if(sum11>0)sum1+=sum11;
        if(sum12>0)sum1+=sum12;
        int max=sum1;
        if(sum2>max)max=sum2;
        if(sum3>max)max=sum3;
        return max;
    }
   
    public int maxPathSum(TreeNode root) {
        HashMap<TreeNode,Integer> maxbranch=new HashMap<TreeNode,Integer>();
        calcmaxbranch(root,maxbranch);
        int res=findMaxPathSum(root,maxbranch);
        return res;
    }
}

LeetCode: Single Number 2

Given an array of integers, every element appears three times except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

public class Solution {
    public int singleNumber(int[] A) {
        int N=64;
        int countbit[]=new int[N];
        int countbitN[]=new int[N];
        int res=0;
        int resN=0;
        for(int i=0;i<A.length;i++)
        {
            int n=A[i];
            if(n>=0)
                for(int j=0;j<N;j++)
                    countbit[j]+=((n&(1<<j))>0)?1:0;
            else
                for(int j=0;j<N;j++)
                    countbitN[j]+=((-(1+n)&(1<<j))>0)?1:0;
           
        }
        for(int j=0;j<64;j++)
        {
            if(countbit[j]%3>0)res|=(1<<j);
            if(countbitN[j]%3>0)resN|=(1<<j);
        }
       
        return (resN>0)?-(resN+1):res;
    }
}

LeetCode : anagrams

public class Solution {
    
    public String hashcoding(String s){
        int count[]=new int[26];
        StringBuffer sb=new StringBuffer("H");
        for(int i=0;i<s.length();i++)
            count[s.charAt(i)-'a']++;
        for(int i=0;i<26;i++)
            if(count[i]>0)sb.append(""+(i+(int)'a')+count[i]);
        return sb.toString();
    }
    public ArrayList<String> anagrams(String[] strs) {
        HashMap<String,ArrayList<String>> hm= new HashMap<String,ArrayList<String>>();
        ArrayList<String> rl=new ArrayList<String>();
        int ecount=0;
        for(int i=0;i<strs.length;i++)
        {
            String hc=hashcoding(strs[i]);
            ArrayList<String> al=hm.get(hc);
            if(al==null)al=new ArrayList<String>();
            al.add(new String(strs[i]));
            if(hm.get(hc)==null)hm.put(hc,al);
        }
        
        for(ArrayList<String> al:hm.values())
        {
            if(al.size()>1)rl.addAll(al);
        }
        
        return rl;
    }
}

LeetCode:palindrome

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

public class Solution {
    public boolean isPalindrome(int x) {
        if(x<0) return false;
        if(x<10) return true;
        int l=(int)Math.log10(x)+1;
        for(int i=l/2;i>=1;i--)
        {
           int r100=(int)Math.pow(10,i);
           int l100=(int)Math.pow(10,l-i);
           int rc=x%r100;
           int lc=x/l100;
           int rcl=(int)Math.log10(rc)+1;
           int lcl=(int)Math.log10(lc)+1;
           if(lcl>1)
           {
                if((rc<10)&&(lc%((int)Math.pow(10,lcl))==0))
                if(rc%10==lc/(int)Math.pow(10,lcl))
                {
                    if(l-rc-lc==0)
                        return true;
                    else
                        return isPalindrome((x/r100)%10);
                }
           }
           else if(lcl==1&&rc==lc)
                if(l-rc-lc==0)
                    return true;
                else
                    return isPalindrome((x/r100)%10);
        }
return false;
    }
}

LeetCode : regular expression

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

public class Solution {
    public boolean isMatch(String s, String p) {
        
        // p=.*  s=c  ==> recursive
        
        // p=.   s=c  ==> p++, s++
        
        // p=x*  s=c  => p+=2
        //       s=x  => s++
        
        // p=x   s=c  => not
        //       s=x  => p++, s++
        
        int sl=s.length();
        int pl=p.length();
        char p1,p2;
        char s1;
        
        if(sl==0)
        {
            if(pl==0)return true;                                           // "":""    => T
            
            if(pl>1)                
            {
                p1=p.charAt(0);
                p2=p.charAt(1);                                             // "":"a*"  => T
                if(pl==2)                                                   // "":".*"  => T
                {
                     return (p2=='*'&&(p1=='.'||(p1>='a'&&p1<='z')||(p1>='A'&&p1<='Z')));
                }
                else if((p1>='a'&&p1<='z')||(p1>='A'&&p1<='Z')||p1=='.')   
                {
                    if(p2=='*') 
                            return isMatch(s,new String(p.substring(2)));   // "":"a*??" => recursive
                    else
                            return false;                                   // "":"a" => F
                }
            }
            return false;
        }
        
        if(sl>0&&pl==0) return false;                                       // "a...":""  => F
        
        p1=p.charAt(0);
        s1=s.charAt(0);
        if(pl==1)
        {
            if(p1=='.'||((p1==s1)&&((p1>='a'&&p1<='z')||(p1>='A'&&p1<='Z'))))
                return isMatch(new String(s.substring(1)),"");                  //"abc...":"?" => recursive
            else
                return false;
        }
        
        p2=p.charAt(1);
        if((p1>='a'&&p1<='z')||(p1>='A'&&p1<='Z'))                             
        {
            if(p2=='*')                                           // "abc...":"b*abc..." => test many cases
            {
                if(isMatch(s,new String(p.substring(2))))
                    return true;
                else
                    for(int i=0;(i<sl)&&s.charAt(i)==p1;i++)
                        if(isMatch(new String(s.substring(i+1)),new String(p.substring(2))))
                            return true;;
                return false;                                                   // "abc...":"a*cd.." =>F 
            }
            else
            {
                if(p1==s1)                                                      // "a...":"a..." =>recursive
                    return isMatch(new String(s.substring(1)),new String(p.substring(1)));
                else
                    return false;                                               // "a...":"b..." =>F
            }
        }
        else if(p1=='.')   
        {
            if(p2=='*')
            {
                if(pl==2)
                    return true;                                             // "????":".*"     => T
                else if(isMatch(s,new String(p.substring(2))))               // "a???":".*a???" => recursive
                    return true;
                else
                    for(int i=0;i<sl;i++)                             // "aaab??":".*b" =>test many cases
                        if(isMatch(new String(s.substring(i+1)),new String(p.substring(2))))
                            return true;
                return false;
            }
            else
            {                                                             // "ab???":".b???" => recursive
                    return isMatch(new String(s.substring(1)),new String(p.substring(1)));
            }
        }

        return false;
    }
}

LeetCode : Subset I

Given a set of distinct integers, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

Input:[4,1,0]
Expected:[[],[0],[1],[4],[0,1],[0,4],[1,4],[0,1,4]]


public class Solution {
    
    // we do it recursively
    public void pickSS(ArrayList<ArrayList<Integer>> list, int[] remain)
    {
        if(remain==null)return;
        int rl=remain.length;
        if(rl==0) return;
        
        // seperate the list f + remain2
        int f=remain[0];
        int[] remain2=new int[rl-1];
        for(int i=0;i<rl-1;i++){
            remain2[i]=remain[i+1];
        }
        
        ArrayList<ArrayList<Integer>> templist = new ArrayList<ArrayList<Integer>>();

        // templist is addition list
        for(ArrayList<Integer> al:list)
        {
            ArrayList<Integer> nl=new ArrayList<Integer>(); //new list
            int all=al.size();
            if(all==0)
            {
                nl.add(0,f);
                templist.add(nl);  // empty list + one element f
            }
            else
            {
                for(int i=0;i<all;i++)
                    nl.add(i,(Integer)al.get(i));
                nl.add(all,f);
                templist.add(nl);   // joining a list + one element f.
            }
        }

        // result list = original list + temp list
        for(ArrayList<Integer> al:templist)
        {
            list.add(al);
        }
        
        // call next level
        pickSS(list,remain2);
    }

    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        
        ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
        res.add(new ArrayList<Integer>());
        
        //sort S
        for(int i=0;i<S.length;i++)
        {
            for(int j=i+1;j<S.length;j++)
            {
                if(S[j]<S[i])
                {
                    int t=S[i];
                    S[i]=S[j];
                    S[j]=t;
                }
            }
        }
        pickSS(res, S);
        return res;
    }
}