The Towers of Hanoi problem TowerHanoi.java
public static void moveTowerHanoi(int n) {List<LinkedList<Integer>> pegs = new ArrayList<>();
for (int i = 0; i < 3; i++) {
pegs.add(new LinkedList<Integer>());
}
// Initialize pegs.
for (int i = n; i >= 1; --i) {
pegs.get(0).push(i);
}
transfer(n, pegs, 0, 1, 2);
}
private static void transfer(int n, List<LinkedList<Integer>> pegs,
int from, int to, int use) {
if (n > 0) {
transfer(n - 1, pegs, from, use, to);
pegs.get(to).push(pegs.get(from).pop());
System.out.println("Move from peg " + from + " to peg " + to);
transfer(n - 1, pegs, use, to, from);
}
}
Implement regular expression matchingRegularExpression.java
public static boolean isMatch(String r, String s) {
// Case (2.) : starts with '^'.
if (r.charAt(0) == '^') {
return isMatchHere(r.substring(1), s);
}
for (int i = 0; i <= s.length(); ++i) {
if (isMatchHere(r, s.substring(i))) {
return true;
}
}
return false;
}
private static boolean isMatchHere(String r, String s) {
// Case (1.)
if (r.isEmpty()) {
return true;
}
// Case (2) : ends with '$'.
if ("$".equals(r)) {
return s.isEmpty();
}
// Case (4.)
if (r.length() >= 2 && r.charAt(1) == '*') {
for (int i = 0; i < s.length()
&& (r.charAt(0) == '.' || r.charAt(0) == s.charAt(i)); ++i) {
if (isMatchHere(r.substring(2), s.substring(i + 1))) {
return true;
}
}
return isMatchHere(r.substring(2), s);
}
// Case (3.)
return !s.isEmpty() && (r.charAt(0) == '.' || r.charAt(0) == s.charAt(0))
&& isMatchHere(r.substring(1), s.substring(1));
}
Enumerate all nonattacking placements of n-Queens NQueens.java
public static List<List<String>> nQueens(int n) {int[] placement = new int[n];
List<List<String>> result = new ArrayList<>();
nQueensHelper(n, 0, placement, result);
return result;
}
private static void nQueensHelper(int n, int row, int[] colPlacement,
List<List<String>> result) {
if (row == n) {
result.add(createOutput(colPlacement));
} else {
for (int col = 0; col < n; ++col) {
colPlacement[row] = col;
if (isFeasible(colPlacement, row)) {
nQueensHelper(n, row + 1, colPlacement, result);
}
}
}
}
private static List<String> createOutput(int[] colPlacement) {
List<String> sol = new ArrayList<>();
for (int aColPlacement : colPlacement) {
char[] line = new char[colPlacement.length];
Arrays.fill(line, '.');
line[aColPlacement] = 'Q';
sol.add(new String(line));
}
return sol;
}
private static boolean isFeasible(int[] colPlacement, int row) {
for (int i = 0; i < row; ++i) {
int diff = Math.abs(colPlacement[i] - colPlacement[row]);
if (diff == 0 || diff == row - i) {
return false;
}
}
return true;
}
Enumerate permutations PermutationsAlternative.java
public static List<List<Integer>> permutations(List<Integer> A) {
List<List<Integer>> result = new ArrayList<>();
permutationsHelper(0, A, result);
return result;
}
private static void permutationsHelper(int i, List<Integer> A,
List<List<Integer>> result) {
if (i == A.size()) {
result.add(new ArrayList<>(A));
return;
}
for (int j = i; j < A.size(); ++j) {
Collections.swap(A, i, j);
permutationsHelper(i + 1, A, result);
Collections.swap(A, i, j);
}
}
