Chengyun Zuo
BAN USERpatpat, you are right.
And this is my code.
Using Merge way, based on your idea:
public class Sum_Smaller_Then_Current {
public static int getSumofLessSum(int[] test,int begin,int end){
if(begin==end){
return 0;
}
if(begin==end-1){
if(test[begin]<=test[end]){
return test[begin];
}
else{
swap(test,begin,end);
return 0;
}
}
int mid=(begin+end)/2;
int leftPart=getSumofLessSum(test,begin,mid);
int rightPart=getSumofLessSum(test,mid+1,end);
int mergeSum=mergeTwoPartGetSum(test,begin,mid,end);
return leftPart+rightPart+mergeSum;
}
public static int mergeTwoPartGetSum(int[] test,int begin,int mid,int end){
int[] helpArray=new int[end-begin+1];
int begin1=begin;
int end1=mid;
int begin2=mid+1;
int end2=end;
int result=0;
int helpArrayIndex=0;
while(begin1<=end1&&begin2<=end2){
if(test[begin1]<=test[begin2]){
result+=test[begin1]*(end2-begin2+1);
helpArray[helpArrayIndex++]=test[begin1++];
}
else{
helpArray[helpArrayIndex++]=test[begin2++];
}
}
if(begin1>end1){
for(;begin2!=end2+1;){
helpArray[helpArrayIndex++]=test[begin2++];
}
}
else{
for(;begin1!=end1+1;){
helpArray[helpArrayIndex++]=test[begin1++];
}
}
for(int i=0;i!=helpArray.length;i++){
test[begin++]=helpArray[i];
}
return result;
}
public static void swap(int[] test,int begin,int end){
int tmp=test[begin];
test[begin]=test[end];
test[end]=tmp;
}
public static void main(String[] args) {
int[] test={3,1,2,4,6,2,7,8};
System.out.println(getSumofLessSum(test,0,test.length-1));
int answer=(1)+(3+1+2)+(3+1+2+4)+(1+2)+(3+1+2+4+6+2)+(3+1+2+4+6+2+7);
System.out.println(answer);
}
}
Cool
- Chengyun Zuo October 07, 2012public static class Node{
public int value;
public int row;
public int col;
public Node(int data,int row,int col){
this.value=data;
this.row=row;
this.col=col;
}
}
public static int[] ConvertMatrixToArray(int[][] test){
int[] result=new int[test.length*test[0].length];
Node[] minHeap=new Node[test.length];
for(int i=0;i!=test.length;i++){
createMinHeap(minHeap,i,new Node(test[i][0],i,0));
}
int indexArray=0;
while(indexArray!=result.length){
Node currentNode=minHeap[0];
int nextRow=currentNode.row;
int nextCol=currentNode.col+1;
int currentValue=currentNode.value;
result[indexArray++]=currentValue;
if(nextCol<test[0].length){
Node nextNode=new Node(test[nextRow][nextCol],nextRow,nextCol);
minHeap[0]=nextNode;
}
else{
Node nextNode=new Node(Integer.MAX_VALUE,nextRow,nextCol);
minHeap[0]=nextNode;
}
adjustMinHeapFromTop(minHeap,0);
}
return result;
}
public static void createMinHeap(Node[] minHeap,int index,Node newItem){
minHeap[index]=newItem;
int parentIndex=(index-1)/2;
while(parentIndex>=0){
if(minHeap[parentIndex].value<=minHeap[index].value){
break;
}
else{
swap(minHeap,parentIndex,index);
}
index=parentIndex;
parentIndex=(index-1)/2;
}
}
public static void adjustMinHeapFromTop(Node[] minHeap,int index){
int left=index*2+1;
int right=index*2+2;
if(right<minHeap.length){
int nextIndex=index;
if(minHeap[nextIndex].value>minHeap[left].value){
nextIndex=left;
}
if(minHeap[nextIndex].value>minHeap[right].value){
nextIndex=right;
}
if(nextIndex==index){
return;
}
else{
swap(minHeap,index,nextIndex);
adjustMinHeapFromTop(minHeap,nextIndex);
}
}
else if(left<minHeap.length){
if(minHeap[index].value>minHeap[left].value){
swap(minHeap,index,left);
}
}
}
public static void swap(Node[] minHeap,int o1,int o2){
Node tmp=minHeap[o1];
minHeap[o1]=minHeap[o2];
minHeap[o2]=tmp;
}
public static void swap(int[] test,int o1,int o2){
int tmp=test[o1];
test[o1]=test[o2];
test[o2]=tmp;
}
public static void SortByOddEvenWay(int [] test){
if(test==null){
return;
}
if(test.length==1){
return;
}
int evenIndex=0;
int oddIndex=1;
int endIndex=test.length-1;
while(evenIndex<test.length&&oddIndex<test.length){
if(test[endIndex]%2==0){
swap(test,endIndex,evenIndex);
evenIndex+=2;
}
else{
swap(test,endIndex,oddIndex);
oddIndex+=2;
}
}
}
public static int[] findMostK(int[] test,int K){
if(test==null){
return null;
}
if(test.length<=K){
return test;
}
int[] result=new int[K];
for(int i=0;i!=K;i++){
creatMinHeap(result,test[i],i);
}
for(int i=K;i!=test.length;i++){
if(result[0]<test[i]){
result[0]=test[i];
adjustMinHeapFromTop(result,0);
}
}
return result;
}
public static void creatMinHeap(int[] result,int newItem,int index){
result[index]=newItem;
int parent=(index-1)/2;
while(parent>=0){
if(result[parent]<=result[index]){
break;
}
else{
swap(result,parent,index);
index=parent;
parent=(index-1)/2;
}
}
}
public static void adjustMinHeapFromTop(int [] result,int index){
int left=index*2+1;
int right=index*2+2;
if(right<result.length){
int nextIndex=index;
if(result[nextIndex]>result[left]){
nextIndex=left;
}
if(result[nextIndex]>result[right]){
nextIndex=right;
}
if(nextIndex==index){
return;
}
else{
swap(result,index,nextIndex);
adjustMinHeapFromTop(result,nextIndex);
}
}
else if (left<result.length){
if(result[index]>result[left]){
swap(result,index,left);
}
}
return;
}
public static void swap(int[] result,int o1Index,int o2Index){
int tmp=result[o1Index];
result[o1Index]=result[o2Index];
result[o2Index]=tmp;
}
public class Printing_Matrix_in_Spiral_Order {
/*
* iven a matrix (2D array) of m x n elements (m rows, n columns),
* write a function that prints the elements in the array in a spiral manner.
* For example:
* int[] test={
* 1, 2, 3, 4,
* 5, 6, 7, 8,
* 9,10,11,12,
* 13,14,15,16
* }
*
* output: 1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10
*/
public static void showSpiralOrder(int[][] test){
int TopLeftRow=0;
int TopLeftCol=0;
int BottomRightRow=test.length-1;
int BottomRightCol=test[0].length-1;
while(TopLeftRow<=BottomRightRow&&TopLeftCol<=BottomRightCol){
int beginX=TopLeftRow;
int beginY=TopLeftCol;
int endX=BottomRightRow;
int endY=BottomRightCol;
if(beginX==endX){
for(int i=beginY;i<=endY;i++){
System.out.print(test[beginX][i]+" ");
}
}
else if(beginY==endY){
for(int i=beginX;i<=endX;i++){
System.out.print(test[i][beginY]+" ");
}
}
else{
int curCol=beginY;
while(curCol!=endY){
System.out.print(test[beginX][curCol]+" ");
curCol++;
}
int curRow=beginX;
while(curRow!=endX){
System.out.print(test[curRow][endY]+" ");
curRow++;
}
while(curCol!=beginY){
System.out.print(test[endX][curCol]+" ");
curCol--;
}
while(curRow!=beginX){
System.out.print(test[curRow][beginY]+" ");
curRow--;
}
}
TopLeftRow++;
TopLeftCol++;
BottomRightRow--;
BottomRightCol--;
}
}
public static void main(String[] args) {
int[][] test={
{ 1, 2, 3, 4},
{ 5, 6, 7, 8},
{ 9,10,11,12},
{13,14,15,16}
};
showSpiralOrder(test);
}
}
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
public class Find_Next_Node_InOrder_In_BinaryTree {
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int data){
this.value=data;
}
}
public static void createParentmap(Node head,HashMap<Node,Node> parentmap){
if(head==null){
System.out.println("This tree is empty!");
return ;
}
Queue<Node> nodeQueue=new LinkedList<Node>();
nodeQueue.add(head);
parentmap.put(head, null);
while(!nodeQueue.isEmpty()){
Node currentNode=nodeQueue.poll();
if(currentNode.left!=null){
parentmap.put(currentNode.left,currentNode);
nodeQueue.add(currentNode.left);
}
if(currentNode.right!=null){
parentmap.put(currentNode.right,currentNode);
nodeQueue.add(currentNode.right);
}
}
}
public static Node findNextNode(Node cur,HashMap<Node,Node> map){
if(!map.containsKey(cur)){
return null;
}
if(map.get(cur)==null||cur.right!=null){
return MostLeftNode(cur.right);
}
Node previous=map.get(cur);
Node current=cur;
while(previous.left!=current){
current=previous;
previous=map.get(previous);
if(previous==null){
return null;
}
}
return previous;
}
public static Node MostLeftNode(Node cur){
if(cur==null){
return null;
}
while(cur.left!=null){
cur=cur.left;
}
return cur;
}
public static void main(String[] args) {
Node head=new Node(16);
head.left=new Node(12);
head.right=new Node(18);
head.left.left=new Node(6);
head.left.right=new Node(14);
head.left.right.left=new Node(13);
head.left.right.right=new Node(15);
head.right.left=new Node(17);
head.right.right=new Node(24);
HashMap<Node,Node> parentMap= new HashMap<Node,Node>();
createParentmap(head, parentMap);
System.out.println(findNextNode(head.left.right,parentMap).value);
}
}
// You can find this problem in leetcode.
// There is my solution.
// I am sure this solution is right.
// And I implement test function.
// The logic is a little complex.
// I spent a whole day solving this problem.
// My solution can find Kth element in two sorted Arrays.
// Time complexity is O(log(m+n)),
// without using extra space
import java.util.Arrays;
public class Find_Kth_Element_of_Two_Sorted_Arrays {
/*
* There are two sorted arrays A and B of size m and n respectively.
* Find the kth element of the two sorted arrays.
* The overall run time complexity should be O(log (m+n)).
*/
public static int findKthofTwoArrays(int[] A,int[] B,int kth){
if(kth>=A.length+B.length||kth<0){
return Integer.MAX_VALUE;//err
}
if(kth==A.length+B.length-1){
return Math.max(A[A.length-1], B[B.length-1]);
}
if(kth<Math.min(A.length, B.length)){
return findMedianTwoArray(A,0,kth,B,0,kth);
}
if(kth==Math.min(A.length, B.length)){
if(A.length==B.length){
if(A[0]>=B[B.length-1]){
return A[0];
}
if(B[0]>=A[A.length-1]){
return B[0];
}
return findMedianTwoArray(A,1,A.length-1,B,1,B.length-1);
}
else{
if(A.length==kth){
if(A[0]>=B[A.length-1]&&A[0]<=B[A.length]){
return A[0];
}
if(B[0]>=A[A.length-1]){
return B[0];
}
if(B[A.length]<=A[0]){
return B[A.length];
}
return findMedianTwoArray(A,1,A.length-1,B,1,A.length-1);
}
else{
if(B[0]>=A[B.length-1]&&B[0]<=A[B.length]){
return B[0];
}
if(A[0]>=B[B.length-1]){
return A[0];
}
if(A[B.length]<=B[0]){
return A[B.length];
}
return findMedianTwoArray(A,1,B.length-1,B,1,B.length-1);
}
}
}
if(kth>Math.min(A.length, B.length)&&kth<Math.max(A.length, B.length)){
if(A.length>B.length){
int beginA=kth-B.length;
int endA=beginA+B.length-1;
int beginB=0;
int endB=B.length-1;
if(A[beginA]>=B[endB]){
return A[beginA];
}
if(B[beginB]>=A[endA]&&B[beginB]<=A[endA+1]){
return B[beginB];
}
if(A[endA+1]<=B[beginB]){
return A[endA+1];
}
return findMedianTwoArray(A,beginA+1,endA,B,beginB+1,endB);
}
else{
int beginA=0;
int endA=A.length-1;
int beginB=kth-A.length;
int endB=beginB+A.length-1;
if(A[beginA]>=B[endB]&&A[beginA]<=B[endB+1]){
return A[beginA];
}
if(B[beginB]>=A[endA]){
return B[beginB];
}
if(B[endB+1]<=A[beginA]){
return B[endB+1];
}
return findMedianTwoArray(A,beginA+1,endA,B,beginB+1,endB);
}
}
if(kth==Math.max(A.length, B.length)){
int beginA=Math.max(0, A.length-B.length);
int endA=A.length-1;
int beginB=Math.max(0, B.length-A.length);
int endB=B.length-1;
if(A[beginA]>=B[endB]){
return A[beginA];
}
if(B[beginB]>=A[endA]){
return B[beginB];
}
return findMedianTwoArray(A,beginA+1,endA,B,beginB+1,endB);
}
if(kth>Math.max(A.length, B.length)){
int beginA=kth-B.length;
int endA=A.length-1;
int beginB=kth-A.length;
int endB=B.length-1;
if(A[beginA]>=B[endB]){
return A[beginA];
}
if(B[beginB]>=A[endA]){
return B[beginB];
}
return findMedianTwoArray(A,beginA+1,endA,B,beginB+1,endB);
}
return -1;
}
public static int findMedianFourNumber(int a, int b,int c,int d){
int[] test=new int[4];
test[0]=a;
test[1]=b;
test[2]=c;
test[3]=d;
Arrays.sort(test);
return test[1];
}
public static int findMedianTwoArray(int[] A,int beginA,int endA,int[] B,int beginB,int endB){
if(endA-beginA!=endB-beginB){
return Integer.MAX_VALUE;
}
if(beginA==endA){
return Math.min(A[beginA], B[beginB]);
}
if(beginA==endA-1){
return findMedianFourNumber(A[beginA],A[endA],B[beginB],B[endB]);
}
int midA=(beginA+endA)/2;
int midB=(beginB+endB)/2;
if(A[midA]==B[midB]){
return A[midA];
}
if((endA-beginA+1)%2==0){
if(A[midA]>B[midB]){
if(A[midA]<=B[midB+1]){
return A[midA];
}
return findMedianTwoArray(A,beginA,midA,B,midB+1,endB);
}
else{
if(B[midB]<=A[midA+1]){
return B[midB];
}
return findMedianTwoArray(A,midA+1,endA,B,beginB,midB);
}
}
else{
if(A[midA]<B[midB]){
if(A[midA]>=B[midB-1]){
return A[midA];
}
return findMedianTwoArray(A,midA+1,endA,B,beginB,midB-1);
}
else{
if(B[midB]>=A[midA-1]){
return B[midB];
}
return findMedianTwoArray(A,beginA,midA-1,B,midB+1,endB);
}
}
}
/*
* for test:
* */
public static int[] creatArray(){
int [] obj=new int[(int)(Math.random()*20)+1];
for(int i=0;i!=obj.length;i++){
obj[i]=(int)(Math.random()*100);
}
Arrays.sort(obj);
return obj;
}
public static int[] creatArray(int length){
int [] obj=new int[length];
for(int i=0;i!=obj.length;i++){
obj[i]=(int)(Math.random()*100);
}
Arrays.sort(obj);
return obj;
}
public static void show(int[] test){
System.out.println();
for(int i=0;i!=test.length;i++){
System.out.print(test[i]+" ");
}
System.out.println();
}
public static int[] mergeSort(int[] o1,int[] o2){
int[] result=new int[o1.length+o2.length];
int index=0;
for(int i=0;i!=o1.length;i++){
result[index++]=o1[i];
}
for(int i=0;i!=o2.length;i++){
result[index++]=o2[i];
}
Arrays.sort(result);
return result;
}
public static void main(String[] args) {
int[] A=creatArray();
int[] B=creatArray();
int[] All=mergeSort(A,B);
System.out.print("Array A:");
show(A);
System.out.print("Array B:");
show(B);
System.out.print("Using merge O(m+n): ");
for(int i=0;i!=All.length;i++){
System.out.print(All[i]+" ");
}
System.out.println();
System.out.print("BS way O(log(m+n)): ");
for(int i=0;i!=A.length+B.length;i++){
System.out.print(findKthofTwoArrays(A,B,i)+" ");
}
}
}
public static ArrayList<Integer> copyList(ArrayList<Integer> obj){
ArrayList<Integer> result=new ArrayList<Integer>();
for(int i=0;i!=obj.size();i++){
result.add(obj.get(i));
}
return result;
}
public static ArrayList<ArrayList<Integer>> getAllSubSet(int num,int length){
if(length<1){
return null;
}
if(num<1){
return null;
}
if(length>num){
return null;
}
ArrayList<ArrayList<Integer>> result= new ArrayList<ArrayList<Integer>>();
for(int i=1;i!=num+1;i++){
ArrayList<Integer> tmp=new ArrayList<Integer>();
tmp.add(i);
compute_process(num,length,i+1,1,result,tmp);
}
return result;
}
public static void compute_process(int num,int len,
int curNum,int curLen,
ArrayList<ArrayList<Integer>> result,
ArrayList<Integer> current){
if(curNum>num){
if(current.size()==len){
result.add(current);
}
return;
}
if(curLen==len){
result.add(current);
return;
}
ArrayList<Integer> next=copyList(current);
current.add(curNum);
compute_process(num,len,curNum+1,curLen+1,result,current);
compute_process(num,len,curNum+1,curLen,result,next);
}
// This problem should confine the value of every element in this BinaryTree is different.
// Or you can not reconstruct A BinaryTree by using Pre-order and In-order Array.
public class Pre_In_Order_Of_Tree_Reconstruct_Tree {
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int data){
this.value=data;
}
}
public static void showPre(Node head){
if(head==null){
return ;
}
System.out.print(head.value+" ");
showPre(head.left);
showPre(head.right);
}
public static void showIn(Node head){
if(head==null){
return ;
}
showIn(head.left);
System.out.print(head.value+" ");
showIn(head.right);
}
public static Node reconTree(int[] Pre,int[] In){
Node result=compute_process(Pre,In,0,0,In.length-1);
return result;
}
public static Node compute_process(int[] Pre,int[] In,int PreIndex,int Inbegin,int Inend){
if(PreIndex>=Pre.length){
return null;
}
if(Inbegin==Inend){
return new Node(Pre[PreIndex]);
}
Node head=new Node(Pre[PreIndex]);
int num=findPosition(In,Inbegin,Inend,Pre[PreIndex]);
if(num==0){
head.left=null;
}
else{
head.left=compute_process(Pre,In,PreIndex+1,Inbegin,Inbegin+num-1);
}
if(num==Inend-Inbegin+1){
head.right=null;
}
else{
head.right=compute_process(Pre,In,PreIndex+num+1,Inbegin+num+1,Inend);
}
return head;
}
public static int findPosition(int[] In,int Inbegin,int Inend,int aim){
int num=0;
for(int i=Inbegin;i<=Inend;i++){
if(In[i]!=aim){
num++;
}
else{
break;
}
}
return num;
}
public static void main(String[] args) {
int[] Pre = {8,7,3,1,2,9,10,6,4,12};
int[] In = {3,7,1,2,8,9,6,4,10,12};
Node head=reconTree(Pre,In);
showPre(head);
System.out.println();
showIn(head);
}
}
I implement it again, and you can define combination number.
In this case, combination number is 4.
you also can define it as 3,5.
package amazon;
import java.util.ArrayList;
import java.util.Arrays;
public class Give_Sum_Get_N_Combination_In_Array {
public static void Print_Result(int[] test,int aim,int ComNumber){
Arrays.sort(test);
ArrayList<Integer> everyResult=new ArrayList<Integer>();
ArrayList<ArrayList<Integer>> results=new ArrayList<ArrayList<Integer>>();
compute_process(test,aim,ComNumber,0,0,1, everyResult,results);
show_result(results);
}
public static void compute_process(int[] test,int aim,int ComNumber,
int index,int currentSum,int currentComNumber,ArrayList<Integer> everyResult,
ArrayList<ArrayList<Integer>> results){
if(index==test.length){
return;
}
if(currentSum>aim){
return;
}
if(currentComNumber==ComNumber){
if(currentSum+test[index]==aim){
everyResult.add(test[index]);
results.add(everyResult);
}
}
ArrayList<Integer> tmp1=copyArrayList(everyResult);
ArrayList<Integer> tmp2=copyArrayList(everyResult);
tmp1.add(test[index]);
compute_process(test,aim,ComNumber,
index+1,currentSum+test[index],currentComNumber+1,tmp1,results);
compute_process(test,aim,ComNumber,
index+1,currentSum,currentComNumber,tmp2,results);
}
public static ArrayList<Integer> copyArrayList(ArrayList<Integer> obj){
ArrayList<Integer> result=new ArrayList<Integer>();
for(int i=0;i!=obj.size();i++){
result.add(obj.get(i));
}
return result;
}
public static void show_result(ArrayList<ArrayList<Integer>> test){
System.out.println("Results number: "+test.size());
for(int i=0;i!=test.size();i++){
int sum=0;
System.out.print((int)(i+1)+") ");
for(int j=0;j!=test.get(i).size();j++){
int num=test.get(i).get(j);
sum+=num;
System.out.print(num);
if(j==test.get(i).size()-1)
System.out.print("=");
else
System.out.print("+");
}
System.out.print(sum);
System.out.println();
}
}
public static void main(String[] args) {
int[] test={10,2,3,4,5,9,7,8};
int aim=23;
int CombinationNumber=4;
Print_Result(test,aim,CombinationNumber);
}
}
output:
Results number: 9
1) 10+2+3+8=23
2) 10+2+4+7=23
3) 10+4+9=23
4) 10+5+8=23
5) 2+3+4+5+9=23
6) 2+4+9+8=23
7) 2+5+9+7=23
8) 3+4+9+7=23
9) 3+5+7+8=23
package amazon;
import java.util.ArrayList;
public class Give_Sum_Get_Combination_In_Array {
/*
* Given an array of integers,
* find all combination in the array whose sum is equal to a given value X.
* For example, if the given array is {10, 2, 3, 4, 5, 9, 7, 8} and X = 23,
* then your function should print “3 5 7 8″ (3 + 5 + 7 + 8 = 23).
*/
public static void Print_Result(int[] test,int aim){
ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> begin=new ArrayList<Integer>();
compute_process(test,0,aim,0,result,begin);
show_result(result);
}
public static void compute_process(int[] test,int index,int aim,int currentValue,
ArrayList<ArrayList<Integer>> result,ArrayList<Integer> currentArray){
if(index==test.length){
return;
}
ArrayList<Integer> stepArray1=cloneArrayList(currentArray);
ArrayList<Integer> stepArray2=cloneArrayList(currentArray);
ArrayList<Integer> stepArray3=cloneArrayList(currentArray);
if(test[index]+currentValue==aim){
stepArray1.add(test[index]);
result.add(stepArray1);
}
stepArray2.add(test[index]);
compute_process(test,index+1,aim,currentValue+test[index],result,stepArray2);
compute_process(test,index+1,aim,currentValue,result,stepArray3);
}
public static ArrayList<Integer> cloneArrayList(ArrayList<Integer> obj){
ArrayList<Integer> result=new ArrayList<Integer>();
for(int i=0;i!=obj.size();i++){
result.add(obj.get(i));
}
return result;
}
public static void show_result(ArrayList<ArrayList<Integer>> test){
System.out.println("Results number: "+test.size());
for(int i=0;i!=test.size();i++){
int sum=0;
System.out.print((int)(i+1)+") ");
for(int j=0;j!=test.get(i).size();j++){
int num=test.get(i).get(j);
sum+=num;
System.out.print(num);
if(j==test.get(i).size()-1)
System.out.print("=");
else
System.out.print("+");
}
System.out.print(sum);
System.out.println();
}
}
public static void main(String[] args) {
int[] test={10,2,3,4,5,9,7,8};
int aim=23;
Print_Result(test,aim);
}
}
public static boolean isAppears(String A,String B){
boolean[] Appears=new boolean[256];
for(int i=0;i!=B.length();i++){
Appears[(int)(B.charAt(i))]=true;
}
for(int i=0;i!=A.length();i++){
if(Appears[(int)(A.charAt(i))]==false){
return false;
}
}
return true;
}
看到中文我都感动的哭了!不过这里应该说是N路并归。
- Chengyun Zuo August 29, 2012public static int[] getResult(int[] test){
int[] result=new int[test.length];
int max=test[test.length-1];
for(int i=test.length-1;i!=-1;i--){
if(test[i]>max){
max=test[i];
}
result[i]=max;
}
return result;
}
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
public class Queue_With_Additional_Functions {
/*
* Design a data structure for the following operations:
*
* I. Enqueue
* II. Dequeue
* III. Delete a given number(if it is present in the queue, else do nothing)
* IV. isNumberPresent
*
* All these operations should take O(1) time
*/
private int NthIn;
private int NthOut;
private Queue<Integer> myQueue;
private HashMap<Integer,Integer> validPosition;
public Queue_With_Additional_Functions(){
this.NthIn=1;
this.NthOut=1;
this.myQueue=new LinkedList<Integer>();
this.validPosition=new HashMap<Integer,Integer>();
}
public void Enqueue(int data){
if(this.validPosition.containsKey(data)){
if(this.validPosition.get(data)==-1){
this.validPosition.put(data, this.NthIn);
}
}
else{
this.validPosition.put(data, this.NthIn);
}
this.NthIn++;
this.myQueue.add(data);
}
public int Dequeue(){
while(!this.myQueue.isEmpty()){
int result=this.myQueue.poll();
if(this.validPosition.get(result)==-1||this.validPosition.get(result)>this.NthOut){
this.NthOut++;
continue;
}
else{
this.NthOut++;
return result;
}
}
return Integer.MAX_VALUE;
}
public void DeleteGivenNumber(int data){
if(this.validPosition.containsKey(data)){
this.validPosition.put(data, -1);
}
}
public boolean isNumberPresent(int data){
if(this.validPosition.containsKey(data)){
if(this.validPosition.get(data)==-1){
return false;
}
else{
return true;
}
}
else{
return false;
}
}
public static void main(String[] args) {
Queue_With_Additional_Functions test=new Queue_With_Additional_Functions();
test.Enqueue(1);
test.Enqueue(1);
test.Enqueue(2);
test.DeleteGivenNumber(1);
test.Enqueue(1);
System.out.println(test.Dequeue());
System.out.println(test.Dequeue());
}
}
public static String findNth(int index){
String result="";
while(index>0){
int currentBit=index%26;
result=getWhat(currentBit)+result;
index=index/26;
}
return result;
}
public static String getWhat(int currentBit){
switch(currentBit){
case 1:
return "A";
case 2:
return "B";
case 3:
return "C";
case 4:
return "D";
case 5:
return "E";
case 6:
return "F";
case 7:
return "G";
case 8:
return "H";
case 9:
return "I";
case 10:
return "J";
case 11:
return "K";
case 12:
return "L";
case 13:
return "M";
case 14:
return "N";
case 15:
return "O";
case 16:
return "P";
case 17:
return "Q";
case 18:
return "R";
case 19:
return "S";
case 20:
return "T";
case 21:
return "U";
case 22:
return "V";
case 23:
return "W";
case 24:
return "X";
case 25:
return "Y";
default:
return "Z";
}
}
public static ArrayList<ArrayList<Integer>> createLevelArrays(BinaryTreeNode head){
if(head==null){
return null;
}
ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
HashMap<BinaryTreeNode,Integer> map=new HashMap<BinaryTreeNode,Integer>();
map.put(head, 1);
Queue<BinaryTreeNode> path=new LinkedList<BinaryTreeNode>();
path.add(head);
while(!path.isEmpty()){
BinaryTreeNode current=path.poll();
int currentlevel=map.get(current);
if(result.size()<currentlevel){
result.add(new ArrayList<Integer>());
}
result.get(currentlevel-1).add(current.value);
if(current.left!=null){
map.put(current.left, currentlevel+1);
path.add(current.left);
}
if(current.right!=null){
map.put(current.right, currentlevel+1);
path.add(current.right);
}
}
return result;
}
public static boolean isNested(String AK){
int status=0;
for(int i=0;i!=AK.length();i++){
if(AK.charAt(i)=='('){
status++;
continue;
}
if(AK.charAt(i)==')'){
status--;
if(status<0){
return false;
}
continue;
}
}
return status==0 ? true : false;
}
HashTable + Min-Heap
- Chengyun Zuo August 25, 2012public static int improvePowCompute(int obj,int times){
HashMap<Integer,Integer> result_hold=new HashMap<Integer,Integer>();
result_hold.put(0, 1);
result_hold.put(1, obj);
return compute_process(obj,times,result_hold);
}
public static int compute_process(int obj,int times,HashMap<Integer,Integer> result_hold){
if(times<0){
return Integer.MIN_VALUE;
}
if(times%2==0){
if(result_hold.containsKey(times/2)){
int tmp=result_hold.get(times/2);
result_hold.put(times, tmp*tmp);
return tmp*tmp;
}
else{
int tmp=compute_process(obj,times/2,result_hold);
result_hold.put(times, tmp);
return tmp*tmp;
}
}
else{
if(result_hold.containsKey((times-1)/2)){
int tmp=result_hold.get((times-1)/2);
result_hold.put(times, tmp*tmp*obj);
return tmp*tmp*obj;
}
else{
int tmp=compute_process(obj,(times-1)/2,result_hold);
result_hold.put(times, tmp*tmp*obj);
return tmp*tmp*obj;
}
}
}
public static int find_miss_one_number(int[] test,int form,int to){
int result1=0;
for(int i=0;i!=test.length;i++){
result1+=test[i];
}
int result2=0;
for(int i=form;i!=to+1;i++){
result2+=i;
}
return result2-result1;
}
public static int[] find_miss_two_numbers(int[] test,int form,int to){
int result1=0;
int result2=0;
for(int i=0;i!=test.length;i++){
result1+=test[i];
result2+=test[i]*test[i];
}
int result3=0;
int result4=0;
for(int i=form;i!=to+1;i++){
result3+=i;
result4+=i*i;
}
int sub1=result3-result1;
int sub2=result4-result2;
//x+y=sub1;
//x^2+y^2=sub2;
int a=2;
int b=sub1*(-2);
int c=sub1*sub1-sub2;
int[] result=new int[2];
result[0]=(b*(-1)-((int)Math.sqrt(b*b-4*a*c)))/(2*a);
result[1]=(b*(-1)+((int)Math.sqrt(b*b-4*a*c)))/(2*a);
return result;
}
public static void divide_neg_0_pos(int [] test){
int neg_hold=-1;
int pos_hold=test.length;
int current=0;
while(current!=pos_hold){
if(test[current]>0){
exChange(test,current,--pos_hold);
continue;
}
if(test[current]<0){
if(current==neg_hold){
current++;
continue;
}
exChange(test,current,++neg_hold);
}
if(test[current]==0){
current++;
}
}
}
public static String getLongestCRS(String test){
if(test==""){
return "";
}
if(test.length()==1){
return "";
}
String max="";
for(int i=0;i!=test.length();i++){
String currentMax="";
for(int j=test.length()-1;j!=i;j--){
if(test.charAt(i)==test.charAt(j)){
if(test.substring(j, test.length()).indexOf(test.substring(i,j))==0){
currentMax=test.substring(i, j);
break;
}
}
}
if(currentMax.length()>max.length()){
max=currentMax;
}
}
return max;
}
Build a min-heap which has 7 nodes, traverse all nodes and keep on adjusting the min-heap. Finally, the min-heap top is the answer.
- Chengyun Zuo August 19, 2012public static String find_all_anagrams(String text){
ArrayList<String> allWords=new ArrayList<String>();
getAllwords(text,allWords);
HashMap<String,Boolean> map = new HashMap<String,Boolean>();
for(int i=0;i!=allWords.size();i++){
String str=allWords.get(i);
String sort=getSortedString(str);
if(map.containsKey(sort)){
map.put(sort, true);
}
else{
map.put(sort, false);
}
}
String result="";
for(int i=0;i!=allWords.size();i++){
String str=allWords.get(i);
String sort=getSortedString(str);
if(map.get(sort)){
result+=str+" ";
}
}
return result;
}
public static void getAllwords(String text,ArrayList<String> allWords){
int begin_index=0;
boolean begin_end=true;
for(int i=0;i!=text.length();i++){
if(begin_end){
if(text.charAt(i)!=' '){
begin_index=i;
begin_end=false;
}
}
else{
if(text.charAt(i)==' '){
allWords.add(text.substring(begin_index, i));
begin_end=true;
continue;
}
if(i==text.length()){
allWords.add(text.substring(begin_index, i));
begin_end=true;
}
}
}
}
public static String getSortedString(String obj){
char[] result=obj.toCharArray();
Arrays.sort(result);
return String.valueOf(result);
}
Yes, oh God...
- Chengyun Zuo August 17, 2012public static LinkedListNode delete_given_number(LinkedListNode head,int givenNumber){
if(head==null){
return null;
}
while(head.data==givenNumber){
head=head.next;
if(head==null){
return null;
}
}
LinkedListNode pervious=head;
LinkedListNode current=head;
while(current!=null){
if(current.data==givenNumber){
pervious.next=current.next;
}
else{
pervious=current;
}
current=current.next;
}
return head;
}
If you run my code, you will know I am correct.
- Chengyun Zuo August 16, 2012It can be proved, and the original proof is easy to find by using google.^_^
- Chengyun Zuo August 16, 2012Oh, sorry. In my solution, A is longer than B.
But the same logic
firstly, slow node moves one time one step, fast node moves one time two steps.
there is a loop, So when slow encounter fast, slow go back to head and move one time one step.
Now, fast move one time one step too.
when they meet again, the node is entry.
public class Problem_1_Merge_B_into_A {
public static void sort_into(int[] a,int[] b,int lastA,int lastB){
int valid_a_end_index=lastA-1;
int valid_b_end_index=lastB-1;
int valid_all_end_index=lastA+lastB-1;
while((valid_a_end_index>=0)&&(valid_b_end_index>=0)){
if(a[valid_a_end_index]>b[valid_b_end_index]){
a[valid_all_end_index]=a[valid_a_end_index];
valid_all_end_index--;
valid_a_end_index--;
}
else{
a[valid_all_end_index]=b[valid_b_end_index];
valid_all_end_index--;
valid_b_end_index--;
}
}
while(valid_b_end_index>=0){
a[valid_all_end_index]=b[valid_b_end_index];
valid_all_end_index--;
valid_b_end_index--;
}
}
public static void main(String[] args) {
int[] a=new int[]{1,3,5,7,9,11,13,14,0,0,0,0,0,0,0,0,0};// valid 8 element
int[] b=new int[]{2,4,5,6,8,10,13,15};//valid 8 element
sort_into(a,b,8,b.length);
for(int i=0;i!=8+b.length;i++)
System.out.print(a[i]+" ");
}
}
My code, check Linkedlist has cycle and return entry node of cycle:
public static LinkedListNode find_cycle_entry(LinkedListNode head){
if(head==null){
System.out.println("err, no cycle!");
return null;
}
LinkedListNode slow=head.next;
if(slow==null){
System.out.println("err, no cycle!");
return null;
}
LinkedListNode fast=head.next.next;
if(fast==null){
System.out.println("err, no cycle!");
return null;
}
while(fast!=null){
if(slow==fast){
break;
}
slow=slow.next;
fast=fast.next;
if(fast==null){
System.out.println("err, no cycle!");
return null;
}
fast=fast.next;
}
if(fast==null){
System.out.println("err, no cycle!");
return null;
}
slow=head;
while(slow!=fast){
slow=slow.next;
fast=fast.next;
}
return slow;
}
public static void set_random_no_repeated(int[][] test,int maxValue){
if(maxValue<test.length*test[0].length){
System.out.println("No way!");
return;
}
HashMap<Integer,Boolean> map=new HashMap<Integer,Boolean>();
for(int i=0;i!=test.length;i++){
for(int j=0;j!=test[0].length;j++){
int setValue=0;
do{
setValue=(int)(Math.random()*maxValue);
}
while(map.containsKey(setValue));
map.put(setValue, true);
test[i][j]=setValue;
}
}
}
public static int getMincoinsnumber(int[] coins,int aim){
Arrays.sort(coins);
int results=compute_posscess(coins,aim,coins.length-1,0,0);
if(results==Integer.MAX_VALUE){
return -1;
}
return results;
}
public static int compute_posscess(int[] coins,int aim,
int index,int currentaim,int currentnumber){
if(index==0){
if(aim==coins[0]+currentaim){
return currentnumber+1;
}
else{
return Integer.MAX_VALUE;
}
}
if(aim==coins[index]+currentaim){
return currentnumber+1;
}
else if(aim<coins[index]+currentaim){
int result=compute_posscess(coins,aim,index-1,currentaim,currentnumber);
return result;
}
else{
int result1=compute_posscess(coins,aim,index-1,currentaim+coins[index],currentnumber+1);
int result2=compute_posscess(coins,aim,index-1,currentaim,currentnumber);
return Math.min(result1, result2);
}
}
public static void zigzagShow(int input){
int[][] matrix=new int[input][input];
int beginSet=1;
for(int i=0;i!=matrix.length;i++){
for(int j=0;j!=matrix.length;j++){
matrix[i][j]=beginSet++;
}
}
boolean direct=false;
//direct==true, show from top-right to bottom-left
//direct==false, show from bottom-left to top-right
int index_x=0;
int index_y=0;
while(!(index_x==input-1&&index_y==input-1)){
System.out.print(matrix[index_x][index_y]+" ");
if(direct){
try{
matrix[index_x+1][index_y-1]=matrix[index_x+1][index_y-1];
}
catch(Exception e1){
try{
matrix[index_x+1][index_y]=matrix[index_x+1][index_y];
}
catch(Exception e2){
index_y++;
direct=!direct;
continue;
}
index_x++;
direct=!direct;
continue;
}
index_x++;
index_y--;
}
else{
try{
matrix[index_x-1][index_y+1]=matrix[index_x-1][index_y+1];
}
catch(Exception e1){
try{
matrix[index_x][index_y+1]=matrix[index_x][index_y+1];
}
catch(Exception e2){
index_x++;
direct=!direct;
continue;
}
index_y++;
direct=!direct;
continue;
}
index_x--;
index_y++;
}
}
System.out.println(matrix[index_x][index_y]);
}
public static int getSurviveNode(LinkedListNode head,int times){
if(head.next==head){
return head.data;
}
LinkedListNode current=head.next;
while(current.next!=head){
current=current.next;
}
LinkedListNode pervious=current;
current=head;
int killtimes=1;
while(current.next!=current){
if(killtimes==times){
pervious.next=current.next;
current.next=null;
current=pervious.next;
killtimes=1;
continue;
}
else{
pervious=current;
current=current.next;
killtimes++;
}
}
return current.data;
}
public static LinkedListNode Merge_Two_List(LinkedListNode head1,LinkedListNode head2){
LinkedListNode current1=(head1.data<=head2.data?head1:head2);
LinkedListNode current2=(current1==head1?head2:head1);
LinkedListNode newhead=current1;
LinkedListNode pervious=current1;
while(current1!=null&¤t2!=null){
if(current1.data<=current2.data){
pervious=current1;
current1=current1.next;
continue;
}
else{
LinkedListNode nextcurrent2=current2.next;
pervious.next=current2;
current2.next=current1;
pervious=current2;
current2=nextcurrent2;
}
}
if(current1==null){
pervious.next=current2;
return newhead;
}
else{
return newhead;
}
}
Your idea is great!
and I implemented your idea,
here is my code:
public static int get_shortest_path(int[][] test){
if(test[0][0]==0||test[test.length-1][test[0].length-1]==0){
return Integer.MAX_VALUE;
}
int[][] map=new int[test.length][test[0].length];
map[0][0]=1;
boolean change=true;
while(change){ //If there is no update, then we finish.
change=false;
for(int i=0;i!=test.length;i++){
for(int j=0;j!=test[0].length;j++){
if(test[i][j]==1){
int up=Integer.MAX_VALUE;
int down=Integer.MAX_VALUE;
int left=Integer.MAX_VALUE;
int right=Integer.MAX_VALUE;
if(i>0){
up=(map[i-1][j]==0?Integer.MAX_VALUE:map[i-1][j]);
}//check up
if(i<test.length-1){
down=(map[i+1][j]==0?Integer.MAX_VALUE:map[i+1][j]);
}//check down
if(j>0){
left=(map[i][j-1]==0?Integer.MAX_VALUE:map[i][j-1]);
}//check left
if(j<test[0].length-1){
right=(map[i][j+1]==0?Integer.MAX_VALUE:map[i][j+1]);
}//check right
int a=Math.min(up, down);
int b=Math.min(left,right);
int update=Math.min(a, b);
if(update==Integer.MAX_VALUE){
continue;
}
if(map[i][j]==0){
map[i][j]=update+1;
change=true;
}
else{
if(map[i][j]>update+1){
map[i][j]=update+1;
change=true;
}
}
}
}
}
}
int results=map[map.length-1][map[0].length-1];
if(results==0){
return Integer.MAX_VALUE;
}
else
return results-1;
}
How to solve this problem by using knowledge of Graph?
- Chengyun Zuo August 14, 2012import java.util.ArrayList;
class Point{
public int x;
public int y;
public Point(int x,int y){
this.x=x;
this.y=y;
}
}
public class Walk_from_0_0_to_n_n {
/*
* You have a matrix of size n*n with entries either 1 or 0.
* 1 means there is a path, 0 means no path.
* Find shortest path and print it from (0,0) to (n-1, n-1)
*/
public static void setvalue(int[][]test){
for(int i=0;i!=test.length;i++){
for(int j=0;j!=test[0].length;j++){
if((int)(Math.random()*4)>2){
test[i][j]=0;
}
else{
test[i][j]=1;
}
}
}
}
public static void show(int[][] test){
for(int i=0;i!=test.length;i++){
for(int j=0;j!=test[0].length;j++){
System.out.print(test[i][j]+" ");
}
System.out.println();
}
}
public static int get_shortest_path(int[][]test){
if(test[0][0]==0||test[test.length-1][test[0].length-1]==0){
return Integer.MAX_VALUE;
}
ArrayList<Point> map=new ArrayList<Point>();
int a=find_path(0,0,4,map,test);
int b=find_path(0,0,3,map,test);
if(a==Integer.MAX_VALUE&&b==Integer.MAX_VALUE){
return Integer.MAX_VALUE;
}
else{
return Math.min(a, b);
}
}
public static int find_path(int x,int y,int direct,ArrayList<Point> map,int[][] test){
if(checkHas(map,x,y)){
return Integer.MAX_VALUE;
}
else{
map.add(new Point(x,y));
}
if(x==test.length-1&&y==test[0].length-1){
return 1;
}
int go_down=Integer.MAX_VALUE;
int go_right=Integer.MAX_VALUE;
int go_up=Integer.MAX_VALUE;
int go_left=Integer.MAX_VALUE;
@SuppressWarnings("unchecked")
ArrayList<Point> map1=(ArrayList<Point>) map.clone();
@SuppressWarnings("unchecked")
ArrayList<Point> map2=(ArrayList<Point>) map.clone();
@SuppressWarnings("unchecked")
ArrayList<Point> map3=(ArrayList<Point>) map.clone();
@SuppressWarnings("unchecked")
ArrayList<Point> map4=(ArrayList<Point>) map.clone();
if(x<test.length-1&&test[x+1][y]==1&&direct!=1){
go_down=find_path(x+1,y,3,map1,test);
}
if(y<test[0].length-1&&test[x][y+1]==1&&direct!=2){
go_right=find_path(x,y+1,4,map2,test);
}
if(x>0&&test[x-1][y]==1&&direct!=3){
go_up=find_path(x-1,y,1,map3,test);
}
if(y>0&&test[x][y-1]==1&&direct!=4){
go_left=find_path(x,y-1,2,map4,test);
}
int a=Math.min(go_right, go_down);
int b=Math.min(go_up, go_left);
int result=Math.min(a, b);
if(result==Integer.MAX_VALUE){
return result;
}
else{
return result+1;
}
}
public static boolean checkHas(ArrayList<Point>map,int x,int y){
for(int i=0;i!=map.size();i++){
if(map.get(i).x==x&&map.get(i).y==y){
return true;
}
}
return false;
}
public static void main(String[] args) {
int size=7;
int[][] test=new int[size][size];
setvalue(test);
show(test);
System.out.println("Shortest Path: "+get_shortest_path(test));
}
}
My code, It can work:
public class Divide_Array {
public static ArrayList<Integer> return_results(int test){
String number=String.valueOf(test);
int[] array_int=new int[number.length()];
for(int i=0;i!=array_int.length;i++){
array_int[i]=Integer.valueOf(String.valueOf(number.charAt(i)));
}
ArrayList<Integer> results=new ArrayList<Integer>();
for(int i=0;i!=array_int.length;i++){
results.clear();
results.add(split(array_int,0,i));
compute_process(results,array_int,test,i+1);
if(isValid(results,test)){
return results;
}
}
return null;
}
public static void compute_process(ArrayList<Integer> results,int[] array_int,int aim,int step){
if(step==array_int.length){
return;
}
if(results.size()==1){
for(int i=step;i!=array_int.length;i++){
int next=split(array_int,step,i);
if(next==results.get(0)||next==results.get(0)+1){
results.add(next);
compute_process(results,array_int,aim,i+1);
if(isValid(results,aim)){
return;
}
}
}
}
else{
for(int i=step;i!=array_int.length;i++){
int next=split(array_int,step,i);
if(next==results.get(results.size()-1)+results.get(results.size()-2)){
results.add(next);
compute_process(results,array_int,aim,i+1);
if(isValid(results,aim)){
return;
}
}
}
}
}
public static int split(int[] test,int begin,int end){
if((begin<0)||(end>test.length-1)){
return Integer.MAX_VALUE;
}
int result=0;
for(int i=begin;i<=end;i++){
result*=10;
result+=test[i];
}
return result;
}
public static boolean isValid(ArrayList<Integer> test,int check){
if(test.size()<2){
return false;
}
if(test.size()==2){
if((test.get(1)!=test.get(0))&&(test.get(1)!=test.get(0)+1)){
return false;
}
String o1=String.valueOf(test.get(0))+String.valueOf(test.get(1));
String o2=String.valueOf(check);
if(o1.equals(o2)){
return true;
}
return false;
}
String o1=String.valueOf(test.get(0))+String.valueOf(test.get(1));
for(int i=2;i!=test.size();i++){
if(test.get(i)!=test.get(i-1)+test.get(i-2)){
return false;
}
o1+=String.valueOf(test.get(i));
}
if(o1.equals(String.valueOf(check))){
return true;
}
return false;
}
public static void main(String[] args) {
int test=1235813;
ArrayList<Integer> results=return_results(test);
if(results!=null){
for(int i=0;i!=results.size();i++){
System.out.println(results.get(i)+" ");
}
}
else{
System.out.println("OPPS");
}
}
}
public static int Rand_3(){
return (int)(Math.random()*3)+1;
}
public static int Rand_9(){
return (Rand_3()*3)-(Rand_3()-1);
}
package amazon;
import java.util.ArrayList;
public class Divide_A_B {
public static String divide_A_B(int A,int B){
String results="";
if(A%B==0){
results=String.valueOf(A/B);
return results;
}
ArrayList<String> map=new ArrayList<String>();
int begin_maybe=0;
if(A>B){
results=String.valueOf(A/B)+".";
begin_maybe=results.length();
A=(A%B);
}
else{
results="0.";
begin_maybe=2;
}
while(A!=0){
int hasIndex=checkWhetherHasReturnIndex(map,String.valueOf(A));
if(hasIndex!=-1){
results=results.substring(0,begin_maybe+hasIndex)+"("+
results.substring(begin_maybe+hasIndex,results.length())+")";
break;
}
map.add(String.valueOf(A));
A=A*10;
results+=String.valueOf(A/B);
A=(A%B);
}
return results;
}
public static int checkWhetherHasReturnIndex(ArrayList<String> map,String obj){
for(int i=0;i!=map.size();i++){
if(map.get(i).equals(obj)){
return i;
}
}
return -1;
}
public static void main(String[] args) {
System.out.println(divide_A_B(4,8));
System.out.println(divide_A_B(9,5));
System.out.println(divide_A_B(2,10000));
System.out.println(divide_A_B(22,7));
}
}
This solution is O(n*logn)
- Chengyun Zuo October 08, 2012