[Leetcode]07/09 [Hash]Count Primes

/* No hashMap here @@ Time:O(n^2), Space:O(1) Logic: isPrime:O(n) 1-n check isPrime:O(n)*O(n)=O(n^2) Time:O(nlog(logn)); Space:O(n) Logic: ，Sieve of Eratosthenes step 1. assume all number are prime number step 2. starting from 2, take out all 2*2, 2*3, 2*4...2*X and then take out all 3*2, 3*3, 3*4...3*X step 3. count all isPrime number NOTE: i < Math.sqrt(n) boolean isPrime[] = new boolean[n+1]; */

public class Solution {
    public int countPrimes(int n) {
        // speical case
        if ( n <= 2 )
        {
            return 0;
        }
        boolean isPrime[] = new boolean[n+1];
        // step 1. 
        for (  int i =2; i < n ; i++ )
        {
            isPrime[i] = true;
        }  
        // step 2.
        for ( int i =2; i < Math.sqrt(n); i++ )
        {
            if (isPrime[i])
            {
                for ( int j = i+i; j < n; j=j+i)
                {
                    isPrime[j] = false;
                }
            }
        }
        
        // step3
        int count = 0;
        for ( int i =2; i < n ; i++ )
        {
            if (isPrime[i])
            {
                count++;
            }
        }
        
        return count;
    }
}

07/08 [hash]Happy Number

/* Time:O(); Space:O() Logic: 1. perform calculation of a^2 ++ b^2 2. record the value of a^2 ++ b^2 in the HashSet */

public class Solution {
    public boolean isHappy(int n) {
        HashSet set = new HashSet();
        while (!set.contains(n))
        {
            set.add(n);
            n = sum(getDigits(n));
            if ( n ==1 )
            {
                return true;
            }
        }
        return false;
    }
    
    private int sum (int[] arr)
    {
        int sum = 0;
        for ( int i: arr)
        {
            sum+= i*i;
        }
        return sum;
    }
    
    private int[] getDigits(int n)
    {
        String s = String.valueOf(n);
        int[] result = new int[s.length()];
        int i = 0;
        while ( n > 0 )
        {
            int m = n%10;
            result[i++] = m;
            n = n/10;
        }
        return result;
    }
}

[Leetcode]07/08 [hash] Isomorphic Strings

/* Method1: Time:O(n^2); Space:O(n) Logic: check each correpsonding character set if in the map and backward check if the corresponding key of c2 is the same as current c1 getKey() Method2: Time:O(n):Space:O(2n) Logic: Two hashmap sourceMap[ t[x] ] = s[x] targetMap[ s[x] ] = t[x] False if two map relationship valid;Otherwise, it is ture. Given "egg", "add", return true. Given "foo", "bar", return false. Given "paper", "title", return true. */

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        
        
        /* Metho1: 
        // special case
        if (  s== null || t == null )
        {
            return false;
        }
        if ( s.length() != t.length() )
        {
            return false;
        }
        if (  s.length() ==0 && t.length() == 0 )
        {
            return true;
        }
        
        HashMap map = new HashMap();
        for ( int i = 0; i < s.length();i++  )
        {
            char c1 = s.charAt(i);
            char c2 = t.charAt(i);
            
            //Input:
            //  "ab", "aa"
            //Output:
            //true
            //Expected:
            //false
            // **** Need to backward check
            
            //if ( map.containsKey(c1) )
            //{
            //    if ( c2 != map.get(c1) )
            //    {
            //        return false;
            //   }
            //}
            //else 
            //{
            //    map.put(c1,c2);
            //}
            
            
            Character c = getKey(map,c2);
            if ( c != null && c != c1)
            {
                return false;
            }
            else if ( map.containsKey(c1) )
            {
                if ( c2 != map.get(c1) )
                {
                    return false;
                }
            }
            else 
            {
                map.put(c1,c2);
            }
            
        }
        return true;
        */
        
        
        
        
        /*Method2:*/
        if ( s.length() != t.length() )
        {
            return false;
        }
        if ( s.length() == 0 && t.length() == 0)
        {
            return true;
        }
        if ( s == null || t == null )
        {
            return false;
        }
        HashMap map1 = new HashMap();
        HashMap map2 = new HashMap();
        for (  int i = 0 ;i < s.length() ;i ++)
        {
            char c1 = s.charAt(i);
            char c2 = t.charAt(i);
            if (  map1.containsKey(c1) )
            {
                if ( map1.get(c1) != c2 ) 
                {
                    return false;
                }
            }
            if ( map2.containsKey(c2) )
            {
                if ( map2.get(c2) != c1 )
                {
                    return false;
                }
            }
            map1.put( c1,c2 );
            map2.put( c2,c1);
        }
        return true;
    }
    
    
    // a method for getting key given a target value
    // a method for getting key of a target value
    
    private Character getKey(HashMap map, Character value )
    {
        for ( Map.Entry entry : map.entrySet() )
        {
            if ( entry.getValue().equals(value) )
            {
                return entry.getKey();
            }
        }
        return null;
    }
    
}

[Leetcode]07/06 [String] Reverse Words in a String

