Arrays

Initialization

Type[] a = new Type[length];
Type[] a = {a,b,c,...,z};

Type[][] = new Type[length][length];
Type[][] = new Type[length][];
Type[][] = {{a,b,c,...,d},{a,b,...,z}};

Sorting

import java.util.Arrays;
int[] a = {9,7,3,8,2}

Arrays.sort(a);
Arrays.sort(Object[], Comparator c);

Searching

int index = Arrays.binarySearch(Array, term);

Array to List

List l = Array.asList(Array);

ArrayList

Basics

import java.util.*;
ArrayList<Type> a = new ArrayList<Type>
a.add(data);
a.size();
a.get(index);
a.clear();
a.remove(index);
a.set(index, value);

Array to ArrayList

ArrayList<Type> a = new ArrayList<Type>(Arrays.asList(myArray));

ArrayList to Array

Type[] myArray = a.toArray();

Strings

Basics

"String".length();
"String".toCharArray();
"String".toUpperCase();
"String".toLowerCase();
"String".trim();

Split String on Whitespace

String[] tokens = line.trim().split("\\s+");

Regex Based String Replacement

String s = "This is a string".replaceAll(REGEX, "replacement");

String Equals

"String".equals("String 2");
"String".equalsIgnoreCase("String 2");

Substrings

String s = "String".substring(beginIndex, endIndex);
String s = "String".substring(beginIndex, beginIndex + length);

Commonly Used API

Interface java.util.List<E>

boolean         add(E o)
void            add(int index, E element)
boolean         addAll(Collection<? extends E> c)
boolean         addAll(int index, Collection<? extends E> c)
void            clear()
boolean         contains(E o)
boolean         containsAll(Collection<?> c)
E               get(int index)
int             indexOf(E o)
boolean         isEmpty()
Iterator<E>     iterator()
int             lastIndexOf(E o)
ListIterator<E> listIterator()
ListIterator<E> listIterator(int index)
E               remove(int index)
boolean         remove(E o)
boolean         removeAll(Collection<?> c)
boolean         retainAll(Collection<?> c)
E               set(int index, E element)
int             size()
List<E>         subList(int fromIndex, int toIndex)
Object[]        toArray()

Interface java.util.Comparator<T>

int compare(T o1, T o2);

Interface java.util.Map<K, V>

void          clear()
boolean       containsKey(Object key)
boolean       containsValue(Object value)
V             get(K key)
boolean       isEmpty()
Set<K>        keySet()
V             put(K key, V value)
void          putAll(Map<? extends K,? extends V> t)
V             remove(K key)
int           size()
Collection<V> values()

Class java.util.Collections

int     binarySearch(List<T> list, T key)
boolean disjoint(Collection<?> c1, Collection<?> c2)
List    emptyList()
Map     emptyMap()
Set     emptySet()
void    fill(List<T> list, T value)
int     frequency(Collection <C> col, C value)
int     indexOfSublist(List<?> source, List<?> target)
int     lastIndexOfSublist(List<?> source, List<?> target)
T       max(Collection <T> col)
T       max(Collection <T> col, Comparator<T> cmp)
T       min(Collection <T> col)
T       min(Collection <T> col, Comparator<T> cmp)
boolean replaceAll(List<T> list, T oldVal, T newVal)
void    reverse(List<T> list)
void    rotate(List<T> list, int distance)
void    shuffle(List<T> list)
void    sort(List<T> list)
void    swap(List<T> list, int i, int j)

Class java.util.Arrays

int     binarySearch(Type [] array)
String  deepToString(Type [] array)
boolean equals(Type [] array)
void    fill(Type [] array, Type value)
void    sort(Type [] array)
String  toString(Type [] array)

Class java.util.Random

Random()
Random(long seed)

boolean nextBoolean()
void    nextBytes(byte[] bytes)
double  nextDouble()
float   nextFloat()
double  nextGaussian()
int     nextInt()
int     nextInt(int n)
long    nextLong()
void    setSeed(long seed)

Static Class java.lang.Math

static double    abs(double a)
static double    acos(double a)
static double    asin(double a)
static double    atan(double a)
static double    atan2(double y, double x)
static double    cbrt(double a)
static double    ceil(double a)
static double    cos(double a)
static double    cosh(double x)
static double    exp(double a)
static double    floor(double a)
static double    hypot(double x, double y)
static double    log(double a)
static double    log10(double a)
static double    max(double a, double b)
static double    min(double a, double b)
static double    pow(double a, double b)
static double    random()
static double    rint(double a)
static long      round(double a)
static double    sin(double a)
static double    sin(double a)
static double    sinh(double x)
static double    sqrt(double a)
static double    tan(double a)
static double    tanh(double x)
static double    toDegrees(double angrad)
static double    toRadians(double angdeg)
# The sign of the argument, or 0 if a==0
static double    signum(double a)

