zhuyu.deng
BAN USERbeautiful code ...
- zhuyu.deng July 11, 2013apply a quickSort() or heapSort()
- zhuyu.deng July 10, 2013u can reduce your algo to O(N) time complexity...
- zhuyu.deng July 10, 2013package com.zhuyu_deng.test;
import java.util.Stack;
public class Test
{
private static void printMatrix(char[][] a)
{
for (int i = 0; i < a.length; ++i)
{
for (int j = 0; j < a[i].length; ++j)
{
System.out.print(a[i][j] + " ");
}
System.out.println();
}
}
private static void floodFill(char[][] a, int x, int y)
{
class Node
{
public Node(int x, int y)
{
this.x = x;
this.y = y;
}
int x;
int y;
}
char orgColor = a[x][y];
char revColor = a[x][y] == 'W' ? 'B' : 'W';
int size = 0;
Node stack[] = new Node[a.length * a[0].length];
stack[size] = new Node(x, y);
while (size >= 0)
{
Node cur = stack[size];
size--;
a[cur.x][cur.y] = revColor;
if (cur.x - 1 >= 0 && orgColor == a[cur.x - 1][cur.y])
{
stack[++size] = (new Node(cur.x-1, cur.y));
}
if (cur.x + 1 < a.length && orgColor == a[cur.x + 1][cur.y])
{
stack[++size] = (new Node(cur.x+1, cur.y));
}
if (cur.y - 1 >= 0 && orgColor == a[cur.x][cur.y - 1])
{
stack[++size] = (new Node(cur.x, cur.y-1));
}
if (cur.y + 1 < a[0].length && orgColor == a[cur.x][cur.y + 1])
{
stack[++size] = (new Node(cur.x, cur.y + 1));
}
}
}
public static void main(String args[])
{
// int[] a = {-2,11,-4,13,-5,-2};
int[][] b = { { 0, -2, -7, 0 }, { 9, 2, -6, 2 }, { -4, 1, -4, 1 },
{ -1, 8, 0, -2 } };
int[][] matrix = { { 2, 3, 4, 1 }, { 1, 1, 3, 9 }, { 2, 2, 3, 1 },
{ 2, 2, 3, 1 } };
char a[][] = new char[][] { { 'W', 'B', 'W', 'W', 'B', 'W' },
{ 'B', 'B', 'W', 'W', 'B', 'W' },
{ 'W', 'B', 'B', 'B', 'W', 'B' },
{ 'W', 'B', 'W', 'W', 'B', 'B' } };
printMatrix(a);
floodFill(a, 2, 2);
System.out.println();
printMatrix(a);
}
}
Thanx........
- zhuyu.deng July 09, 2013package com.zhuyu_deng.test;
public class Test
{
static int a[] = new int[] { 3, 2, 1, 6, 5, 4, 9, 8, 7 };
static int c[] = new int[a.length];
public static void main(String args[])
{
int b[] = new int[a.length];
for (int i = 0; i < b.length; ++i)
b[i] = 1;
for (int i = 1; i < a.length; ++i)
{
int maxLen = 1;
for (int j = 0; j < i; ++j)
{
if (a[j] < a[i] && b[j] + 1 > maxLen)
{
maxLen = b[j] + 1;
b[i] = maxLen;
c[i] = j;
}
if (maxLen >= 3)
break;
}
if (maxLen >= 3)
{
print(i);
System.out.println();
break;
}
}
}
private static void print(int x)
{
if (x != 0)
{
print(c[x]);
System.out.print(a[x] + " ");
} else
{
System.out.print(a[x] + " ");
}
}
}
main idea: rotate each matrix's edge from outer to inner.
time efficience is O(n^2).
private static int findMinDifNum(int[] a, int n)
{
if (a.length == 1)
return a[0];
else if (a[0] > n)
{
return a[0];
}
else if (a[a.length-1] < n)
{
return a[a.length-1];
}else if (a.length == 2)
{
return n - a[0] > a[1] - n ? a[1] : a[0];
}
int left = 0;
int right = a.length - 1;
int mid = 0;
while (left <= right)
{
mid = (left + right) / 2;
if (a[mid] < n)
left = mid + 1;
else if (a[mid] > n)
right = mid - 1;
else
break;
}
if (left <= right)
return a[mid];
if (a[mid] < n)
{
return n-a[mid] > a[mid+1] - n ? a[mid+1] : a[mid];
}
else
{
return a[mid] - n > n - a[mid-1] ? a[mid-1] : a[mid];
}
}
Thanks for your idea.
- zhuyu.deng July 08, 2013public class subSet
{
public Object a;
public int n;
public int[] x;
public boolean flag;
private int c;
public subSet(int[] a, int c)
{
this.a = a;
this.c = c;
this.n = a.length;
this.flag = false;
this.x = new int[n];
}
public boolean isPartial(int k)
{
int sum = 0;
for (int i = 0; i < k; i++)
sum += ((int[]) (a))[i] * x[i];
return sum <= c;
}
public boolean isComplete(int k)
{
int sum = 0;
if (k >= n)
{
for (int i = 0; i < n; i++)
sum += ((int[]) (a))[i] * x[i];
}
return sum == c;
}
public void printSolution(int k)
{
for (int i = 0; i < n; i++)
if (x[i] == 1)
System.out.print(((int[]) (a))[i] + " ");
System.out.println();
}
public static void backtrack(subSet p)
{
explore(p, 0);
if (!p.flag)
System.out.println("no sulution!");
}
private static void explore(subSet p, int k)
{
if (k >= p.n)
{
if (p.isComplete(k))
{
p.flag = true;
p.printSolution(k);
}
return;
}
for (int i = 0; i < 2; i++)
{
p.x[k] = i;
if (p.isPartial(k))
explore(p, k + 1);
}
}
public static void main(String args[])
{
int b[] = { 1, 2, 3, 4 };
subSet t = new subSet(b, 6);
t.backtrack(t);
}
}
public class subSet
{
public Object a;
public int n;
public int[] x;
public boolean flag;
private int c;
public subSet(int[] a, int c)
{
this.a = a;
this.c = c;
this.n = a.length;
this.flag = false;
this.x = new int[n];
}
public boolean isPartial(int k)
{
int sum = 0;
for (int i = 0; i < k; i++)
sum += ((int[]) (a))[i] * x[i];
return sum <= c;
}
public boolean isComplete(int k)
{
int sum = 0;
if (k >= n)
{
for (int i = 0; i < n; i++)
sum += ((int[]) (a))[i] * x[i];
}
return sum == c;
}
public void printSolution(int k)
{
for (int i = 0; i < n; i++)
if (x[i] == 1)
System.out.print(((int[]) (a))[i] + " ");
System.out.println();
}
public static void backtrack(subSet p)
{
explore(p, 0);
if (!p.flag)
System.out.println("no sulution!");
}
private static void explore(subSet p, int k)
{
if (k >= p.n)
{
if (p.isComplete(k))
{
p.flag = true;
p.printSolution(k);
}
return;
}
for (int i = 0; i < 2; i++)
{
p.x[k] = i;
if (p.isPartial(k))
explore(p, k + 1);
}
}
public static void main(String args[])
{
int b[] = { 1, 2, 3, 4 };
subSet t = new subSet(b, 6);
t.backtrack(t);
}
}
learn a lot from your answers.
main idea is : left smaller and right bigger than parent.
what u changed for the algo is wrong......:)
- zhuyu.deng July 11, 2013u can check your code....thanx