Tower of Hanoi program in Java ?

The towers of hanoi is a popular problem. You have three poles and n disks which fit on the poles. All disks have different size. They are stacked on pole 1 in the orders of their size. The largest disk is on the bottom, the smallest is on the top.

The task is to move all disk from pole 1 to pole 3 under the following restrictions.

Only one disk can be moved

A larger disk can not be placed on a smaller disk.

The recursive algorithm works like the following: move n-1 disk from the starting pole to the pole which is neither start nor target (intermediate), move disk n to the target pole and then move n-1 disk from the intermediate pole to the target pole. The n-1 disks are moved recursively.


public class MinimumWindow {

public static void move(int n, int startPole, int endPole) {
if (n == 0) {
return;
}
int intermediatePole = 6 - startPole - endPole;
move(n - 1, startPole, intermediatePole);
System.out.println("Move " + n + " from " + startPole + " to "
+ endPole);
move(n - 1, intermediatePole, endPole);
}

public static void main(String[] args) {
move(5, 1, 3);
}

}


Below is the output...

Move 1 from 1 to 3
Move 2 from 1 to 2
Move 1 from 3 to 2
Move 3 from 1 to 3
Move 1 from 2 to 1
Move 2 from 2 to 3
Move 1 from 1 to 3

Prime Factorization in Java ?

import java.util.ArrayList;
import java.util.List;

public class PrimeFactorization {

public static List<Integer> primeFactors(int numbers) {
int n = numbers;
List<Integer> factors = new ArrayList<Integer>();
for (int i = 2; i <= n / i; i++) {
while (n % i == 0) {
factors.add(i);
n /= i;
}
}
if (n > 1) {
factors.add(n);
}
return factors;
}

public static void main(String[] args) {
for (Integer integer : primeFactors(44)) {
System.out.println(integer);
}

System.out.println("---------");

for (Integer integer : primeFactors(3)) {
System.out.println(integer);
}
}

}

Below is the Output....

2
2
11
---------
3

Determine Prime number with the sieve of Eratosthenes in Java in java ?

import java.util.ArrayList;
import java.util.List;

public class DeterminePrime{

public static List<Integer> calcPrimeNumbers(int n) {
boolean[] isPrimeNumber = new boolean[n + 1]; // boolean defaults to
// false
List<Integer> primes = new ArrayList<Integer>();
for (int i = 2; i < n; i++) {
isPrimeNumber[i] = true;
}
for (int i = 2; i < n; i++) {
if (isPrimeNumber[i]) {
primes.add(i);
// Now mark the multiple of i as non-prime number
for (int j = i; j * i <= n; j++) {
isPrimeNumber[i * j] = false;
}
}

}

return primes;
}

public static void main(String[] args) {
List<Integer> calcPrimeNumbers = calcPrimeNumbers(21);
for (Integer integer : calcPrimeNumbers) {
System.out.println(integer);
}
System.out.println("Prime counting function (Pie(N)) : "
+ calcPrimeNumbers.size());
}

}


Below is the output...

2
3
5
7
11
13
17
19
Prime counting function (Pie(N)) : 8

Euclid's Greatest Common divisor alogorithmn ?

public class EuclidGCdAlgorithmn {

public static int gcd(int p, int q) {

if (q == 0) {
return p;
}

return gcd(q, p % q);
}

// Test enable assert check via -ea as a VM argument

public static void main(String[] args) {
System.out.print(" "+gcd(4, 16));

System.out.print(" "+gcd(16, 4));

System.out.print(" "+gcd(15, 60));
System.out.print(" "+gcd(15, 65));

System.out.print(" "+gcd(1052, 52));
}

}


Below is the output....

 4
 4
 15
 5
 4

Odd even Transposition algorithmn in Java ?