Class java.lang.Integer [And Long]

static int     MIN_VALUE
static int     MAX_VALUE
static int     bitCount(int i)
static Integer decode(String s)
static int     highestOneBit(int i)
static int     lowestOneBit(int i)
static int     numberOfTrailingZeros(i)
static int     numberOfLeadingZeros(i)
static int     parseInt(String s)
static int     parseInt(String s, int radix)
static int     rotateLeft(int i, int distance)
static int     rotateRight(int i, int distance)
static int     toString(int i, int radix)

Class java.lang.Character

static boolean    isDigit(char c)
static boolean    isLetter(char c)
static boolean    isLetterOrDigit(char c)
static boolean    isLowerCase(char c)
static boolean    isUpperCase(char c)
static boolean    isWhiteSpace(char c)

Class java.lang.String

char          charAt(int i)
boolean       contains(CharSequence s)
boolean       endsWith(String s)
boolean       equals(String s)
boolean       equalsIgnoreCase(String s)
static String format(String fmt_str, args)

# The next 8 methods return -1 if character not found
int        indexOf(char ch)
int        indexOf(char ch, int fromIndex)
int        indexOf(String s)
int        indexOf(String s, int fromIndex)
int        lastIndexOf(char ch)
int        lastIndexOf(char ch, int fromIndex)
int        lastIndexOf(String s)
int        lastIndexOf(String s, int fromIndex)
int        length()

boolean    matches(String regex)
String     replace(char old, char new)
String     replace(String old, String new)
String     replaceAll(String regex, String replace)
String     replaceFirst(String regex, String replace)
String[]   split(String regex)
String[]   split(String regex, int limit)
boolean    startsWith(String s)
String     substring(int beginIndex)
String     substring(int beginIndex, int endIndex)
char[]     toCharArray()
String     toLowerCase()
String     toUpperCase()
String     trim()
String     valueOf(xxx)

Geometry Related

import java.awt.*;
import java.awt.geom.*;

Point p = new Point(double x, double y);
p.translate(dx, dy);
p.getX() p.getY()

Line2D line = new Line2D.Double(x1, y1, x2, y2);
Line2D line = new Line2D.Double(Point, Point);
line.intersects(Rectangle r);
line.intersectsLine(Line2D l);
line.intersectsLine(x1, y1, x2, y2);
line.ptLineDist(Point p);
line.relativeCCW(Point p); // returns 1, -1, or 0

Rectangle r = new Rectangle(x, y, w, h);
# If p is in or on r
r.contains(Point p);
# If r completely contains r1
r.contains(Rectangle r1);
r.intersects(Rectangle r1);
# rInt is the inter. of both. w/h negative if no inter.
Rectangle rInt = r.intersecrtion(r1);

Polygon poly = new Polygon(int[] x, int[] y, int n);
Rectangle r = poly.getBounds();
poly.contains(Point p);
poly.contains(Rectangle r);
poly.intersects(Rectangle r);

Regular Expressions

Example

import java.util.regex.*;

String line = "Some String";

Pattern p = Pattern.compile(regex);
Matcher m = p.matcher(line);

while(m.find()) {
    // lines are the same
    System.out.println(line.substring(m.start(), m.end()));
    System.out.println(m.group());
}

Anchors

^    Start of Line
\A   Start of String
$    End of Line
\Z   End of String

Character Classes

\c    Control Character
\s    White Space
\S    Not White Space
\d    Digit
\D    Not Digit
\w    Word
\W    Not Word

Assertions

?=    Lookahead
?!    Negative Lookahead

Quantifiers

*      0 or More Greedy
*?     0 or More
+      1 or More Greedy
+?     1 or More
?      0 or 1 Greedy
??     0 or 1
{x}    x Times
{x,}   x or More Times
{x,y}  x to y Times
{x,y}? x to y Times UnGreedy

Ranges

.       Any Character Except \n
(a|b)   a or b
[abc]   Range [a or b or c]
[^abc]  Not a or b or c
[a-z]   a or b or ... or z

Characters That Need to be Escaped

