onurraktas
BAN USERpublic class SortedArrayCountN {
public static void main(String[] args) {
int[] A = {1, 1, 2, 3, 3, 3, 4, 5};
System.out.println(count(A, 1, 0, A.length - 1));
}
static int count(int[] A, int n, int lo, int hi) {
if (A == null || A[lo] > n || A[hi] < n) {
return 0;
}
if (A[lo] == A[hi]) {
return hi - lo + 1;
}
int mid = lo + (hi - lo) / 2;
if (A[mid] < n) {
return count(A, n, mid + 1, hi);
} else if (A[mid] > n) {
return count(A, n, lo, mid - 1);
} else {
return 1 + count(A, n, mid + 1, hi)
+ count(A, n, lo, mid - 1);
}
}
}
Simple solution. Once you understand the logic, you can apply to many other problems by
doing some minor changes. (e.g. Maze, Knights Movement, N-Queen, Sudoku etc.)
import java.util.Arrays;
public class MuseumGuardian {
static int[] moveX = {0, 0, 1, -1};
static int[] moveY = {1, -1, 0, 0};
public static void main(String[] args) {
char[][] board =
{
{'.', '#', '.', 'G', 'G'},
{'.', '.', '#', '.', '.'},
{'G', '.', '.', '.', '.'},
{'.', '.', '#', '.', '.'}
};
solve(board);
for (char[] arr : board) {
System.out.println(Arrays.toString(arr));
}
}
/// Helper Methods
static int atoi(char c) {
return c - '0';
}
static char itoa(int n) {
return (char)('0' + n);
}
public static void solve(char[][] A) {
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < A[0].length; j++) {
if (A[i][j] == 'G') {
markNeighbors(A, i, j, 0);
}
}
}
}
public static boolean isSafe(char[][] A, int i, int j, int newValue) {
if (i < 0 || i >= A.length || j < 0 || j >= A[0].length) {
return false;
}
if (A[i][j] == 'G' || A[i][j] == '#') {
return false;
}
if (A[i][j] != '.' && atoi(A[i][j]) <= newValue) {
return false;
}
return true;
}
public static void markNeighbors(char[][] A, int i, int j, int value) {
for (int k = 0; k < moveX.length; k++) {
int nextX = i + moveX[k];
int nextY = j + moveY[k];
if (isSafe(A, nextX, nextY, value + 1)) {
A[nextX][nextY] = itoa(value + 1);
markNeighbors(A, nextX, nextY, value + 1);
}
}
}
}
- onurraktas August 02, 2015