chandler.c.zuo
BAN USERpublic class trieNode{
public char key;
public Hashtable< char, trieNode> children;
public static trieNode root;
public boolean isWord;
public trieNode( char k ){
key = k;
children = new Hashtable< char, trieNode> ();
isWord = false;
}
public static void constructTrie( ArrayList<String> input ){
for( int i = 0; i < input.size(); i ++ ){
String st = input.at( i );
n = root;
for( int j = 0; j < st.size(); j ++ ){
trieNode newN;
if( ( newN = n.children.get( st.charAt( j ) ) )== null ){
newN = new trieNode( st.charAt( j ) );
n.children.add( newN );
}
n = newN;
}
n.isWord = true;
}
}
public static boolean search( String word ){
trieNode n = root;
trieNode newN;
for( int i = 0; i < word.size(); i ++ ){
if( ( newN = root.children.get( word.charAt( i ) ) ) == null )
return false;
n = newN;
}
if( n.isWord )
return true;
return false;
}
}
The following algorithm uses the recursive formula to generate Catalan Numbers.
public class Catalan{
public ArrayList< ArrayList< String> > allCatalanParentheses;
public Catalan( int n ){
for( int i = 0; i <= n; i ++ )
allCatalanParentheses.add( new ArrayList<String>() );
allCatalanParentheses.get( 0 ).add( "" );
}
public void generate( int n ){
for( int k = 1; k < n; k ++ ){
if( allCatalanParentheses.get( k ).size() == 0 ){
generate( k-1 );
}
if( allCatalanParentheses.get( n - k ).size() == 0 ){
generate( n - k );
for( int i = 0; i < allCatalanParentheses.get( k-1 ).size(); i ++ ){
for( int j = 0; j < allCatalanParentheses.get( n-k ).size(); j ++ ){
allCatalanParentheses.get( n ).add( "(" + allCatalanParentheses.get( k-1 ).get( i ) + ")" + allCatalanParentheses.get( n-k ).get( j ) );
}
}
}
}
public void print( int k ){
for( int i = 0; i < allCatalanParentheses.get( k ).size(); i ++ )
System.out.println( allCatalanParentheses.get( k ).get( i ) );
}
}
public int[] add( int[] a, int[] b ){
int len = a.length + 1;
int[] newa = a;
int[] newb = b;
if( a.length < b.length ){
len = b.length + 1;
newa = new int[b.length];
for( int i = a.length; i < b.length; i ++ )
newa[ i ] = 0;
} else {
len = a.length + 1;
newb = new int[a.length];
for( int i = b.length; i < a.length; i ++ )
newb[ i ] = 0;
}
int t = 0;
for( int i = len - 1; i > 0; i -- ){
ret[ i ] = ( newa[i-1] + newb[i-1] + t ) % 2;
t = newa[i-1] + newb[i-1] > 1 ? 1 : 0;
}
ret[ 0 ] =t;
return ret;
}
- chandler.c.zuo December 16, 2013