public class OddEvenTransposition {

public static void main(String a[]) {

int i;
int array[] = { 12, 9, 4, 99, 120, 1, 3, 10, 13 };

System.out.println(" Odd Even Transposition Sort\n\n");

System.out.println("Values Before the sort:\n");

for (i = 0; i < array.length; i++){
System.out.print(array[i] + "  ");
}

System.out.println();

odd_even_srt(array, array.length);

System.out.print("Values after the sort:\n");

for (i = 0; i < array.length; i++){
System.out.print(array[i] + "  ");
}

}

public static void odd_even_srt(int array[], int n) {
for (int i = 0; i < n / 2; i++) {
for (int j = 0; j + 1 < n; j += 2)
if (array[j] > array[j + 1]) {
int T = array[j];
array[j] = array[j + 1];
array[j + 1] = T;
}
for (int j = 1; j + 1 < array.length; j += 2)
if (array[j] > array[j + 1]) {
int T = array[j];
array[j] = array[j + 1];
array[j + 1] = T;
}
}
}
}


Below is the output....

Values Before the sort:

12  9  4  99  120  1  3  10  13  

Values after the sort:

1  3  4  9  10  12  13  99  120  

Merge sort algorithmn in Java?

public class MergeSort {

public static void main(String a[]) {
int i;
int array[] = { 12, 9, 4, 99, 120, 1, 3, 10 };

System.out.println("Values Before the sort:\n");

for (i = 0; i < array.length; i++) {
System.out.print(array[i] + "  ");
}

System.out.println();

mergeSort_srt(array, 0, array.length - 1);

System.out.print("Values after the sort:\n");

for (i = 0; i < array.length; i++) {
System.out.print(array[i] + "  ");
}

}

public static void mergeSort_srt(int array[], int lo, int n) {
int low = lo;
int high = n;
if (low >= high) {
return;
}

int middle = (low + high) / 2;
mergeSort_srt(array, low, middle);
mergeSort_srt(array, middle + 1, high);
int end_low = middle;
int start_high = middle + 1;
while ((lo <= end_low) && (start_high <= high)) {
if (array[low] < array[start_high]) {
low++;
} else {
int Temp = array[start_high];
for (int k = start_high - 1; k >= low; k--) {
array[k + 1] = array[k];
}
array[low] = Temp;
low++;
end_low++;
start_high++;
}
}
}
}


Below is the output...

Values Before the sort:

12  9  4  99  120  1  3  10

Values after the sort:

1  3  4  9  10  12  99  120

Insertion Sort Algorithmn in Java ?

public class InsertionSort {

public static void main(String a[]) {

int i;
int array[] = { 12, 9, 4, 99, 120, 1, 3, 10 };

System.out.println("Values Before the sort:\n");
for (i = 0; i < array.length; i++) {
System.out.print(array[i] + "  ");
}

System.out.println();

insertion_srt(array, array.length);

System.out.print("Values after the sort:\n");

for (i = 0; i < array.length; i++) {
System.out.print(array[i] + "  ");
}
}

public static void insertion_srt(int array[], int n) {
for (int i = 1; i < n; i++) {
int j = i;
int B = array[i];
while ((j > 0) && (array[j - 1] > B)) {
array[j] = array[j - 1];
j--;
}
array[j] = B;
}
}
}


Below is the output..

Values Before the sort:

12  9  4  99  120  1  3  10

Values after the sort:

1  3  4  9  10  12  99  120

Heap Sort algorithmn in Java ?

public class HeapSort {

public static void main(String a[]) {

int i;
int arr[] = { 1, 3, 4, 5, 2 };

for (i = 0; i < arr.length; i++) {
System.out.print(" " + arr[i]);
}

for (i = arr.length; i > 1; i--) {
fnSortHeap(arr, i - 1);
}

System.out.println("\n  Sorted array\n---------------\n");

for (i = 0; i < arr.length; i++) {
System.out.print(" " + arr[i]);
}

}

public static void fnSortHeap(int array[], int arr_ubound) {
int i, o;
int lChild, rChild, mChild, root, temp;
root = (arr_ubound - 1) / 2;

for (o = root; o >= 0; o--) {
for (i = root; i >= 0; i--) {
lChild = (2 * i) + 1;
rChild = (2 * i) + 2;
if ((lChild <= arr_ubound) && (rChild <= arr_ubound)) {
if (array[rChild] >= array[lChild])
mChild = rChild;
else
mChild = lChild;
} else {
if (rChild > arr_ubound)
mChild = lChild;
else
mChild = rChild;
}

if (array[i] < array[mChild]) {
temp = array[i];
array[i] = array[mChild];
array[mChild] = temp;
}
}
}
temp = array[0];
array[0] = array[arr_ubound];
array[arr_ubound] = temp;
return;
}
}


