sqw
BAN USERRound-robin algorithm:
public class GameSchedule {
public static void scheduleGames(int nmb) {
int days = (nmb % 2 == 0) ? nmb -1 : nmb;
for (int i=0; i<days; i++) {
System.out.println("\tDay " + (i+1) + ":");
for (int j=0; j<nmb/2; j++) {
int t1 = (j+i) % nmb + 1;
int t2 = ((nmb - j -1) + i) % nmb + 1;
System.out.println("\t\tTeam " + t1 + " v.s Team " + t2);
}
}
}
public static void main(String[] args) {
for (int i=1; i<12; i++) {
System.out.println("Schedule for " + i + " teams:");
GameSchedule.scheduleGames(i);
}
}
}
Assume that 1) the size of file A > the size of file B; 2) the size of each is too big to be loaded into Memory; the Memory only allows N numerb of integers.
do while() {
read N integers from A into the Hashtable in memory, if no more integer available, break;
read each integer from B, check if it is in the Hashtable. if yes, write it into the output file C
}
O(B*A/N)
static int getNumberOfPrime(int N) {
int count = 0;
for (int i=2; i<=N; i++) {
int max = (int)Math.sqrt(i);
boolean prime = true;
for (int j=2; j<=max; j++) {
if (i%j == 0 && i != j) {
prime = false;
break;
}
}
if (prime) {
count++;
System.out.print(i + ",");
}
}
return count;
}
I am trying to prove that the following algorithm is correct by MI (Mathematical Induction):
Let K = the number of numbers in the input stream.
1. when K=1, returns the first number M.
2. when K=n-1, assume that a number M is selected from the n-1 numbers with equal oppertunity.
3. For K=n, we give an oppertunity of 1/n to select the current number to replace M, so that the previous selected number M has an oppertunity of (n-1)/n. Wicth means that the oppertunity of (n-1)/n is evently distributed to the previous n-1 numbers, each of the numbers has 1/n oppertunity.
Implementation in Java:
public static String getRandomNumber(String filename) {
BufferedReader inputStream = null;
int count = 0;
String nmb = "";
Random r = new Random();
try {
inputStream = new BufferedReader(new FileReader(filename));
String line;
while ((line = inputStream.readLine()) != null) {
count++;
int tmp = r.nextInt(count);
if (tmp == 0) {
nmb = line;
}
}
} catch (IOException e) {
System.out.println(e.getMessage());
}
return nmb;
}
1. use first as a bit map: bit 0 - there is 1's in column 0; bit 1 - there is 1's in row 0.
2. for each arr(i,j), where i,j > 0, if it is 1, set arr(0,j) and arr(i,0) to 1.
3. for each arr(i,j), where i,j > 0, if arr(0,j) or arr(i,0) is 1, set it to 1.
4. if bit 0 in first is 1, set all the elements in the column 0 to 1; if bit 1 in first 1, set all the elements in the row 0 to 1.
5. print out the 2d array.
O(2n*m) time and O(1) space
int[][] arr= new int[][] {{0,1,0,0}, {0,1,0,0}, {0,0,0,0}, {1,0,0,0}, {0,1,1,0}};
int first = 0;
for (int i = 0; i<arr[0].length; i++)
if (arr[0][i] == 1) first |= 1;
for (int i = 0; i<arr.length; i++)
if (arr[i][0] == 1) first |= 2;
for (int row = 1; row < arr.length; row++) {
for (int col = 1; col < arr[0].length; col++) {
if (arr[row][col]==1) {
arr[0][col] = 1;
arr[row][0] = 1;
}
}
}
for (int i=1; i<arr.length; i++) {
for (int j=1; j<arr[0].length; j++) {
if (arr[0][j] == 1 || arr[i][0] == 1) arr[i][j] = 1;
}
}
if ((first & 1) != 0) for (int i = 0; i<arr[0].length; i++) arr[0][i] = 1;
if ((first & 2) != 0) for (int i = 1; i<arr.length; i++) arr[i][0] = 1;
for (int i=0; i<arr.length; i++) {
for (int j=0; j<arr[0].length; j++) {
System.out.print(arr[i][j] + ",");
}
System.out.println();
}
public static void printMaxSum(int[] a) {
if (a == null || a.length == 0) return;
int len = a.length;
int max=a[0], maxi=0, maxj=0;
int sum=a[0], i=0;
for (int j=1; j<len; j++) {
if (sum <= 0 || sum + a[j] <= 0) {
sum = a[j];
i = j;
} else {
sum += a[j];
}
if (sum > max) {
max = sum;
maxi = i;
maxj = j;
}
}
System.out.println("\nmaxi, maxj, and max are: " + maxi + "," + maxj + "," + max);
}
O(n)
public class CoinChange {
public static void findChanges(int[] d, int sum) {
int[] a = new int[sum+1];
int[] coins = new int[sum+1];
for (int i=0; i<sum+1; i++) a[i] = 0;
int total_den = d.length;
for (int i = 1; i<= sum; i++) {
int min = Integer.MAX_VALUE;
for (int j = 0; j < total_den; j++) {
if (i - d[j] >= 0) {
if (1+a[i-d[j]] < min) {
min = 1+a[i-d[j]];
coins[i] = d[j];
}
}
}
a[i] = min;
}
while (sum > 0) {
System.out.print(coins[sum] + ",");
sum = sum - coins[sum];
}
System.out.println();
}
public static void main(String[] args) {
int[] den = {1, 4, 5, 20};
findChanges(den, 58);
}
1. let M = x2-x1 and N = y2-y1.
2. from (x1, y1) you need M rights and N ups to reach the destination (x2, y2)
3. assume that M is 2 and N is 3, the path is a "multiset" (RRUUU). (R-move right, U-move up)
4. so the number of distinctive paths is the number of permutation of the multiset (RRUUU), which is 10.
RRUUU
RUUUR
URRUU
URUUR
:
:
5. in general, the answer is (M+N)!/(M!*N!)
ram,
1) treat the n*n numbers as an 2D array;
2) to generate a new subset, we need to pick one of number from each row to form a new sequence.
3) starting row 2, we need to pick up a number in a way that would have only one from each other subsets:
i * (k-1) + j
where j is the offset, i*(k-1) is the step distance.
import java.util.*;
public class BinaryMatrix {
class Square {
int size;
int r1;
int r2;
int c1;
int c2;
public Square(int x1, int x2, int y1, int y2) {
r1 = x1; r2 = x2;
c1 = y1; c2 = y2;
size = (r2-r1+1)*(c2-c1+1);
}
public String toString() {
String s;
if (size == 1) s = "{" + r1 + "," + c1 + "}";
else s = "{" + r1 + "," + r2 + "," + c1 + "," + c2 + "}";
return s;
}
}
protected int[][] a;
int rows;
int cols;
public BinaryMatrix(int r, int c) {
rows = r;
cols = c;
a = new int[r][c];
initMatrix();
}
protected void initMatrix() {
Random r = new Random();
for (int i=0; i<rows; i++) {
for (int j=0; j<cols; j++) {
a[i][j] = r.nextInt(2);
}
}
}
public void dumpMatrix() {
for (int i=0; i<rows; i++) {
for (int j=0; j<cols; j++) {
System.out.print(a[i][j]);
}
System.out.println();
}
}
public List<Square> getSquares() {
List<Square> sqlist = new LinkedList<Square>();
for (int i=0; i<rows; i++) {
int s = -1;
int j = 0;
while (true) {
if (j >= cols) {
if (s != -1) addSquare(sqlist, i, s, j-1);
break;
}
if (a[i][j] == 1) {
if (s == -1) { s = j++; continue; }
if (isSquare(i, s, j)) {
j++;
continue;
}
addSquare(sqlist, i, s, j-1);
j = s+1;
s = -1;
} else {
if (s != -1) {
addSquare(sqlist, i, s, j-1);
s = -1;
}
j++;
}
}
}
return sqlist;
}
public void addSquare(List<Square> sqlist, int row, int c1, int c2) {
Square sq = new Square(row, row+(c2-c1), c1, c2);
if (isValidSquare(sqlist, sq)) {
sqlist.add(sq);
}
}
public boolean isSquare(int row, int c1, int c2) {
// 1. single cell is a square
if (c1 == c2) return true;
// 2. assume row, c1, c2-1 is square, now check if row, c1, c2 is a square
int d = c2 - c1;
if (row + d >= rows) return false;
for (int i=1; i<d; i++) {
if (a[row+i][c2] != 1) return false;
}
for (int j=c1; j<=c2; j++) {
if (a[row+d][j] != 1) return false;
}
return true;
}
public boolean isValidSquare(List<Square> sqlist, Square sq) {
//if (sq.size ==1 ) return false;
for (Square s : sqlist) {
if (sq.size < s.size) {
if (sq.r1 >= s.r1 && sq.r2 <= s.r2 && sq.c1 >= s.c1 && sq.c2 <= s.c2) return false;
}
}
return true;
}
public static void main(String[] args) {
BinaryMatrix b = new BinaryMatrix(8, 10);
b.dumpMatrix();
List<Square> sqs = b.getSquares();
System.out.println(sqs);
}
}
0110000111
0000010111
1101111110
0010010111
1100010011
1110011010
1110100100
0111111000
[{0,1}, {0,2}, {0,1,7,8}, {0,1,8,9}, {1,5}, {1,2,7,8}, {2,0}, {2,1}, {2,3}, {2,4}, {2,5}, {2,6}, {2,3,7,8}, {3,2}, {3,5}, {3,4,8,9}, {4,5,0,1}, {4,5}, {5,6,0,1}, {5,6,1,2}, {5,5}, {5,6}, {5,8}, {6,7,1,2}, {6,4}, {6,7}, {7,3}, {7,4}, {7,5}, {7,6}]
public static int findKthValue(int[] a, int[] b, int k) {
int alen = a.length;
int blen = b.length;
int d = k;
if (k > alen + blen) return -1;
if (alen == 0) { return b[k-1]; }
if (blen == 0) { return a[k-1]; }
int i;
int j;
i = k > alen ? alen-1 : k-2;
j = k - i -2;
while (true) {
if (a[i] > b[j]) {
if (j == blen-1 || a[i] <= b[j+1]) return a[i];
if (j+d < blen && i-d > -2) { j += d; i -= d; }
} else {
if (i == alen-1 || b[j] <= a[i+1]) return b[j];
if (i+d < alen && j-d > -2) { i += d; j -= d; }
}
if (i == -1) return b[j];
if (j == -1) return a[i];
d = d/2;
if (d == 0) d = 1;
}
}
O(logK)
public static void print2BSTInorder(Node n1, Node n2) {
Stack<Node> stack1 = new Stack<Node>();
Stack<Node> stack2 = new Stack<Node>();
while (true) {
while (n1 != null) {
stack1.push(n1);
n1 = n1.left;
}
while (n2 != null) {
stack2.push(n2);
n2 = n2.left;
}
if (stack1.isEmpty() && stack2.isEmpty()) break;
if (stack2.isEmpty() || stack1.peek().value < stack2.peek().value) {
n1 = stack1.pop();
System.out.print(n1.value+",");
n1 = n1.right;
} else {
n2 = stack2.pop();
System.out.print(n2.value+",");
n2 = n2.right;
}
}
System.out.println();
}
int permutationTest(int n){
int i, j, k;
printf("n=%d\n", n);
for(i=1; i<=n*n;) {
printf("\n");
for (int j=1; j<=n; j++) {
printf("%3d",i++);
}
}
for (i=0; i<n; i++) {
for (j=0; j<n; j++) {
printf("\n%3d%3d", i+1, n+j+1);
for (k=2; k<n; k++) {
int s = (i*(k-1)+j)%n + 1;
printf("%3d", k*n+s);
}
}
}
return 0;
}
- sqw June 28, 2012