/* Recursive NOTE null vs "" "" is an actual string, you can still invoke methods or functions on it like a.length() a.substring(0, 1) null, like b, Java would throw a NullPointerException if you tried invoking, say b.length() http://stackoverflow.com/questions/4802015/difference-between-null-and-java-string Mrthod1: Time:O(n), Sapce:O(n) Logic: Split and keep appending inside 1. split by space to get each word - iterate thru string when ' ' is met, record the word and skip ' ' 2. append getting word in the end Ex. the sky is blue => "sky is blue" + "the" => "is blue" + "sky " + "the" => "blue" + "is " + "sky "+"the" => "" + "blue" + "is " + "sky "+"the" NOTE: return helper(s,index).append(cur); return helper(s,index).append(cur).append(' '); Method2: (Iterative) Two poitners Time:O(n), SpacE:O(n) Logic: 先反转整体，再反转局部 1. "the sky is blue" => "eulb si yks eht" O(n) 2. "eulb si yks eht" => "blue is sky the" O(n) NOTE: s = s.trim(); It returns a copy of this string with leading and trailing white space removed // skip one of double spaces if ( i != s.length() -1 && s.charAt(i)== ' ' && s.charAt(i)==s.charAt(i+1) ) { continue; } */

public class Solution {
    public String reverseWords(String s) {
      /* Method1:
      s = s.trim();
      return helper(s,0).toString();
      */
      
      
      /* Method2:*/
      if ( s == null  )
      {
          return null;
      }
      if ( s.length() == 0 )
      {
          return "";
      }
      s = s.trim();
      // 1. reverse entire string from the last character
      StringBuilder res = new StringBuilder();
      for (  int i = s.length()-1; i >=0 ; i--  )
      {
          // skip one of double spaces
          if ( i != s.length() -1 && s.charAt(i)== ' ' && s.charAt(i)==s.charAt(i+1) )
          {
              continue;
          }
          res.append(s.charAt(i));
      }
      // 2. reverse each word, scan twice: 
      // one for length and one for reverse
      int left = 0;
      int right = 0;
      while ( right < res.length()  )
      {
          // 1. get the end index of each word
          while( right < res.length() && res.charAt(right) != ' ' )
          {
            right++;    
          }
          int next = right + 1; // right after ' '
          right--;
          // 2. two poitners for each word, 
          // one point to start and the other point the end
          while(  left < right ) 
          {
              // 3. swap
              char temp = res.charAt(left);
              res.setCharAt( left++, res.charAt(right) );
              res.setCharAt( right--, temp );
          }
          // 4. reset the start for two poitners
          left = next;
          right = next;
      }
      return res.toString();
    }
    
    // Method1:
    private StringBuilder helper( String s, int index )
    {
        // Base case
        if (  index >= s.length() )
        {
            return new StringBuilder();
        }
        // 1. append not ' ' 
        StringBuilder cur = new StringBuilder();
        int lastIndex = index;
        while ( index < s.length() && s.charAt(index) != ' ' )
        {
            cur.append( s.charAt(index++) );
        }
        // 2. remove ' '
        while ( index < s.length() && s.charAt(index) == ' ' )
        {
            index++;
        }
        
        // 3. first word append to the end
        if (lastIndex == 0 )
        {
            return helper(s,index).append(cur);
        }
        // 4. not the first word
        return helper(s,index).append(cur).append(' ');
    }
}

[Leetcode] 07/06 [String] Generate Parentheses

Recursive Time:O(); Space:O() Logic: ==> (( => (( ) => (( )) ( L2 R0 L2 R1 L2 R2 L1 R0 ==> ( ) => ( ) ( => ( ) ( ) L1 R1 L2 R1 L2 R2 NOTE: C_0 =1, C_1 = 1, C_2 =2 ,C_3 = 5, C_4 = 14 C_0 =1, C_n+1 = [i=0~n]signma(C_i*C_n-i), for n >= 0 C3 = C_0*C2 + C_1*C_1 + C_2*C_0 = 2 + 1 + 2 = 5 C_n+1 = ( 2(2*n+1) / n+2 )* C_n the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively-defined objects. Re-interpreting the symbol X as an open parenthesis and Y as a close parenthesis, Cn counts the number of expressions containing n pairs of parentheses which are correctly matched: C_0 = 1 \quad \mbox{and} \quad C_{n+1}=\sum_{i=0}^{n}C_i\,C_{n-i}\quad\text{for }n\ge 0;

public class Solution {
    public List generateParenthesis(int n) {
        ArrayList res = new ArrayList();
        if ( n < 0 )
        {
            return res;
        }    
        helper( n,n, new String(), res );
        return res;
    }
    
    private void helper( int l, int r, String item, ArrayList res ) 
    {
        // Base case
        // remaining r should be greater or equal to l
        if ( r < l )
        {
            return;
        }
        // when consuming all l and r, return current combination
        if ( l == 0 && r == 0 )
        {
            res.add(item);
        }
        
        
        if (  l > 0 )
        {
            helper( l-1, r, item+"(", res);
        }
        if (  r > 0 )
        {
            helper(l, r-1, item+")", res);
        }
    }
}

test syntaxHighlighter

<?php
$example = range(0, 9);
foreach ($example as $value)
{
 echo $value;
}

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:

Add Your Encoded Code Here
   /* Method2:*/
    Stack stack = new Stack();
    stack.push(1);
    int res = 0;
    int sign = 1;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '+' || c == '-') {
            sign = c == '+' ? 1: -1;
        } else if (c == '(') {
            stack.push(sign * stack.peek());
            sign = 1;
        } else if (c == ')') {
            sign = stack.pop();
        } else if (Character.isDigit(c)) {
            int num = 0;
            while (i < s.length() && Character.isDigit(s.charAt(i))) {
                num = num * 10 + (s.charAt(i) - '0');
                i++;
            }
            i--;
            res += sign * num * stack.peek();
        }
    }
    return res;