Below is the output....

 1 3 4 5 2

Sorted array
---------------

 1 2 3 4 5

Bi-directional bubble sort Algorithmn in java ?

public class BidirectionalBubbleSort {

public static void main(String a[]) {

int i;
int array[] = { 12, 9, 4, 99, 120, 1, 3, 10 };

System.out.println("Values Before the sort:\n");
for (i = 0; i < array.length; i++){
System.out.print(array[i] + "  ");
}

System.out.println();

bidirectionalBubble_srt(array, array.length);

System.out.print("Values after the sort:\n");

for (i = 0; i < array.length; i++){
System.out.print(array[i] + "  ");
}

}

public static void bidirectionalBubble_srt(int array[], int n) {
int j;
int st = -1;
while (st < n) {
st++;
n--;
for (j = st; j < n; j++) {
if (array[j] > array[j + 1]) {
int T = array[j];
array[j] = array[j + 1];
array[j + 1] = T;
}
}
for (j = n; --j >= st;) {
if (array[j] > array[j + 1]) {
int T = array[j];
array[j] = array[j + 1];
array[j + 1] = T;
}
}
}
}
}


Values Before the sort:

12  9  4  99  120  1  3  10

Values after the sort:

1  3  4  9  10  12  99  120

BubbleSort Algorithmn in Java ?

public class BubbleSort {

public static void main(String a[]) {

int i;
int array[] = { 12, 9, 4, 99, 120, 1, 3, 10 };

System.out.println("Values Before the sort:\n");

for (i = 0; i < array.length; i++) {
System.out.print(array[i] + "  ");
}
System.out.println();

bubble_srt(array, array.length);

System.out.print("Values after the sort:\n");

for (i = 0; i < array.length; i++) {
System.out.print(array[i] + "  ");
}
}

public static void bubble_srt(int a[], int n) {
int i, j, t = 0;
for (i = 0; i < n; i++) {
for (j = 1; j < (n - i); j++) {
if (a[j - 1] > a[j]) {
t = a[j - 1];
a[j - 1] = a[j];
a[j] = t;
}
}
}
}
}

Below is the output.....

Values Before the sort:

12  9  4  99  120  1  3  10  

Values after the sort:

1  3  4  9  10  12  99  120  

Generate array of random numbers with quickSort in Java?

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class QuickSort {
/**
* Main method.
* @param args
*/
public static void main(String[] args) {

QuickSort app = new QuickSort();

//Generate an integer array of length 7
   List<Integer> input = app.generateRandomNumbers(7);

   //Before sort
   System.out.println(input);

   //After sort
   System.out.println(app.quicksort(input));

}

/**
* This method sort the input ArrayList using quick sort algorithm.
* @param input the ArrayList of integers.
* @return sorted ArrayList of integers.
*/
private List<Integer> quicksort(List<Integer> input){

if(input.size() <= 1){
return input;
}

int middle = (int) Math.ceil((double)input.size() / 2);
int pivot = input.get(middle);

List<Integer> less = new ArrayList<Integer>();
List<Integer> greater = new ArrayList<Integer>();

for (int i = 0; i < input.size(); i++) {
if(input.get(i) <= pivot){
if(i == middle){
continue;
}
less.add(input.get(i));
}
else{
greater.add(input.get(i));
}
}

return concatenate(quicksort(less), pivot, quicksort(greater));
}

/**
* Join the less array, pivot integer, and greater array
* to single array.
* @param less integer ArrayList with values less than pivot.
* @param pivot the pivot integer.
* @param greater integer ArrayList with values greater than pivot.
* @return the integer ArrayList after join.
*/
private List<Integer> concatenate(List<Integer> less, int pivot, List<Integer> greater){

List<Integer> list = new ArrayList<Integer>();

for (int i = 0; i < less.size(); i++) {
list.add(less.get(i));
}

list.add(pivot);

for (int i = 0; i < greater.size(); i++) {
list.add(greater.get(i));
}

return list;
}

/**
* This method generate a ArrayList with length n containing random integers .
* @param n the length of the ArrayList to generate.
* @return ArrayList of random integers with length n.
*/
private List<Integer> generateRandomNumbers(int n){

   List<Integer> list = new ArrayList<Integer>(n);
   Random random = new Random();

   for (int i = 0; i < n; i++) {
   list.add(random.nextInt(n * 10));
   }

   return list;
}
}

