Chengyun Zuo
BAN USERpublic static ArrayList<String> get_anagrams_results(String[] test,String aim){
ArrayList<String> results=new ArrayList<String>();
for(int i=0;i!=test.length;i++){
if(isAnagrams(test[i],aim)){
results.add(test[i]);
}
}
return results;
}
public static boolean isAnagrams(String o1,String o2){
if(o1.length()!=o1.length()){
return false;
}
int[] holdChar=new int[256];
for(int i=0;i!=o1.length();i++){
holdChar[(int)o1.charAt(i)]++;
}
for(int i=0;i!=o2.length();i++ ){
if(--holdChar[(int)o2.charAt(i)]==-1){
return false;
}
}
return true;
}
My code can work:
public static ArrayList<String> Serialize(BinaryTreeNode head){
ArrayList<String> arrayTree=new ArrayList<String>();
serializeProcess(head,arrayTree);
return arrayTree;
}
public static void serializeProcess(BinaryTreeNode head,ArrayList<String> arrayTree){
if(head==null){
arrayTree.add("#");
return;
}
arrayTree.add(String.valueOf(head.value));
serializeProcess(head.leftchild, arrayTree);
serializeProcess(head.rightchild, arrayTree);
}
public static BinaryTreeNode Reconstruct(ArrayList<String> map){
Stack<BinaryTreeNode> holdNode=new Stack<BinaryTreeNode>();
HashMap<BinaryTreeNode,Boolean> definedLeft=new HashMap<BinaryTreeNode,Boolean>();
BinaryTreeNode result=new BinaryTreeNode(Integer.valueOf(map.get(0)));
holdNode.push(result);
for(int i=1;i!=map.size();i++){
BinaryTreeNode current=holdNode.pop();
if(!definedLeft.containsKey(current)){
definedLeft.put(current, true);
if(!map.get(i).equals("#")){
current.leftchild=new BinaryTreeNode(Integer.valueOf(map.get(i)));
holdNode.push(current);
holdNode.push(current.leftchild);
}
else{
holdNode.push(current);
}
}
else{
if(!map.get(i).equals("#")){
current.rightchild=new BinaryTreeNode(Integer.valueOf(map.get(i)));
holdNode.push(current.rightchild);
}
}
}
return result;
}
package google;
public class Plusplus_Operator_Array {
public static int[] plusplusOperator(int[] test){
boolean whether_add=true;
for(int i=0;i!=test.length;i++){
if((test[i]<0)||(test[i]>9)){
System.out.println("int[] err!");
return null;
}
else if(test[i]!=9){
whether_add=false;
break;
}
}
if(whether_add){
int[] result=new int[test.length+1];
result[0]=1;
for(int i=1;i!=result.length;i++){
result[i]=0;
}
return result;
}
else{
int[] result=new int[test.length];
int add_value=1;
for(int i=test.length-1;i>=0;i--){
if(test[i]+add_value==10){
add_value=1;
result[i]=0;
}
else{
result[i]=test[i]+add_value;
add_value=0;
}
}
return result;
}
}
public static void main(String[] args) {
int[] test=new int[]{9,9,9,9};
int[] plus_plus_result=plusplusOperator(test);
for(int i=0;i!=plus_plus_result.length;i++){
System.out.print(plus_plus_result[i]+" ");
}
}
}
if int[] test=new int[]{9,9,9,9};
Your result: {1,0,0,0};
But it should be[1,0,0,0,0]
package google;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
public class Get_All_Compute_Results {
public static ArrayList<Integer> compute(int[] test,int begin,int end,
ArrayList<Integer> deal,HashMap<Integer,String> resultsStore){
if(begin==end){
deal.add(test[begin]);
resultsStore.put(test[begin], String.valueOf(test[begin]));
return deal;
}
HashMap<Integer,Boolean> keep=new HashMap<Integer,Boolean>();
if(begin==end-1){
resultsStore.put(test[begin]+test[end],"("+String.valueOf(test[begin])+"+"+String.valueOf(test[end])+")");
deal.add(test[begin]+test[end]);
keep.put(test[begin]+test[end], true);
if(!keep.containsKey(test[begin]-test[end])){
resultsStore.put(test[begin]-test[end],"("+String.valueOf(test[begin])+"-"+String.valueOf(test[end])+")");
deal.add(test[begin]-test[end]);
keep.put(test[begin]-test[end], true);
}
if(!keep.containsKey(test[begin]*test[end])){
resultsStore.put(test[begin]*test[end],"("+String.valueOf(test[begin])+"*"+String.valueOf(test[end])+")");
deal.add(test[begin]*test[end]);
keep.put(test[begin]*test[end], true);
}
if(test[end]!=0){
if(!keep.containsKey(test[begin]/test[end])){
resultsStore.put(test[begin]/test[end],"("+String.valueOf(test[begin])+"/"+String.valueOf(test[end])+")");
deal.add(test[begin]/test[end]);
keep.put(test[begin]/test[end], true);
}
}
return deal;
}
for(int let=begin;let!=end;let++){
HashMap<Integer,String> leftStore=new HashMap<Integer,String>();
HashMap<Integer,String> rightStore=new HashMap<Integer,String>();
ArrayList<Integer> left=compute(test,begin,let,new ArrayList<Integer>(),leftStore);
ArrayList<Integer> right=compute(test,let+1,end,new ArrayList<Integer>(),rightStore);
for(int i=0;i!=left.size();i++){
String leftPart=leftStore.get(left.get(i));
for(int j=0;j!=right.size();j++){
if(!keep.containsKey(left.get(i)+right.get(j))){
String rightPart=rightStore.get(right.get(j));
resultsStore.put(left.get(i)+right.get(j),"("+leftPart+"+"+rightPart+")");
deal.add(left.get(i)+right.get(j));
keep.put(left.get(i)+right.get(j), true);
}
if(!keep.containsKey(left.get(i)-right.get(j))){
String rightPart=rightStore.get(right.get(j));
resultsStore.put(left.get(i)-right.get(j),"("+leftPart+"-"+rightPart+")");
deal.add(left.get(i)-right.get(j));
keep.put(left.get(i)-right.get(j), true);
}
if(!keep.containsKey(left.get(i)*right.get(j))){
String rightPart=rightStore.get(right.get(j));
resultsStore.put(left.get(i)*right.get(j),"("+leftPart+"*"+rightPart+")");
deal.add(left.get(i)*right.get(j));
keep.put(left.get(i)*right.get(j), true);
}
if(right.get(j)!=0){
if(!keep.containsKey(left.get(i)/right.get(j))){
String rightPart=rightStore.get(right.get(j));
resultsStore.put(left.get(i)/right.get(j),"("+leftPart+"/"+rightPart+")");
deal.add(left.get(i)/right.get(j));
keep.put(left.get(i)/right.get(j), true);
}
}
}
}
}
return deal;
}
public static void main(String[] args) {
int [] test=new int[]{4,5,4,6};
HashMap<Integer,String> resultsStore=new HashMap<Integer,String>();
ArrayList<Integer> results=compute(test,0,test.length-1,new ArrayList<Integer>(),resultsStore);
Collections.sort(results);
for(int i=0;i!=results.size();i++){
System.out.println(resultsStore.get(results.get(i))+"="+results.get(i));
}
}
}
package amazon;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
public class Get_All_Possible_Results {
public static ArrayList<Integer> compute(int[] test,int begin,int end, ArrayList<Integer> deal){
if(begin==end){
deal.add(test[begin]);
return deal;
}
HashMap<Integer,Boolean> keep=new HashMap<Integer,Boolean>();
if(begin==end-1){
deal.add(test[begin]+test[end]);
keep.put(test[begin]+test[end], true);
if(!keep.containsKey(test[begin]-test[end])){
deal.add(test[begin]-test[end]);
keep.put(test[begin]-test[end], true);
}
if(!keep.containsKey(test[begin]*test[end])){
deal.add(test[begin]*test[end]);
keep.put(test[begin]*test[end], true);
}
if(test[end]!=0){
if(!keep.containsKey(test[begin]/test[end])){
deal.add(test[begin]/test[end]);
keep.put(test[begin]/test[end], true);
}
}
return deal;
}
for(int let=begin;let!=end;let++){
ArrayList<Integer> left=compute(test,begin,let,new ArrayList<Integer>());
ArrayList<Integer> right=compute(test,let+1,end,new ArrayList<Integer>());
for(int i=0;i!=left.size();i++){
for(int j=0;j!=right.size();j++){
if(!keep.containsKey(left.get(i)+right.get(j))){
deal.add(left.get(i)+right.get(j));
keep.put(left.get(i)+right.get(j), true);
}
if(!keep.containsKey(left.get(i)-right.get(j))){
deal.add(left.get(i)-right.get(j));
keep.put(left.get(i)-right.get(j), true);
}
if(!keep.containsKey(left.get(i)*right.get(j))){
deal.add(left.get(i)*right.get(j));
keep.put(left.get(i)*right.get(j), true);
}
if(right.get(j)!=0){
if(!keep.containsKey(left.get(i)/right.get(j))){
deal.add(left.get(i)/right.get(j));
keep.put(left.get(i)/right.get(j), true);
}
}
}
}
}
return deal;
}
public static void main(String[] args) {
int [] test=new int[]{6,6,4,4};
ArrayList<Integer> results=compute(test,0,test.length-1,new ArrayList<Integer>());
Collections.sort(results);
for(int i=0;i!=results.size();i++){
System.out.println(results.get(i));
}
}
}
public class Find_First_Instance_In_Sorted_Array {
public static int find_first(int[] test,int aim){
int result_index=find(test,aim,0,test.length-1);
return result_index;
}
public static int find(int[] test,int aim,int begin,int end){
if(begin==end){
if(test[begin]==aim){
return begin;
}
else{
return -1;
}
}
if(begin==end-1){
if((test[begin]==aim)||(test[end]==aim)){
if(test[begin]==aim){
return begin;
}
if(test[end]==aim){
return end;
}
}
else{
return -1;
}
}
int mid=(begin+end)/2;
if(test[mid]>aim){
return find(test,aim,begin,mid-1);
}
if(test[mid]<aim){
return find(test,aim,mid+1,end);
}
if(test[mid]==aim){
return find(test,aim,begin,mid-1)!=-1?find(test,aim,begin,mid-1):mid;
}
return -1;
}
public static void main(String[] args) {
int[] test=new int[]{1,2,3,3,3,3,4,5,6,7,7,8};
int aim=3;
int result_index=find_first(test,aim);
System.out.println(result_index);
}
}
Here is my code, I implement two solutions:
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
public class Problem_7_find_lowest_common_ancessstor {
// I implement two solutions, Solution1() and Solution2()
public static BinaryTreeNode return_first_common_ancesstor(
BinaryTreeNode head,BinaryTreeNode o1,BinaryTreeNode o2){
BinaryTreeNode parent=null;
parent=Solution1(head,o1,o2);
parent=Solution2(head,o1,o2);
return parent;
}
public static BinaryTreeNode Solution1(BinaryTreeNode head,BinaryTreeNode o1,BinaryTreeNode o2){
HashMap<BinaryTreeNode,BinaryTreeNode> parentmap=new HashMap<BinaryTreeNode,BinaryTreeNode>();
Solution1_createParentmap(head,parentmap);
HashMap<BinaryTreeNode,Boolean> o1parent=new HashMap<BinaryTreeNode,Boolean>();
o1parent.put(o1, true);
BinaryTreeNode currentParento1=parentmap.get(o1);
while(currentParento1!=null){
o1parent.put(currentParento1, true);
currentParento1=parentmap.get(currentParento1);
}
BinaryTreeNode currentParento2=o2;
while(currentParento2!=null){
if(o1parent.containsKey(currentParento2)){
return currentParento2;
}
currentParento2=parentmap.get(currentParento2);
}
return null;
}
public static void Solution1_createParentmap(BinaryTreeNode head,HashMap<BinaryTreeNode,BinaryTreeNode> parentmap){
if(head==null){
System.out.println("This tree is empty!");
return ;
}
Queue<BinaryTreeNode> nodeQueue=new LinkedList<BinaryTreeNode>();
nodeQueue.add(head);
parentmap.put(head, null);
while(!nodeQueue.isEmpty()){
BinaryTreeNode currentNode=nodeQueue.poll();
if(currentNode.leftchild!=null){
parentmap.put(currentNode.leftchild,currentNode);
nodeQueue.add(currentNode.leftchild);
}
if(currentNode.rightchild!=null){
parentmap.put(currentNode.rightchild,currentNode);
nodeQueue.add(currentNode.rightchild);
}
}
}
public static BinaryTreeNode Solution2(BinaryTreeNode head,BinaryTreeNode o1,BinaryTreeNode o2){
if((!Solution2_contains_node(head,o1))||(!Solution2_contains_node(head,o2))){
return null;
}
if(o1==o2){
return o1;
}
BinaryTreeNode current=head;
while(Solution2_contains_node(current,o1)&&Solution2_contains_node(current,o2)){
if(Solution2_contains_node(current.leftchild,o1)&&Solution2_contains_node(current.leftchild,o2)){
current=current.leftchild;
continue;
}
if(Solution2_contains_node(current.rightchild,o1)&&Solution2_contains_node(current.rightchild,o2)){
current=current.rightchild;
continue;
}
break;
}
return current;
}
public static boolean Solution2_contains_node(BinaryTreeNode head,BinaryTreeNode node){
if(head==null){
return false;
}
if(head==node){
return true;
}
boolean lefthas=Solution2_contains_node(head.leftchild,node);
boolean righthas=Solution2_contains_node(head.rightchild,node);
if((lefthas)||(righthas)){
return true;
}
else{
return false;
}
}
// main function for test
public static void main(String[] args) {
BinaryTreeNode head=new BinaryTreeNode(16);
head.insertleft(new BinaryTreeNode(12));
head.insertright(new BinaryTreeNode(18));
head.leftchild.insertleft(new BinaryTreeNode(6));
head.leftchild.insertright(new BinaryTreeNode(14));
head.leftchild.rightchild.insertleft(new BinaryTreeNode(13));
head.leftchild.rightchild.insertright(new BinaryTreeNode(15));
head.rightchild.insertleft(new BinaryTreeNode(17));
head.rightchild.insertright(new BinaryTreeNode(24));
BinaryTreeNode results = return_first_common_ancesstor(
head,head.leftchild.rightchild.leftchild,head.rightchild.leftchild);
System.out.println(results.value);
}
}
class Number_Pool{
private HashMap<Integer,Boolean> invalidMap;
public Number_Pool(){
this.invalidMap=new HashMap<Integer,Boolean>();
}
public int checkout(){
for(int i=1;i!=Integer.MAX_VALUE;i++){
if(!this.invalidMap.containsKey(i)){
this.invalidMap.put(i, true);
return i;
}
}
return Integer.MAX_VALUE;
}
public void checkin(int newItem){
if(this.invalidMap.containsKey(newItem)){
this.invalidMap.remove(newItem);
}
}
}
package yahoo;
import java.util.ArrayList;
public class Divide_Two_Set_Min_Difference {
public static ArrayList<Integer> get_results(int[] test){
ArrayList<Integer> results=new ArrayList<Integer>();
int sum=computer_sum(test);
System.out.println("sum: "+sum);
for(int i=sum/2;i!=sum+1;i++){
if(whether_sum(test,0,test.length-1,i,results)){
System.out.println("haha: "+i);
return results;
}
}
return null;
}
public static boolean whether_sum(int[] test,int begin,int end,
int aim,ArrayList<Integer> results){
if(aim<0){
return false;
}
if(begin>end){
return false;
}
if(test[begin]==aim){
results.add(test[begin]);
return true;
}
if(whether_sum(test,begin+1,end,aim-test[begin],results)){
results.add(test[begin]);
return true;
}
if(whether_sum(test,begin+1,end,aim,results)){
return true;
}
return false;
}
public static int computer_sum(int[] test){
int sum=0;
for(int i=0;i!=test.length;i++){
sum+=test[i];
}
return sum;
}
public static void show(ArrayList<Integer> results){
for(int i=0;i!=results.size();i++){
System.out.println(results.get(i));
}
}
public static void main(String[] args) {
int[] test=new int[]{12,4,7,1,6,3,3};
ArrayList<Integer> results=get_results(test);
show(results);
}
}
package amazon;
import java.util.Stack;
class MyStack{
public Stack<Integer> basic;
public Stack<Integer> hold_min;
public MyStack(){
this.basic=new Stack<Integer>();
this.hold_min=new Stack<Integer>();
}
public void push(int newItem){
if(newItem<=this.getmin()){
this.hold_min.push(newItem);
}
this.basic.push(newItem);
}
public int pop(){
if(this.basic.isEmpty()){
return Integer.MIN_VALUE;
}
int value=this.basic.pop();
if(value==this.getmin()){
this.hold_min.pop();
}
return value;
}
public int getmin(){
if(this.hold_min.isEmpty()){
return Integer.MAX_VALUE;
}
else{
return this.hold_min.peek();
}
}
}
public class pop_push_min_in_stack{
public static void main(String[] args) {
MyStack test=new MyStack();
test.push(6);
test.push(3);
test.push(7);
System.out.println(test.getmin());
System.out.println(test.pop());
}
}
I think, firstly, you should know how many bytes of this stream.
For example, if there are 5 bytes in this stream.
Then, for the first byte:
You can use:
if ( (int)(Math.Random()*5)==0 ){
Store this byte;
return this byte;
}
for the second byte:
if ( (int) (Math.Random()*4) ==0 ){
Store this byte;
return this byte;
}
.........
for the kth byte of n byte:
if ( (int) (Math.Random()*(n-k+1)) ==0 ){
Store this byte;
return this byte;
}
.....
every byte have the same probability
package google;
public class rotate_string_with_1_additional_data_and_O_n {
public static String rotate(String aim,int index){
if(index<=0){
return aim;
}
if(index>=aim.length()){
return aim;
}
char[] test=aim.toCharArray();
do_work(test,0,index,test.length-1);
return String.valueOf(test);
}
public static void do_work(char[] test,int bIndex,int mIndex,int eIndex){
if(mIndex-bIndex==eIndex-mIndex+1){
deal_char_array(test,bIndex,eIndex,(eIndex-bIndex+1)/2);
return;
}
else if(mIndex-bIndex>eIndex-mIndex+1){
int size=eIndex-mIndex+1;
deal_char_array(test,bIndex,eIndex,size);
do_work(test,bIndex+size,mIndex,eIndex);
}
else{
int size=mIndex-bIndex;
deal_char_array(test,bIndex,eIndex,size);
do_work(test,bIndex,bIndex+size,eIndex-size);
}
}
public static void deal_char_array(char[] test,int begin,int end,int size){
if((size>(end-begin+1)/2)||(size<1)){
System.out.println("err");
return;
}
for(int i=0;i!=size;i++){
char tmp=test[begin+i];
test[begin+i]=test[end-size+1+i];
test[end-size+1+i]=tmp;
}
}
public static void main(String[] args) {
String aim="abcde123456";
String result=rotate(aim,5);
System.out.println(result);
}
}
The answer is C:
6
5 9
2 8 10
20
I write this code in eclipse, It can work...
public static boolean Whether_Balance(BinaryTreeNode head){
if(check_process(head,1)!=-1){
return true;
}
return false;
}
public static int check_process(BinaryTreeNode head,int height){
if((head.leftchild==null)&&(head.rightchild==null)){
return height;
}
else if((head.leftchild!=null)&&(head.rightchild!=null)){
int height_left=check_process(head.leftchild,height+1);
int height_right=check_process(head.rightchild,height+1);
if((height_left==-1)||(height_right==-1)){
return -1;
}
else if(height_left!=height_right){
return -1;
}
else
return height_left;
}
else
return -1;
}
public static void reverse(Stack<Integer> test){
if(test.isEmpty()){
return;
}
int i= get_and_remove_last(test);
reverse(test);
test.push(i);
}
public static int get_and_remove_last(Stack<Integer> test){
int result=test.pop();
if(test.isEmpty()){
return result;
}
else{
int last=get_and_remove_last(test);
test.push(result);
return last;
}
}
public static LinkedListNode My_BinaryTree_to_LinkedList(BinaryTreeNode head){
- Chengyun Zuo August 09, 2012if(head==null){
return null;
}
if(head.leftchild==null&&head.rightchild==null){
return new LinkedListNode(head.value);
}
LinkedListNode left=My_BinaryTree_to_LinkedList(head.leftchild);
LinkedListNode right=My_BinaryTree_to_LinkedList(head.rightchild);
LinkedListNode newhead=new LinkedListNode(head.value);
if(left==null){
newhead.next=right;
return newhead;
}
if(right==null){
newhead.next=left;
return newhead;
}
LinkedListNode current=left;
while(current.next!=null){
current=current.next;
}
current.next=right;
newhead.next=left;
return newhead;
}