当前位置:首页 » Project Euler » 详细页

Anagramic squares 题号:98 难度: 35 中英对照

By replacing each of the letters in the word CARE with 1, 2, 9, and 6 respectively, we form a square number: 1296 = 362. What is remarkable is that, by using the same digital substitutions, the anagram, RACE, also forms a square number: 9216 = 962. We shall call CARE (and RACE) a square anagram word pair and specify further that leading zeroes are not permitted, neither may a different letter have the same digital value as another letter.

Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, find all the square anagram word pairs (a palindromic word is NOT considered to be an anagram of itself).

What is the largest square number formed by any member of such a pair?

NOTE: All anagrams formed must be contained in the given text file.

Solution

先读取文件内所有数据,按照字符串长度分为不同的ArrayList储存,随后对同一个ArrayList的内容用两层循环枚举两个字符串a和b,此时a和b的长度相同,之后进行如下判定: 1. a和b的字母组成是否一致(即b是否是a的重排) 如果满足上述条件,则: 1. 分配一个位数等于a的长度的完全平方数给a,明确其字母-数字的对应关系。 2. 如果存在一个字母对应不同数字、一个数字有多个字母对应的情况,则枚举下一个位数满足条件的完全平方数 3. 按照对应关系计算字符串b对应的数字 4. 判定b对应的数字是否有前导零(即判断该数字的位数是否和字符串a的长度一样) 5. 判定b对应的数字是否是完全平方数 对所有满足上述条件的a和b的对应的两个数字取较大值,即为答案。

Code

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;

public final class p98 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }	
    static public String run(){
		String fileName="p098_words.txt";
		HashMap<Integer,ArrayList<String>> words=new HashMap<Integer,ArrayList<String>>();
		try(FileReader fr=new FileReader(fileName);
				BufferedReader in = new BufferedReader(fr);){
			String line;
			while((line=in.readLine())!=null){
				String tmp[]=line.split(",");
				for(String s:tmp){
					String ss=s.substring(1,s.length()-1);
					if(words.containsKey(ss.length()))
						words.get(ss.length()).add(ss);
					else{
						ArrayList<String> t=new ArrayList<String>();
						t.add(ss);
						words.put(ss.length(),t);
					}
				}
			}
		}catch(IOException e){
			e.printStackTrace();
			return null;
		}
		int ans=0;
		//找出相同字母的单词对a和b
		for(HashMap.Entry<Integer,ArrayList<String>> t:words.entrySet()){
			ArrayList<String> list=t.getValue();
			for(int i=0;i<list.size();i++) for(int j=i+1;j<list.size();j++){
				String a=list.get(i);
				String b=list.get(j);
				//判断a和b是不是相同字母组成
				if(!a.equals(b) && check(a,b)){
					//具体计算
					int res=dowith(a,b);
					if(ans<res)
						ans=res;
					}
			}
		}
		return Integer.toString(ans);
    }
    static public final boolean check(String a,String b){
    	int cnt[]=new int[26];
    	for(int i=0;i<a.length();i++){
    		cnt[a.charAt(i)-'A']++;
    		cnt[b.charAt(i)-'A']--;
    	}
    	for(int i=0;i<26;i++) if(cnt[i]!=0) return false;
    	return true;
    }
    static public final int dowith(String a,String b){
    	int n=a.length();
    	int ans=0;
    	for(int i=1;;i++){
    		int x=i*i;
    		int wx=weishu(x);
    		if(wx<n) continue;
    		if(wx>n) break;
    		//现在x是一个完全平方数,而且位数恰好为n
    		int[] xx=weishu2(x);
    		int[] f=new int[26];
    		for(int j=0;j<26;j++) f[j]=-1;
    		boolean vis[]=new boolean[10];//记录0-9有没有被对应
    		for(int j=0;j<10;j++) vis[j]=false;
    		
    		boolean ok=true;
    		for(int j=0;j<n&&ok;j++){
    			if(f[a.charAt(j)-'A']<0)
    				f[a.charAt(j)-'A']=xx[j];
    			else if(f[a.charAt(j)-'A']!=xx[j])
    				ok=false;//该字符被对应到不同的数字了
    			if(vis[xx[j]])
    				ok=false;//数字xx[j]已经被对应过了
    			else vis[xx[j]]=true;
    		}
    		if(ok==false)
    			continue;//对应关系不正确
    		//对应完毕,映射关系是数组f
    		int y=0;
    		for(int j=0;j<n;j++){
    			y*=10;
    			y+=f[b.charAt(j)-'A'];
    		}
    		//y是b对应的数字,判断是否有前导零以及是否为完全平方数
    		if(weishu(y)!=n)
    			continue;
    		int ty=(int)Math.sqrt(y);
    		if(ty*ty!=y)
    			continue;//不是完全平方数
    		//是完全平方数,加入答案
    		ans=Math.max(ans,Math.max(x, y));
    	}
    	return ans;
    }
    //计算一个数的十进制位数
    static public final int weishu(int a){
    	int res=0;
    	while(a!=0){
    		a/=10;
    		res++;
    	}
    	return res;
    }
    static public final int[] weishu2(int a){
    	int n=weishu(a);
    	int res[]=new int[n];
    	for(int i=0;i<n;i++){
    		res[i]=a%10;
    		a/=10;
    	}
    	//reverse res[]
    	for(int i=0;i*2<n;i++){
    		int x=res[i];
    		res[i]=res[n-1-i];
    		res[n-1-i]=x;
    	}
    	return res;
    }
}
18769
59ms