Below is the output....


[25, 58, 65, 19, 59, 8, 39]
[8, 19, 25, 39, 58, 59, 65]

QuickSort algorithm Java?

public class QuickSort {

public static void main(String a[]) {

int i;
int array[] = { 12, 9, 4, 99, 120, 1, 3, 10, 13 };

System.out.println("Values Before the sort:\n");
for (i = 0; i < array.length; i++){
System.out.print(array[i] + "  ");
}


quick_srt(array, 0, array.length - 1);
System.out.println("");
System.out.print("Values after the sort:\n");

for (i = 0; i < array.length; i++){
System.out.print(array[i] + "  ");
}
}

public static void quick_srt(int array[], int low, int n) {
int lo = low;
int hi = n;
if (lo >= n) {
return;
}
int mid = array[(lo + hi) / 2];
while (lo < hi) {
while (lo < hi && array[lo] < mid) {
lo++;
}
while (lo < hi && array[hi] > mid) {
hi--;
}
if (lo < hi) {
int T = array[lo];
array[lo] = array[hi];
array[hi] = T;
}
}
if (hi < lo) {
int T = hi;
hi = lo;
lo = T;
}
quick_srt(array, low, lo);
quick_srt(array, lo == low ? lo + 1 : lo, n);
}
}

Below is the output.....


Values Before the sort:

12  9  4  99  120  1  3  10  13

Values after the sort:

1  3  4  9  10  12  13  99  120

Dijkstra's (Shortest path) algorithm in Java?

Below is the example to find out the shortest path between edges......


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

public class Dijkstra {
public static void computePaths(Vertex source) {
source.minDistance = 0.;
PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
vertexQueue.add(source);

while (!vertexQueue.isEmpty()) {
Vertex u = vertexQueue.poll();

// Visit each edge exiting u
for (Edge e : u.adjacencies) {
Vertex v = e.target;
double weight = e.weight;
double distanceThroughU = u.minDistance + weight;
if (distanceThroughU < v.minDistance) {
vertexQueue.remove(v);
v.minDistance = distanceThroughU;
v.previous = u;
vertexQueue.add(v);
}
}
}
}

public static List<Vertex> getShortestPathTo(Vertex target) {
List<Vertex> path = new ArrayList<Vertex>();
for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
path.add(vertex);
Collections.reverse(path);
return path;
}

public static void main(String[] args) {
MinimumWindow a = new MinimumWindow();

Vertex v0 = a.new Vertex("Redvile");
Vertex v1 = a.new Vertex("Blueville");
Vertex v2 = a.new Vertex("Greenville");
Vertex v3 = a.new Vertex("Orangeville");
Vertex v4 = a.new Vertex("Purpleville");

v0.adjacencies = new Edge[] { a.new Edge(v1, 5), a.new Edge(v2, 10),a.new Edge(v3, 8) };
v1.adjacencies = new Edge[] { a.new Edge(v0, 5), a.new Edge(v2, 3),a.new Edge(v4, 7) };
v2.adjacencies = new Edge[] { a.new Edge(v0, 10), a.new Edge(v1, 3) };
v3.adjacencies = new Edge[] { a.new Edge(v0, 8), a.new Edge(v4, 2) };
v4.adjacencies = new Edge[] { a.new Edge(v1, 7), a.new Edge(v3, 2) };
Vertex[] vertices = { v0, v1, v2, v3, v4 };

computePaths(v0);

for (Vertex v : vertices) {
System.out.println("Distance to " + v + ": " + v.minDistance);
List<Vertex> path = getShortestPathTo(v);
System.out.println("Path: " + path);
}
}

public class Vertex implements Comparable<Vertex> {

public final String name;
public Edge[] adjacencies;
public double minDistance = Double.POSITIVE_INFINITY;
public Vertex previous;

public Vertex(String argName) {
name = argName;
}

public String toString() {
return name;
}

public int compareTo(Vertex other) {
return Double.compare(minDistance, other.minDistance);
}
}

class Edge {
public final Vertex target;
public final double weight;

public Edge(Vertex argTarget, double argWeight) {
target = argTarget;
weight = argWeight;
}
}
}



