Untitled
plain_text
2 months ago
7.0 kB
2
Indexable
Never
//package Family_tree; import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.TreeSet; class UserSolution { class Node { String name; int firstday; int lastday; int child; Node parent; String lc; int level; public Node(String name, int firstday, int lastday, int level) { super(); this.name = name; this.firstday = firstday; this.lastday = lastday; this.parent = null; this.level = level; this.lc=""; } } String charttoString(char[] a) { int i = 0; String str = ""; while (a[i] != '\0') { str += a[i]; i++; } return str; } HashMap<String, Node> nodeMap; int[] time; int[][] time1; void init(char mAncestor[], int mDeathday) { time=new int[1001]; time1=new int[1001][1001]; nodeMap=new HashMap<String, UserSolution.Node>(); String str=charttoString(mAncestor); Node root=new Node(str, 0, mDeathday, 0); nodeMap.put(str, root); updateTime(0, mDeathday); return; } int add(char mName[], char mParent[], int mBirthday, int mDeathday) { String str=charttoString(mName); Node parent=nodeMap.get(charttoString(mParent)); Node child=new Node(str,mBirthday,mDeathday,parent.level+1); child.parent=parent; if(parent.child==0){ child.lc=parent.lc+"L"; } else{ child.lc=parent.lc+"R"; } parent.child++; nodeMap.put(str, child); updateTime(mBirthday, mDeathday); return child.level; } int distance(char mName1[], char mName2[]) { int ans=0; Node node1=nodeMap.get(charttoString(mName1)); Node node2=nodeMap.get(charttoString(mName2)); int min=Math.min(node1.lc.length(), node2.lc.length()); for(int i=0;i<min;i++){ if(node1.lc.charAt(i)!=node2.lc.charAt(i)){ break; } ans++; } // while(node1!=node2){ // if(node1.level>node2.level){ // ans++; // node1=node1.parent; // } // else if(node1.level<node2.level){ // ans++; // node2=node2.parent; // } // else{ // ans+=2; // node1=node1.parent; // node2=node2.parent; // } // } return node1.lc.length()+node2.lc.length()-2*ans; } void updateTime(int start,int end){ int startrow=start/1000; int startcol=start%1000; int endrow=end/1000; int endcol=end%1000; if(startrow==endrow){ for(int i=startcol;i<=endcol;i++){ time1[startrow][i]++; } } else{ for(int i=startcol;i<=1000;i++){ time1[startrow][i]++; } for(int i=0;i<=endcol;i++){ time1[endrow][i]++; } for(int i=startrow+1;i<endrow;i++){ time[i]++; } } } int count(int mDay) { int start=mDay/1000; int end=mDay%1000; int ans=time[start]+time1[start][end]; return ans; } } package String_Management; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; class UserSolution { class Node{ char id; Node prev; Node next; public Node(char id) { super(); this.id = id; this.prev = null; this.next = null; } void delete(){ connect(prev,next); } } class DoubleLL{ Node head,tail; public DoubleLL() { this.head = new Node(' '); this.tail = new Node(' '); connect(head,tail); } void reset(){ connect(head,tail); } boolean isEmpty(){ return head.next==tail; } void addLast(Node s){ connect(tail.prev, s); connect(s,tail); } void addFisrt(Node s){ connect(s,head.next); connect(head,s); } } void connect(Node a,Node b){ a.next=b; b.prev=a; } boolean Reverse; DoubleLL LL; int[] count1; int[][] count2; int[][][]count3; int[][][][] count4; void init(char mStr[]) { //String str=charttoString(mStr); count1=new int[26]; count2=new int[26][26]; count3=new int[26][26][26]; count4=new int[26][26][26][26]; LL=new DoubleLL(); LL.reset(); Reverse=false; int j=0; while(mStr[j]!='\0'){ Node node=new Node(mStr[j]); LL.addLast(node); count1[mStr[j]-'a']++; if(j>=1){ count2[mStr[j-1]-'a'][mStr[j]-'a']++; } if(j>=2){ count3[mStr[j-2]-'a'][mStr[j-1]-'a'][mStr[j]-'a']++; } if(j>=3){ count4[mStr[j-3]-'a'][mStr[j-2]-'a'][mStr[j-1]-'a'][mStr[j]-'a']++; } j++; } } void appendWord(char mWord[]) { if(Reverse){ int i=0; while(mWord[i]!='\0'){ Node node=new Node(mWord[i]); //LL.addFisrt(node); count1[mWord[i]-'a']++; count2[mWord[i]-'a'][LL.head.next.id-'a']++; count3[mWord[i]-'a'][LL.head.next.id-'a'][LL.head.next.next.id-'a']++; count4[mWord[i]-'a'][LL.head.next.id-'a'][LL.head.next.next.id-'a'][LL.head.next.next.next.id-'a']++; LL.addFisrt(node); i++; } } else{ int i=0; while(mWord[i]!='\0'){ Node node=new Node(mWord[i]); //LL.addLast(node); count1[mWord[i]-'a']++; count2[LL.tail.prev.id-'a'][mWord[i]-'a']++; count3[LL.tail.prev.prev.id-'a'][LL.tail.prev.id-'a'][mWord[i]-'a']++; count4[LL.tail.prev.prev.prev.id-'a'][LL.tail.prev.prev.id-'a'][LL.tail.prev.id-'a'][mWord[i]-'a']++; LL.addLast(node); i++; } } } void cut(int k) { if(Reverse){ while(k>0){ Node node=LL.head.next; count1[node.id-'a']--; count2[node.id-'a'][node.next.id-'a']--; count3[node.id-'a'][node.next.id-'a'][node.next.next.id-'a']--; count4[node.id-'a'][node.next.id-'a'][node.next.next.id-'a'][node.next.next.next.id-'a']--; node.delete(); k--; } } else{ while(k>0){ Node node=LL.tail.prev; count1[node.id-'a']--; count2[node.prev.id-'a'][node.id-'a']--; count3[node.prev.prev.id-'a'][node.prev.id-'a'][node.id-'a']--; count4[node.prev.prev.prev.id-'a'][node.prev.prev.id-'a'][node.prev.id-'a'][node.id-'a']--; node.delete(); k--; } } } void reverse() { if(Reverse){ Reverse=false; return; } Reverse=true; } int countOccurrence(char mWord[]) { int ans=0; if(Reverse){ int j=0; while(mWord[j]!='\0'){ if(j==0){ ans=count1[mWord[j]-'a']; } if(j>=1){ ans=count2[mWord[j]-'a'][mWord[j-1]-'a']; } if(j>=2){ ans=count3[mWord[j]-'a'][mWord[j-1]-'a'][mWord[j-2]-'a']; } if(j>=3){ ans=count4[mWord[j]-'a'][mWord[j-1]-'a'][mWord[j-2]-'a'][mWord[j-3]-'a']; } j++; } } else{ int j=0; while(mWord[j]!='\0'){ if(j==0){ ans=count1[mWord[j]-'a']; } if(j>=1){ ans=count2[mWord[j-1]-'a'][mWord[j]-'a']; } if(j>=2){ ans=count3[mWord[j-2]-'a'][mWord[j-1]-'a'][mWord[j]-'a']; } if(j>=3){ ans=count4[mWord[j-3]-'a'][mWord[j-2]-'a'][mWord[j-1]-'a'][mWord[j]-'a']; } j++; } } return ans; } }