Common Algorithms in Java

Input Files

To be able to use a file:

import java.io.*;

import java.util.*;

To declare and initialize a file and a scanner:

File f = new File("ceasar.txt");

Scanner input = new Scanner(f);

To read the next int (stops right after the last digit of the int). The int must be followed by whitespace (blank, tab, or end-of-line character):

i = input.nextInt();

To read the next double (stops right after the last digit of the double). The double must be followed by whitespace (blank, tab, or end-of-line character):

d = input.nextDouble();

To read to the end of the line (returns a string and moves past the end-of-line character):

str = input.nextLine();

Range and Precision

int: from -2,147,483,648 to 2,147,483,647

Long.MAX_VALUE =  9223372036854775807

Long.MIN_VALUE = -9223372036854775808

Double: approximately 15 digits. 1.79769313486231570e+308d 

Parameters

Primitives are passed by value. You cannot change the value of a primitive in a method. Primitives are int, char, boolean, and double. Everything else is an object.

Comparing strings and other objects

Objects can only be compared by using the compareTo method. If you have two objects x and y and you execute the following:

x.compareTo(y)

a negative value will be returned if x<y, zero will be returned if x==y, and a positive value will be returned if x>y.

Arrays

Arrays are objects, and when you pass an array as a parameter, all changes made to the array in the method are actually changing the actual array. If you want to copy all elements from one array to another, you must copy one element at a time. You cannot just do this:

array1 = array2;

This just produces two references (pointers) to the same array.

Bubble Sort: Sorting integers

public static void BubbleSort( int [ ] num )
{
    int j;
    boolean notSorted = true;  // set flag to true to begin first pass
    int temp;   //holding variable

    while ( notSorted )
    {
         notSorted = false;   //set flag to false awaiting a possible swap
         for( j=0;  j < num.length -1;  j++ )
         {
            if ( num[ j ] < num[j+1] )// change to > for ascending sort
            {
                temp = num[ j ];            //swap elements
                num[ j ] = num[ j+1 ];
                num[ j+1 ] = temp;
                notSorted = true;           //shows a swap occurred  
            } 
         } 
     } 
} 

Reversing an array's elements

    public static void reverseList(int[] list)

    {

        for (int i=0, j=list.length-1; i<list.length/2; i++,j--)

        {

            int save = list[i];

            list[i] = list[j];

            list[j] = save;

        }

    }


 

Greatest Common Divisor of two integers

private static long gcd(long a, long b)

{

    while (b > 0)

    {

        long temp = b;

        b = a % b; // % is remainder

        a = temp;

    }

    return a;

}

Greatest Common Divisor of an array of integers

private static long gcd(long[] input)

{

    long result = input[0];

    for(int i = 1; i < input.length; i++) result = gcd(result, input[i]);

    return result;

}

Least Common Multiple of two integers

private static long lcm(long a, long b)

{

    return a * (b / gcd(a, b));

}

Least Common Multiple of an array of integers

private static long lcm(long[] input)

{

    long result = input[0];

    for(int i = 1; i < input.length; i++) result = lcm(result, input[i]);

    return result;

}


 

Prime Numbers

public static void main(String[] args){

   low=2;

   high=1000;

   printAllPrimes(low, high);

}

 

public static void printAllPrimes(int start,int end)

{

   for(int i = start;i <= end;i++)

      if(isPrime(i))

         System.out.println("Print prime:"+i);

}

 

private static boolean isPrime(int i)

{

   if(i%2 == 0 && i!=2)

      return false;

   else{

      if(i == 1)

         return false;

 

   for(int p=3;p<=i/2;p+=2)

      if(i%p == 0)

         return false;

 

   return true;

}

Converting Strings to numbers

If iStr is a string representing an integer and dStr is a string representing a double, you can convert them to an int and a double, respectively with:

Integer.parseInt(iStr)

Double.parseDouble(dStr)

Reading an input line and converting it to tokens

The following assumes that the strings on the input line are separated by white space (blanks, tabs, or end-of-line characters), but only one white-space character.

//File f = new File ("problem1.txt");

String f = “Four score and seven years ago, our fathers brought forth”);

Scanner input = new Scanner (f);

While (input.hasNext())

{

   String[] s = input.nextLine().split("\\s");

   Process (s);

}

Reading an input line and converting it to tokens

The following assumes that the strings on the input line are separated by one or more of the following: whitespace ("\\s" is a code for any whitespace character: space, tab, carriage return), a semicolon, a comma, a period.

//File f = new File ("problem1.txt");

String f =

"Four score;    and seven\t years ago, our\nfathers brought. forth";

Scanner input = new Scanner(f);

while (input.hasNext()) {

    String[] s = input.nextLine().split("[\\s;,.]+");

    for (int i=0; i<s.length; i++)

        System.out.println (s[i]);

}

Strings

To step through a string, one character at a time, use charAt. The charAt method returns a character:

String line;

line = input.nextLine();

for (int i=0; i<line.length(); i++)

     System.out.print(line.charAt(i));

To step through a string, one character at a time, but returning a String (as opposed to a character in the previous example):

String line;

line = input.nextLine();

for (int i=0; i<line.length(); i++)

     System.out.print(line.substr(i, i+1);

NOTE: In the previous two examples, the output is the same. But in the first case, individual characters are being returned, and in the second case, strings that are one character long are being returned.