^    [    .    $    {    *

(    \    +    )    |    ?

<    >

Algorithms

Permutations

public class perms {

    // ordered
    public  static void perm1(String s) { perm1("", s); }
    private static void perm1(String prefix, String s) {
        int n = s.length();
        if (n == 0){
            System.out.println(prefix);
            return;
        }
        for (int i = 0; i < n; i++){
             perm1(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, n));
        }
    }

    // no order
    public static void perm2(String s) { perm2(s.toCharArray(), s.length());}
    private static void perm2(char[] a, int n) {
        if (n == 1) {
            System.out.println(a);
            return;
        }
        for (int i = 0; i < n; i++) {
            swap(a, i, n-1);
            perm2(a, n-1);
            swap(a, i, n-1);
        }
    }

    // swap the characters at indices i and j
    private static void swap(char[] a, int i, int j) {
        char c;
        c = a[i]; a[i] = a[j]; a[j] = c;
    }

    public static void main(String[] args) {
       String alphabet = "123";
       perm1(alphabet);
    }
}

Combinations With Replacement

class CombinationsWithReplacement{
    public static void generate(char[] values, int k, char[] value){

        // do something here for every combination of any size
        // ie. a, b, aa, ab, ba, bb
        /*
        //EXAMPLE
        String cb = "";
        for(int i = 0; i < k; i++){
            cb += value[i];
        }
        System.out.println(cb);
        */
        if(k == value.length){
            // or here for combinations of full size
            // ie. aa, ab, ba, bb
            return;
        }
        else{
            for(char v: values){
                value[k] = v;
                k++;
                generate(values, k, value);
                k--;
            }
        }
    }

    public static void main(String[] args){
        char[] values = "abcdefghijklmnopqrstuvwxyz".toCharArray();
        char[] value = new char[2];

        generate(values, 0, value);

    }
}

KnapSack [Example]

public class KnapSack {

    public static void main(String[] args) {
        int N = Integer.parseInt(args[0]);   // number of items
        int W = Integer.parseInt(args[1]);   // maximum weight of knapsack

        int[] profit = new int[N+1];
        int[] weight = new int[N+1];

        // generate random instance, items 1..N
        for (int n = 1; n <= N; n++) {
            profit[n] = (int) (Math.random() * 1000);
            weight[n] = (int) (Math.random() * W);
        }

        // opt[n][w] = max profit of packing items 1..n with weight limit w
        // sol[n][w] = does opt solution to pack items 1..n with weight limit w include item n?
        int[][] opt = new int[N+1][W+1];
        boolean[][] sol = new boolean[N+1][W+1];

        for (int n = 1; n <= N; n++) {
            for (int w = 1; w <= W; w++) {

                // don't take item n
                int option1 = opt[n-1][w];

                // take item n
                int option2 = Integer.MIN_VALUE;
                if (weight[n] <= w) option2 = profit[n] + opt[n-1][w-weight[n]];

                // select better of two options
                opt[n][w] = Math.max(option1, option2);
                sol[n][w] = (option2 > option1);
            }
        }

        // determine which items to take
        boolean[] take = new boolean[N+1];
        for (int n = N, w = W; n > 0; n--) {
            if (sol[n][w]) { take[n] = true;  w = w - weight[n]; }
            else           { take[n] = false;                    }
        }

        // print results
        System.out.println("item" + "\t" + "profit" + "\t" + "weight" + "\t" + "take");
        for (int n = 1; n <= N; n++) {
            System.out.println(n + "\t" + profit[n] + "\t" + weight[n] + "\t" + take[n]);
        }
    }
}

Floyd-Warshall All Pairs Shortest Path

public class FloydWarshall {

   public int[][] D;
   public Node[][] P;

   public void calcShortestPaths(Node[] nodes, Edge[] edges) {
       D = initializeWeight(nodes, edges);
       P = new Node[nodes.length][nodes.length];

       for(int k=0; k<nodes.length; k++){
           for(int i=0; i<nodes.length; i++){
               for(int j=0; j<nodes.length; j++){
                   if(D[i][k] != Integer.MAX_VALUE && D[k][j] != Integer.MAX_VALUE && D[i][k]+D[k][j] < D[i][j]){
                       D[i][j] = D[i][k]+D[k][j];
                       P[i][j] = nodes[k];
                   }
               }
           }
       }
   }

   public int getShortestDistance(Node source, Node target){
       return D[source.name][target.name];
   }

   public ArrayList<Node> getShortestPath(Node source, Node target){
       if(D[source.name][target.name] == Integer.MAX_VALUE){
           return new ArrayList<Node>();
       }
       ArrayList<Node> path = getIntermediatePath(source, target);
       path.add(0, source);
       path.add(target);
       return path;
   }

   private ArrayList<Node> getIntermediatePath(Node source, Node target){
       if(P[source.name][target.name] == null){
           return new ArrayList<Node>();
       }
       ArrayList<Node> path = new ArrayList<Node>();
       path.addAll(getIntermediatePath(source, P[source.name][target.name]));
       path.add(P[source.name][target.name]);
       path.addAll(getIntermediatePath(P[source.name][target.name], target));
       return path;
   }

   private int[][] initializeWeight(Node[] nodes, Edge[] edges){
       int[][] Weight = new int[nodes.length][nodes.length];
       for(int i=0; i<nodes.length; i++){
           Arrays.fill(Weight[i], Integer.MAX_VALUE);
       }
       for(Edge e : edges){
           Weight[e.from.name][e.to.name] = e.weight;
       }
       return Weight;
   }
}