アルゴリズムベース

1.共通コード

1.1 character to integer

char c ='1';
int number = Character.getNumericValue(c);

1.2逆転数

public static int reverse(int n) {
  int reverse = 0;
  while(n != 0) {
    reverse *= 10;
    reverse += (n % 10);
    n = n / 10;
  }
  return reverse;
}

1.3逆転文字列

// 추가 공간을 사용하지 않는 방법 
public static String reverseString(String original) {
  char[] chs = original.toCharArray();
  int length = chs.length;
	    
  for(int i=0; i<length/2; i++) {
    // swap characters
    char tmp = chs[i];
    chs[i] = chs[length-1-i];
    chs[length-1-i] = tmp;
  }
  return new String(chs);
}

// 추가 공간을 사용 하는 방법
public static String reverseString(Strign original) {
  char[] chs = original.toCharArray();
  char[] result = new char[chs.length];
  
  for(int i=0; i<chs.length - 1; i++) {
    result[i] = chs[chs.length - i - 1];
  }
  return new String(result);
}

1.4 Swap

// 기본 스왑 
public void swap(int x, int y) {
  int tmp = x;
  x = y;
  y = tmp;
}

// XOR을 사용한 스왑 
// (피연산자의 수가 서로 다를 경우에만 1인 XOR의 성질을 이용해서 2진수로 풀어 계산 해보면 된다.)
public void swap(int x, int y) {
  x = x ^ y;
  y = x ^ y;
  x = x ^ y;
}

2.並べ替え

2.1 Quick sort

    public static void quickSort(int[] arr, int low, int high) {
         if(low >= high) return;
         
         // pick the pivot
         int middle = low + (high - low) / 2;
         int pivot = arr[middle];
         
         // make left < pivot and right > pivot
         int i = low, j = high;
         while(i <= j) {
             while(arr[i] < pivot) {
                 i++;
             }
             while(arr[j] > pivot) {
                 j--;
             }
             if(i <= j) {
                 // swapping
                 int tmp = arr[i];
                 arr[i] = arr[j];
                 arr[k] = tmp;
                 i++;
                 j--;
             }
         }
         if(low < j) {
             quickSort(arr, low, j);
         }
         if(high > i) {
             quickSort(arr, i, high);
         }
     }

 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));
	}
	
	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;
	}

2.2連結ソート

public class Mergesort {
        private int[] numbers;
        private int[] helper;

        private int number;

        public void sort(int[] values) {
                this.numbers = values;
                number = values.length;
                this.helper = new int[number];
                mergesort(0, number - 1);
        }

        private void mergesort(int low, int high) {
                // check if low is smaller then high, if not then the array is sorted
                if (low < high) {
                        // Get the index of the element which is in the middle
                        int middle = low + (high - low) / 2;
                        // Sort the left side of the array
                        mergesort(low, middle);
                        // Sort the right side of the array
                        mergesort(middle + 1, high);
                        // Combine them both
                        merge(low, middle, high);
                }
        }

        private void merge(int low, int middle, int high) {
                // Copy both parts into the helper array
                for (int i = low; i <= high; i++) {
                        helper[i] = numbers[i];
                }

                int i = low;
                int j = middle + 1;
                int k = low;
                // Copy the smallest values from either the left or the right side back
                // to the original array
                while (i <= middle && j <= high) {
                        if (helper[i] <= helper[j]) {
                                numbers[k] = helper[i];
                                i++;
                        } else {
                                numbers[k] = helper[j];
                                j++;
                        }
                        k++;
                }
                // Copy the rest of the left side of the array into the target array
                while (i <= middle) {
                        numbers[k] = helper[i];
                        k++;
                        i++;
                }
        }
}

3.探索

3.1優先ナビゲーション幅（BFS）

public static void bfs(int[][] mat, int startVertex) {
  Queue<Integer> queue = new LinkedList<>();
  boolean[] visited = new boolean[mat[startVertex].length];

  visited[startVertex] = true;
  queue.add(startVertex);

  int e = 0, i = 0;
  while(!queue.isEmpty()) {
    e = queue.remove();
    i = e;
    while(i <= mat[startVertex].length) {
      if(mat[e][i] == 1 && !visited[i]) {
        queue.add(i);
        visited[i] = true;
      }
      i++;
    }
  }
}

3.2 DFS（深度優先ナビゲーション）

 int map[][], visit[];

void dfs(int vertexSize, int v) { 
  int i;
  visit[v] = 1; // root node
  for(i=1; i<=vertexSize; i++) {
    if(map[v][i] == 1 && !visit[i]) {
      dfs(i);
    }
  }
}