| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:给几个数据给大家。借鉴In Reply To:给几个数据给大家。借鉴 Posted by:fbixiaozc135 at 2007-08-05 01:21:19 前面测试数据全过了,还是WA,为什么呢?哪位大牛给帮忙看看!!!
import java.util.*;
public class Main1002 {
private static boolean outputed = false;
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
String pnumber = null;
PN root = null;
while(n > 0) {
cin.nextLine();
pnumber = cin.next();
PN pn = parse2StndrdPN(pnumber);
if(root == null) root = pn;
else root.insert(pn);
n--;
}
inOrderTraverse(root);
if(!outputed) System.out.println("No duplicates.");
}
private static void inOrderTraverse(PN root) {
if(root == null) return;
inOrderTraverse(root.left);
if(root.s > 1) {System.out.println(root);outputed = true;}
inOrderTraverse(root.right);
}
private static PN parse2StndrdPN(String pn) {
char [] pna = pn.toCharArray();
char [] ds = new char[8];
int l = pna.length;
char ch;
for(int i = 0, j= 0; i < l; i++) {
ch = pna[i];
if(j == 3) {ds[j++] = '-'; i--;}
else if(ch == '-') continue;
else {
ds[j++] = parseChar2Digital(ch);
}
}
return new PN(ds);
}
private static char parseChar2Digital(char ch) {
switch(ch) {
case 'A' : case 'B' : case 'C' : return '2';
case 'D' : case 'E' : case 'F' : return '3';
case 'G' : case 'H' : case 'I' : return '4';
case 'J' : case 'K' : case 'L' : return '5';
case 'M' : case 'N' : case 'O' : return '6';
case 'P' : case 'R' : case 'S' : return '7';
case 'T' : case 'U' : case 'V' : return '8';
case 'W' : case 'X' : case 'Y' : return '9';
case '1' : case '2' : case '3' :case '4' : case '5' :
case '6' : case '7' : case '8' :case '9' : case '0' : return ch;
default : return '?';
}
}
static class PN {
private int s = 0;
private char [] fn = null;
private int hash = 0;
private PN left = null;
private PN right = null;
public PN(char [] fn) {
this.fn = fn;
s = 1;
hash = hashCode();
}
public void increase() {
s++;
}
public String toString() {
return String.valueOf(fn) + " " + s;
}
public int hashCode() {
int h = hash;
if (h == 0) {
char val[] = fn;
int len = fn.length;
for (int i = 0; i < len; i++) {
h = 7*h + val[i];
}
hash = h;
}
return h;
}
public boolean equals(Object o) {
if(!(o instanceof PN)) return false;
if(this.hashCode() == o.hashCode()) return true;
else return false;
}
public void insert(PN pn) {
if(pn == null) return;
if(this.hash > pn.hash ) {
if(this.left == null) this.left = pn;
else this.left.insert(pn);
} else if(this.equals(pn)) {
this.increase();
} else {
if(this.right == null) this.right = pn;
else this.right.insert(pn);
}
}
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator