Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:给几个数据给大家。借鉴

Posted by skyencc at 2010-03-26 08:46:02 on Problem 1002
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator