wangbingold
BAN USERpackage org.wangbingold.datastructure.array;
/**
* Question:
Implement rotate function for forwardonly iterators.
Clarification: with O(1) additional memory.
Rotate semantics should be that of std::rotate.
Example:
Say the array was [1, 2, 3, 4, 5, a, b , c]. With middle pointing at 'a'.
First at 1, and last at 'c', and we need to rotate so that it is [a, b, c, 1, 2, 3, 4, 5].
You make a copy of the First, Middle Iterators, say first', middle'.
*/
public class Rotation {
private char[] array;
public Rotation(char[] arrayIn){
this.array = arrayIn;
}
/**
* Rotate the array in the range of [start, end] from the position of mid.
* */
public void rotate(int start, int mid, int end){
if(start>=end){
return;
}
int numPart1 = midstart;
int numPart2 = endmid+1;
int p1 = start;
int p2 = mid;
if(numPart1==numPart2){
while(p2<=end){
char tmp = array[p1];
array[p1] = array[p2];
array[p2] = tmp;
p1++;p2++;
}
System.out.println(this.toString());
}
else if(numPart1>numPart2){
while(p2<=end){
char tmp = array[p1];
array[p1] = array[p2];
array[p2] = tmp;
p1++;p2++;
}
int newStart = p1;
int newEnd = p21;
int newMid = newStart+numPart1numPart2;
System.out.println(this.toString());
rotate(newStart, newMid, newEnd);
}
else if(numPart1<numPart2){
while(p1<mid){
char tmp = array[p1];
array[p1] = array[p2];
array[p2] = tmp;
p1++;p2++;
}
int newStart = p1;
int newEnd = (p2==end)?p2:p2+1;
int newMid = (p2>end)?p21:p2;
System.out.println(this.toString());
rotate(newStart, newMid, newEnd);
}
}
public String toString(){
String result="";
for(Object obj: array){
result+=obj.toString()+" ";
}
return result;
}
public static void main(String[] args){
Rotation rotation = new Rotation(new char[]{'1','2','3','4','5','a','b','c'});
rotation.rotate(0, 5, 7);
}
}

wangbingold
August 02, 2012 it equals with finding the longest common subsequence between one word (e.g. XAYBZBA) and its reverse (e.g. ABZBYAX).
 wangbingold July 31, 2012<pre lang="java" line="1" title="CodeMonkey30014" class="runthis">public static boolean is_match(String input, String pattern){
if(pattern=="*") return true;
int inputIndex=0;
int patternIndex = 0;
for(; inputIndex<input.length(); inputIndex++){
if(patternIndex==pattern.length()) break;
if(pattern.charAt(patternIndex)=='*'){
char nonStarChar = ' ';
while(++patternIndex<pattern.length()){
if(pattern.charAt(patternIndex)!='*'){
nonStarChar = pattern.charAt(patternIndex);
break;
}
}
if(nonStarChar==' ') return true;
while(inputIndex<input.length()){
if(input.charAt(inputIndex)==nonStarChar){
inputIndex;
break;
}
inputIndex++;
}
if(inputIndex==input.length()) return false;
else continue;
}
else if(input.charAt(inputIndex)==pattern.charAt(patternIndex)){
patternIndex++;
continue;
}
else break;
}
if(inputIndex==input.length() && patternIndex==pattern.length()) return true;
return false;
}</pre><pre title="CodeMonkey30014" input="yes">
</pre>
In practice, it would be better assuming the start and end time would not be double num, should be like "15:30". And if we are talking about setting up appointment on calendar, the gap would be the times of 5 mins (e.g. "15:30  15:40"). So we can think of using baskets on a time line to indicate whether there have already had an appointment. That would be definitely O(n).
 wangbingold January 07, 2011Thanks Sri. But why current aptn only compares with its decedent aptns?
 wangbingold January 07, 2011<pre lang="java" line="1" title="CodeMonkey83982" class="runthis">/*
Only use StringBuilder to be the char buffer.
KMP idea
*/
public String filtering(){
StringBuilder resultBuilder = new StringBuilder();
StringBuilder buffer = new StringBuilder();
int point1=0, point2=0;
while(point1<input1.length()){
if(point2>=input2.length()){
buffer.delete(0, buffer.length());
point2=0;
}
if(input1.charAt(point1)!=input2.charAt(point2)){
if(buffer.length()!=0){
resultBuilder.append(buffer.toString());
buffer.delete(0, buffer.length());
point2=0;
}
resultBuilder.append(input1.charAt(point1++));
}
else if(input1.charAt(point1)==input2.charAt(point2)){
buffer.append(input1.charAt(point1));
point1++; point2++;
}
}
return resultBuilder.toString();
}</pre><pre title="CodeMonkey83982" input="yes">
</pre>
<pre lang="java" line="1" title="CodeMonkey72835" class="runthis">public void printALevel(Node root, int curHeight, int height){
if(root==null) return;
if (height==0) return;
if(curHeight==height){
System.out.print(root+" ");
return;
}
printALevel(root.left, curHeight+1, height);
printALevel(root.right, curHeight+1, height);
}</pre><pre title="CodeMonkey72835" input="yes">
</pre>
DFS solution
 wangbingold December 22, 2010Does the question mean the following:
Sorted list:
abc
bcd
bcde
efghi
Encoded list:
bca
cdb
cdeb
fghie
Does this example make sense or not?
/*
Here is the complete code.
Assume that there is no duplicated element in the matrix.
If handling duplicated element, I will use a HashSet to record seen element.
*/
public class RowColumnSortedMatrix {
int[][] matrix;
public RowColumnSortedMatrix(int[][] matrix){
this.matrix = matrix;
}
public int[] findKthLargest(int k){
int[] result = new int[2];
if(k>matrix.length*matrix.length){//validate input
result[0] = 1; result[1] = 1;
return result;
}
int rowX=matrix.length1, rowY = matrix.length1;
int colX=matrix.length1, colY = matrix.length1;
int maxX=1, maxY=1;
int curRow = matrix.length1, curCol = matrix.length1;
int count=0;
while(count<k){
if(matrix[rowX][rowY]==matrix[colX][colY]){//pointed element equal, move both rowPointer and colPointer
count++;
maxX = rowX; maxY = rowY;
rowX = rowX1;
if(rowX<0){ rowX = curRow1; rowY = rowY1; curRow;}
colY = colY1;
if(colY<0){colY = curCol1; colX = colX1; curCol;}
}
else if(matrix[rowX][rowY]<matrix[colX][colY]){//element pointed by colPointer is bigger, move colPointer
count++;
maxX = colX; maxY = colY;
colY = colY1;
if(colY<0){colY = curCol1; colX = colX1; curCol;}
}
else{//element pointed by rowPointer is bigger, move rowPointer
count++;
maxX = rowX; maxY = rowY;
rowX = rowX1;
if(rowX<0){ rowX = curRow1; rowY = rowY1; curRow;}
}
}
result[0] = maxX; result[1]=maxY;
return result;
}
public static void main(String[] args){
int[][] matrix = {
{0,1,2,3},
{12,14,17,36},
{13,15,18,40},
{50,60,70,80}
};
RowColumnSortedMatrix sortedMatrix = new RowColumnSortedMatrix(matrix);
int[] xy = sortedMatrix.findKthLargest(11);
System.out.println("x= "+xy[0]+"; y= "+xy[1]+" element= "+matrix[xy[0]][xy[1]]);
}
}
O(k), inplace, noextra data structure solution:
Initialization:
Use two pointers (row pointer and column pointer), both begin from the bottomright corner of matrix (the maximum element).
Row pointer moves from bottom to top, and column pointer moves from right to left.
If the element pointed by row pointer is bigger than column pointer, row pointer moves to the next; else column pointer moves to the next.
If row pointer moves to the top (i.e. (0, Y), its next position will wrap innerback (i.e. (preRow1, Y1)); if column pointer moves to the leftmost (i.e. (X, 0)), it also moves back (i.e. (X1, preCol1));
Continue until count to k.
How about taking levelwide travels on two trees? If finding not same nodes, return false; return true until finishing the traveling. Worst case is O(nlogn), average case would be less than O(nlogn)
 wangbingold December 21, 2010I believe that should be double circular linked list
 wangbingold December 16, 2010<pre lang="java" line="1" title="CodeMonkey29109" class="runthis">boolean isBinarySearchTree(Node r){
if(r.isLeaf){
return true;
}
if(r.key>=r.left.key && r.key<r.right.key){
return (true && isBinaryTree(r.left) && isBinaryTree(r.right))
}
else{
return false;
}
}</pre><pre title="CodeMonkey29109" input="yes">
</pre>
Assume that there is no need of aux array, the number of B's empty slots just equal to A's length, and B is trailed by the empty slots
 wangbingold December 06, 2010<pre lang="java" line="1" title="CodeMonkey57027" class="runthis">int[] mergeArrays(int[] a, int[] b){
int emptyIndex = b.length1;
int curB = 0;
int curA = a.length1;
for(int i=b.length1;b>=0; b){//find the first nonempty slots of b from end
if(b[i]!=null){
emptyIndex = i+1;
curB = i;
break;
}
}
while(curA>=0 && curB>=0){
if(a[curA]>b[curB]){
b[emptyIndex] = a[curA];
}
else{
b[emptyIndex] = b[curB];
}
}
if(curA!=0){
while(curA>=0){
b[emptyIndex] = a[curA];
}
}
return b;
}</pre><pre title="CodeMonkey57027" input="yes">
</pre>
O(logN)
 wangbingold December 06, 2010Open Chat in New Window
Please correct me if I was wrong:
 wangbingold August 02, 2012it is true that an input string matches the given pattern once satisfying:
1) pattern length equals with input string's length;
2) fixed characters in pattern match the ones in the same positions of input string