Problem22

Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938  53 = 49714.

What is the total of all the name scores in the file?

package com.yao;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.LinkedList;
import java.util.List;
/**
 * Created by IntelliJ IDEA.
 * User: shuimuqinghua77
 * Date: 12-3-13
 * Time: 下午9:04
 */
public class Problem22 {
    public static void main(String[] args) throws IOException {
        File file=new File("C:\\Users\\Administrator\\Desktop\\names.txt");

        ///home/yaoyao/template/names.txt
        FileReader fr=new FileReader(file);
        BufferedReader br=new BufferedReader(fr);
        String namestxt=br.readLine();
        br.close();
        fr.close();
        String[] names=namestxt.split("\",\"");
        /*去除最后一个和第一个name的引号*/
        names[0]=names[0].substring(1, names[0].length());
        names[names.length-1]=names[names.length-1].substring(0,names[names.length-1].length()-1);
        /**建立一个链表  以字典序列存储名字*/
        List<String> list=new LinkedList<String>();
        int[] location=new int[26];
        long start=System.currentTimeMillis();
        for(String name:names){
            if(list.size()==0){
                location[name.charAt(0)-'A']++;
                list.add(name);
                continue;
            }
            int bigger=0;
            int insert=0;
            //获取索引位置
                int i=0;
                int x=name.charAt(0)-'A';
                for(int k=0;k<=x-1;k++){
                 i+=location[k];
                }
                for(;i<list.size();i++){
                String pre=list.get(i);
                int len=pre.length()>name.length()? name.length():pre.length();
                for(int j=0;j<len;j++){
                    if(pre.charAt(j)>name.charAt(j)){
                        bigger=1;
                        break;
                    }
                    else if(pre.charAt(j)<name.charAt(j)){
                        bigger=0;
                        break;
                    }
                    else{
                        bigger=2;
                    }
                }
                if(bigger==1||(bigger==2&&(pre.length()>name.length()))){
                    location[name.charAt(0)-'A']++;
                    list.add(i,name);
                    insert=1;
                    break;
                }
            }
            if(insert==0)list.add(name);

        }
        int sum=0;
        int a='A'-1;
        for(int i=0;i<list.size();i++){
            String name=list.get(i);
            int base=0;
            for(int j=0;j<name.length();j++){
                     base+=name.charAt(j)-a;
            }
             sum+=base*(i+1);
        }
        System.out.println(sum);
        long end=System.currentTimeMillis();
        System.out.println(end-start);

    }

}

package com.yao;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
/**
 * Created by IntelliJ IDEA.
 * User: shuimuqinghua77
 * Date: 12-3-13
 * Time: 下午9:04
 */
public class Problem22 {
    public static void main(String[] args) throws IOException {
        File file=new File("C:\\Users\\Administrator\\Desktop\\names.txt");

        ///home/yaoyao/template/names.txt
        FileReader fr=new FileReader(file);
        BufferedReader br=new BufferedReader(fr);
        String namestxt=br.readLine();
        br.close();
        fr.close();
        String[] names=namestxt.split("\",\"");
        /*去除最后一个和第一个name的引号*/
        names[0]=names[0].substring(1, names[0].length());
        names[names.length-1]=names[names.length-1].substring(0,names[names.length-1].length()-1);
        long start=System.currentTimeMillis();
        Arrays.sort(names);
    /*    *//**建立一个链表  以字典序列存储名字*//*
        List<String> list=new LinkedList<String>();
        int[] location=new int[26];
        long start=System.currentTimeMillis();
        for(String name:names){
            if(list.size()==0){
                location[name.charAt(0)-'A']++;
                list.add(name);
                continue;
            }
            int bigger=0;
            int insert=0;
            //获取索引位置
                int i=0;
                int x=name.charAt(0)-'A';
                for(int k=0;k<=x-1;k++){
                 i+=location[k];
                }
                for(;i<list.size();i++){
                String pre=list.get(i);
                int len=pre.length()>name.length()? name.length():pre.length();
                for(int j=0;j<len;j++){
                    if(pre.charAt(j)>name.charAt(j)){
                        bigger=1;
                        break;
                    }
                    else if(pre.charAt(j)<name.charAt(j)){
                        bigger=0;
                        break;
                    }
                    else{
                        bigger=2;
                    }
                }
                if(bigger==1||(bigger==2&&(pre.length()>name.length()))){
                    location[name.charAt(0)-'A']++;
                    list.add(i,name);
                    insert=1;
                    break;
                }
            }
            if(insert==0)list.add(name);

        }*/
        int sum=0;
        int a='A'-1;
        for(int i=0;i<names.length;i++){
            String name=names[i];
            int base=0;
            for(int j=0;j<name.length();j++){
                     base+=name.charAt(j)-a;
            }
             sum+=base*(i+1);
        }
        System.out.println(sum);
        long end=System.currentTimeMillis();
        System.out.println(end-start);

    }

}