chriscow
BAN USERAssuming both sorted in strictly increasing order:
M[row][column] < M[row+1][column] and M[row][column] < M[row][column+1]
Start from the top-right corner of the matrix. If the matrix element is larger than the target, move to the column on the left; if smaller, move to the row below.
Complexity if O(#rows + #columns)
public Position searchSortedMatrix(int x, int[][] M) {
if (M.length==0 || M[0].length==0) return Position(-1,-1);
int row = 0, column = M[0].length-1, curVal;
while (row<M.length && column>=0) {
curVal = M[row][column];
if (curVal == x) return Position(row,column);
if (curVal > x) column--;
else row++;
}
return Position(-1,-1);
}
java code:
I assumed that if there is no star in the second String, false should be returned.
static boolean matches(String input, String star) {
if (star.length()==0) return false;
int p=0, q=0;
while (p < input.length() && q < star.length() && star.charAt(q)!='*') {
//Move from begin to end until hit '*'
if (input.charAt(p++) != star.charAt(q++)) return false;
}
if (q==star.length()) //q==star.length() means no '*' in star
return false;
int u=input.length()-1, v=star.length()-1;
while (u >= 0 && v >= 0 && star.charAt(v) != '*') {
//Move from end to begin until hit '*'
if (input.charAt(u--) != star.charAt(v--)) return false;
}
if (v < 0) //v<0 means no '*' in star
return false;
//If there is a match with a single '*' in star
//q and v should both end up at the position of '*'
return q==v && star.charAt(q)=='*' && star.charAt(v)=='*';
}
Test cases:
"", "": false
"", "*": true
"abcde", "*": true
"abcde", "a*e": true
"abcde", "abc*de": true
"abcde", "*e": true
"abcde", "a*": true
"aaaaaaaaaa", "aa": false
"abababab", "ab": false
"abababab", "ab*b": true
"abababab", "ab***ab": false
int findBreakingPoint (int[] arr) {
if (arr.length > 0) {
int sum = 0;
for (int i:arr) sum += i;
if (sum^1 != 0) return -1; \\sum cannot be odd
sum >>= 1;
for (int pos = 0; pos < arr.length; pos++) {
target -= arr[pos];
if (target == 0) return pos;
}
}
return -1;
}
You are not utilizing the fact that it is a BST. Your solution takes O(n) while it could be done in O(logn).
- chriscow January 24, 2014