alex
BAN USERpublic static int[] findLocalMimMatrix(int[][] matrix, int startRow, int endRow){
int[] ret = new int[2];
int midRow = startRow + (endRow - startRow) / 2;
int rowMin = matrix[midRow][0];
ret[0] = midRow;
ret[1] = 0;
// Get the minimum value of row (startRow + endRow ) / 2
for(int i = 1; i < matrix[midRow].length; i ++){
if(matrix[midRow][i] < rowMin){
rowMin = matrix[midRow][i];
ret[0] = midRow;
ret[1] = i;
}
}
int upNbr = Integer.MAX_VALUE, downNbr = Integer.MAX_VALUE;
if(midRow - 1 >= startRow){
upNbr = matrix[midRow - 1][ret[1]];
}
if(midRow + 1 <= endRow){
downNbr = matrix[midRow + 1][ret[1]];
}
// Find a local minimum
if(rowMin <= upNbr && rowMin <= downNbr){
return ret;
}else{
// Shrink the matrix into half.
if(upNbr >= downNbr){
ret = findLocalMimMatrix(matrix, midRow + 1, endRow);
}else{
ret = findLocalMimMatrix(matrix, startRow, midRow - 1);
}
return ret;
}
}
The time complexity is O(N*lgN)
- alex December 08, 2013public static void removeAlternateDupChar(String str){
StringBuilder sb = new StringBuilder();
byte[] flag = new byte[128];
for(int i = 0; i < str.length(); i ++){
if(flag[str.charAt(i)] == 0){
flag[Character.toUpperCase(str.charAt(i))] = (byte)1;
flag[Character.toLowerCase(str.charAt(i))] = (byte)1;
sb.append(str.charAt(i));
}else{
flag[Character.toUpperCase(str.charAt(i))] = (byte)0;
flag[Character.toLowerCase(str.charAt(i))] = (byte)0;
}
}
System.out.println(sb.toString());
}
private static class Step{
int x, y;
public Step(int xVal, int yVal){
x = xVal;
y = yVal;
}
@Override
public int hashCode(){
int prime = 31;
int result = 1;
result = result * prime + x;
result = result * prime + y;
return result;
}
@Override
public boolean equals(Object obj){
if(obj == null){
return false;
}
if(this == obj){
return true;
}
if(getClass() != obj.getClass()){
return false;
}
Step step = (Step)obj;
if(step.x != x || step.y != y){
return false;
}
return true;
}
}
public static ArrayList<Step> getAdjSteps(Step curStep, int[][] matrix){
ArrayList<Step> ret = new ArrayList<Step>();
int curX = curStep.x, curY = curStep.y;
if(curX - 1 >= 0){
ret.add(new Step(curX - 1, curY));
}
if(curX + 1 <= matrix.length - 1){
ret.add(new Step(curX + 1, curY));
}
if(curY - 1 >= 0){
ret.add(new Step(curX, curY - 1));
}
if(curY + 1 <= matrix[0].length - 1){
ret.add(new Step(curX, curY + 1));
}
return ret;
}
enum Status {VISITED, UNVISITED};
public static boolean findGreyPath(int[][] matrix){
Map<Step, Status> visited = new HashMap<Step, Status>();
Stack<Step> path = new Stack<Step>();
Step start = new Step(0,0);
Step end = new Step(matrix.length - 1, matrix[0].length - 1);
path.push(start);
visited.put(start, Status.VISITED);
boolean ret = findGreyPathInternal(matrix, path, visited, end);
if(ret){
Step tmpStep = null;
Iterator<Step> ite = path.iterator();
while(ite.hasNext()){
tmpStep = ite.next();
System.out.format("->[%d, %d]", tmpStep.x, tmpStep.y);
}
}
return ret;
}
public static boolean findGreyPathInternal(int[][] matrix, Stack<Step> path, Map<Step, Status> visited, Step exit){
if(!path.isEmpty()){
Step curStep = path.peek();
for(Step s: getAdjSteps(curStep, matrix)){
if(visited.get(s) == null && (matrix[s.x][s.y] == 0 || matrix[s.x][s.y] == 2)){
path.push(s);
visited.put(s, Status.VISITED);
if(s.equals(exit)){
boolean hasGrey = false;
Step tmpStep = null;
Iterator<Step> ite = path.iterator();
while(ite.hasNext()){
tmpStep = ite.next();
if(matrix[tmpStep.x][tmpStep.y] == 2){
hasGrey = true;
}
}
if(hasGrey){
return true;
}
}// end "== exit"
boolean ret = findGreyPathInternal(matrix, path, visited, exit);
if(ret){
return true;
}
}// end if
}// end for-each step
visited.remove(path.pop());
}// end if stack empty
return false;
}
public static void main(String[] args) throws Exception {
int[][] matrix = new int[6][6];
matrix[0] = new int[]{0, 1, 1, 1, 1, 1};
matrix[1] = new int[]{0, 0, 0, 0, 1, 1};
matrix[2] = new int[]{1, 0, 1, 0, 1, 0};
matrix[3] = new int[]{1, 2, 1, 0, 1, 0};
matrix[4] = new int[]{1, 0, 0, 0, 1, 0};
matrix[5] = new int[]{1, 1, 1, 0, 0, 0};
System.out.println(findGreyPath(matrix));
}
Ans: ->[0, 0]->[1, 0]->[1, 1]->[2, 1]->[3, 1]->[4, 1]->[4, 2]->[4, 3]->[5, 3]->[5, 4]->[5, 5]true
- alex December 08, 2013public class RabinKarp {
private String pat; // the pattern string.
private long patHash; // the hash of the pattern
private long Q; // a large prime number, small enough to avoid overflow.
private int M; // pattern string length.
private long RM; // R ^ (M - 1) % Q
private int R; // radix.
public RabinKarp(String pattern){
pat = pattern;
M = pat.length();
R = 256;
Q = longPrimeNumber();
patHash = hash(pat);
RM = 1;
for(int i = 1; i <= M - 1; i ++){
RM = (RM * R) % Q;
}
}
public void search(String txt){
int N = txt.length();
if(N < M){
System.out.println(N);
}
// Compare pattern and first M - character sequence in text string.
long txtHash = hash(txt);
if(patHash == txtHash && check(txt, 0)){
System.out.println(0);
}
for(int i = M; i < N; i ++){
txtHash = (txtHash - RM * txt.charAt(i - M)) % Q;
txtHash = (R * txtHash + txt.charAt(i)) % Q;
if(txtHash == patHash && check(txt, i - M + 1)){
System.out.println(i - M + 1);
}
}
}
// Check if pattern equals the corresponding M - character sequence in text string.
public boolean check(String txt, int offset){
for(int i = 0; i < M; i ++){
if(pat.charAt(i) != txt.charAt(i + offset)){
return false;
}
}
return true;
}
// Get a hash value of a string of length M
public long hash(String key){
long h = 0;
for(int i = 0; i < M; i ++){
h = (R * h + key.charAt(i)) % Q;
}
return h;
}
// Get a 31-bit prime number
public long longPrimeNumber(){
BigInteger probablePrime = BigInteger.probablePrime(31, new Random());
return probablePrime.longValue();
}
/**
* @param args
*/
public static void main(String[] args) {
String pat = "abc";
String txt = "abcddbsabcba";
RabinKarp rk = new RabinKarp(pat);
rk.search(txt);
System.out.println("----------");
StringBuilder sb = new StringBuilder(pat);
RabinKarp rk1 = new RabinKarp(sb.reverse().toString());
rk1.search(txt);
}
}
Rephenryhokinsh, Android test engineer at ABC TECH SUPPORT
I’m Henry, I am Children's librarian in Rolling Thunder .My Work involves the responsibility for supervising the children ...
Repjuliaaperez05, Cloud Support Associate at ABC TECH SUPPORT
I Performed extensive web research to collect pertinent data and gather images related to the assigned articleIts act of writing ...
- alex December 09, 2013