Below is the output...


Distance to Redvile: 0.0
Path: [Redvile]
Distance to Blueville: 5.0
Path: [Redvile, Blueville]
Distance to Greenville: 8.0
Path: [Redvile, Blueville, Greenville]
Distance to Orangeville: 8.0
Path: [Redvile, Orangeville]
Distance to Purpleville: 10.0
Path: [Redvile, Orangeville, Purpleville]

How to find the length of longest subString from Java String ?

Below is the example for finding out the longest subString with no repetition in java subString.........

public class LongestSubStringWithNoRepetition {

public static void main(String args[]) {

int x = lengthOfLongestSubstringNoRepetitions("Hi, this is a tesgft string.jgdfgdfkhfjrestjkbngfld ");
System.out.println(""+x);

}

public static int lengthOfLongestSubstringNoRepetitions(String s) {

   if (s == null)
       return 0;

   // Trimming input even for the non-empty case is more consistent.
   final String str = s.trim();

   if (str.equals(""))
       return 0;

   int seen[] = new int[Character.MAX_VALUE+1];
   for (int i = 0; i <= Character.MAX_VALUE; ++i)
       seen[i] = -1;

   int max = 1;
   int len = 0;

   for (int j = 0; j < str.length(); ++j) {
       char ch = str.charAt(j);
       // If ch was recently seen,
       // counting must restart after the last place it was seen.
       // Otherwise, it adds 1 to the length.
       len = Math.min(j-seen[ch], len+1);
       if (len > max)
           max = len;
       seen[ch] = j;
   }
   return max;
}

}

Below is the output........

12

How to find Minimum Window subString from Java String ?

Below is the example for finding the minimum window subString from Java String........


public class MinimumWindow {

public static void main(String args[]) {

Vector<Character> set = new Vector<Character>();
set.add('t');
set.add('i');
set.add('s');
set.add('t');
String x = minWindow("Hi, this is a test string ", set);
System.out.println(x);

}

public static String minWindow(String s, Vector<Character> charset) {
int n = charset.size();
int startindex = 0;
int endindex = n - 1;

Map<Character, Integer> CharSet = new HashMap<Character, Integer>();
for (Character c : charset) {
if (CharSet.containsKey(c)) {
int val = CharSet.get(c);
CharSet.put(c, val + 1);
} else
CharSet.put(c, 1);
}

int end = 0, start = 0;
for (; end < s.length() && n > 0; ++end) {
if (CharSet.containsKey(s.charAt(end))) {
int val = CharSet.get(s.charAt(end));
CharSet.put(s.charAt(end), val - 1);
if (val - 1 >= 0)
--n;
}
}
while (!CharSet.containsKey(s.charAt(start)))
++start;

int min_length = end - start + 1;
startindex = start;
endindex = end - 1;
System.out.println(startindex + " " + endindex);

for (; end < s.length(); ++end) {

if (CharSet.containsKey(s.charAt(end))) {
int val = CharSet.get(s.charAt(end));
CharSet.put(s.charAt(end), val - 1);
// System.out.println("E"+start+" "+end);

while (!CharSet.containsKey(s.charAt(start))
|| CharSet.get(s.charAt(start)) < 0) {

if (CharSet.containsKey(s.charAt(start))
&& CharSet.get(s.charAt(start)) < 0) {
val = CharSet.get(s.charAt(start));
CharSet.put(s.charAt(start), val + 1);
}
++start;
}

int currentLength = end - start + 1;
if (currentLength < min_length) {
min_length = currentLength;
startindex = start;
endindex = end;
}
System.out.println("S----"+start+" "+end);
}
}

System.out.println(startindex + " " + endindex);
return s.substring(startindex, endindex + 1);
}

}



Below is the output.....


1 14
S----4 16
S----9 17
S----9 19
S----9 20
S----17 22
17 22
t stri