Algorithm in Java

一 One

SelectionSort.java (Selection Sort)

• Given an array of integers, sort the elements in the array in ascending order. The selection sort algorithm should be used to solve this problem.
  • {1} is sorted to {1}
  • {1, 2, 3} is sorted to {1, 2, 3}
  • {3, 2, 1} is sorted to {1, 2, 3}
  • {4, 2, -3, 6, 1} is sorted to {-3, 1, 2, 4, 6}

MergeSort.java (Merge Sort)

• Given an array of integers, sort the elements in the array in ascending order. The merge sort algorithm should be used to solve this problem.
  • {1} is sorted to {1}
  • {1, 2, 3} is sorted to {1, 2, 3}
  • {3, 2, 1} is sorted to {1, 2, 3}
  • {4, 2, -3, 6, 1} is sorted to {-3, 1, 2, 4, 6}

QuickSort.java (Quick Sort)

• Given an array of integers, sort the elements in the array in ascending order. The quick sort algorithm should be used to solve this problem.
  • {1} is sorted to {1}
  • {1, 2, 3} is sorted to {1, 2, 3}
  • {3, 2, 1} is sorted to {1, 2, 3}
  • {4, 2, -3, 6, 1} is sorted to {-3, 1, 2, 4, 6}

RainbowSort.java (Rainbow Sort)

• Given an array of balls, where the color of the balls can only be Red, Green or Blue, sort the balls such that all the Red balls are grouped on the left side, all the Green balls are grouped in the middle and all the Blue balls are grouped on the right side. (Red is denoted by -1, Green is denoted by 0, and Blue is denoted by 1).
  • {0} is sorted to {0}
  • {1, 0} is sorted to {0, 1}
  • {1, 0, 1, -1, 0} is sorted to {-1, 0, 0, 1, 1}

Move0s.java (Move 0s To The End I)

• Given an array of integers, move all the 0s to the right end of the array. The relative order of the elements in the original array does not need to be maintained.
  • {1} –> {1}
  • {1, 0, 3, 0, 1} –> {1, 3, 1, 0, 0} or {1, 1, 3, 0, 0} or {3, 1, 1, 0, 0}

二 Two

FibonacciNumber.java (Fibonacci Number)

• Get the Kth number in the Fibonacci Sequence. (K is 0-indexed, the 0th Fibonacci number is 0 and the 1st Fibonacci number is 1).
  • 0th fibonacci number is 0
  • 1st fibonacci number is 1
  • 2nd fibonacci number is 1
  • 3rd fibonacci number is 2
  • 6th fibonacci number is 8

Power.java (a to the power of b)

• Evaluate a to the power of b, assuming both a and b are integers and b is non-negative.
  • power(2, 0) = 1
  • power(2, 3) = 8
  • power(0, 10) = 0
  • power(-2, 5) = -32

BinarySearch.java (Classical Binary Search)

• Given a target integer T and an integer array A sorted in ascending order, find the index i such that A[i] == T or return -1 if there is no such index.
  • A = {1, 2, 3, 4, 5}, T = 3, return 2
  • A = {1, 2, 3, 4, 5}, T = 6, return -1
  • A = {1, 2, 2, 2, 3, 4}, T = 2, return 1 or 2 or 3

FirstOccur.java (First Occurrence)

• Given a target integer T and an integer array A sorted in ascending order, find the index of the first occurrence of T in A or return -1 if there is no such index.
  • A = {1, 2, 3}, T = 2, return 1

LastOccur.java (Last Occurrence)

• Given a target integer T and an integer array A sorted in ascending order, find the index of the last occurrence of T in A or return -1 if there is no such index.
  • A = {1, 2, 3}, T = 2, return 1
  • A = {1, 2, 3}, T = 4, return -1
  • A = {1, 2, 2, 2, 3}, T = 2, return 3

Closest.java (Closest In Sorted Array)

• Given a target integer T and an integer array A sorted in ascending order, find the index i in A such that A[i] is closest to T.
  • A = {1, 2, 3}, T = 2, return 1
  • A = {1, 4, 6}, T = 3, return 1
  • A = {1, 4, 6}, T = 5, return 1 or 2
  • A = {1, 3, 3, 4}, T = 2, return 0 or 1 or 2

KClosest.java (K Closest In Sorted Array)

• Given a target integer T, a non-negative integer K and an integer array A sorted in ascending order, find the K closest numbers to T in A.
  • A = {1, 2, 3}, T = 2, K = 3, return {2, 1, 3} or {2, 3, 1}

UnknownSizeBinarySearch.java (Search In Unknown Sized Sorted Array)

• Given a integer dictionary A of unknown size, where the numbers in the dictionary are sorted in ascending order, determine if a given target integer T is in the dictionary. Return the index of T in A, return -1 if T is not in A.
  • A = {1, 2, 5, 9, ......}, T = 5, return 2
  • A = {1, 2, 5, 9, 12, ......}, T = 7, return -1

SearchInSortedMatrix.java (Search In Sorted Matrix I)

• Given a 2D matrix that contains integers only, which each row is sorted in an ascending order. The first element of next row is larger than (or equal to) the last element of previous row.
• Given a target number, returning the position that the target locates within the matrix. If the target number does not exist in the matrix, return {-1, -1}.
  • matrix = { {1, 2, 3}, {4, 5, 7}, {8, 9, 10} }
  • target = 7, return {1, 2}
  • target = 6, return {-1, -1} to represent the target number does not exist in the matrix.