3

我正在尝试实现 facebook hackathon 2013 http://argote.mx/?p=353"> 上的一个更简单的问题。

摘录： 给定一个字符串 s，小约翰尼将字符串之美定义为其中字母之美的总和。每个字母的美是 1 到 26 之间的整数，包括 1 和 26，没有两个字母具有相同的美。约翰尼不在乎字母是大写还是小写，所以这并不影响字母的美观。你是一名学生，正在写一篇关于这位著名黑客青年的报告。你找到了约翰尼认为最漂亮的绳子。这个字符串的最大可能美是什么？

我已经实现了基于将单个字母映射到特定数字的自己的解决方案。

这是代码：

package samplecodes;

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

public class StringBeauty {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        ArrayList<String> input= new ArrayList<String>();
        try{

            FileReader f1 = new FileReader(args[0]);
            BufferedReader f = new BufferedReader(f1);
            String newLine;
            while ((newLine=f.readLine()) != null){
                   StringTokenizer st = new StringTokenizer(newLine);
                   while (st.hasMoreTokens()) {
                      String string= st.nextToken(); 
                      input.add(string);

                   }

                   for(String i: input)
                       System.out.println("input "+i);
                   ///printLower(input);

                   calculateStringBeauty(input);
                   input.clear();


}

        }

            catch(Exception e){
                e.printStackTrace();
        }
    }


    public static void calculateStringBeauty(ArrayList<String> input){

        /** mapping based on analysing input string**/

        HashMap<Character,Integer> map= new HashMap<Character,Integer>();
        map.put( Character.valueOf('a'),24);
        map.put( Character.valueOf('b'),25);
        map.put( Character.valueOf('c'),26);
        map.put( Character.valueOf('d'),1);
        map.put( Character.valueOf('e'),2);
        map.put( Character.valueOf('f'),3);
        map.put( Character.valueOf('g'),4);
        map.put( Character.valueOf('h'),5);
        map.put( Character.valueOf('i'),6);
        map.put( Character.valueOf('j'),7);
        map.put( Character.valueOf('k'),8);
        map.put( Character.valueOf('l'),9);
        map.put( Character.valueOf('m'),10);
        map.put( Character.valueOf('n'),11);
        map.put( Character.valueOf('o'),12);
        map.put( Character.valueOf('p'),13);
        map.put( Character.valueOf('q'),14);
        map.put( Character.valueOf('r'),15);
        map.put( Character.valueOf('s'),16);
        map.put( Character.valueOf('t'),17);
        map.put( Character.valueOf('u'),18);
        map.put( Character.valueOf('v'),19);
        map.put( Character.valueOf('w'),20);
        map.put( Character.valueOf('x'),21);
        map.put( Character.valueOf('y'),22);
        map.put( Character.valueOf('z'),23);
        int sum=0;
        for(String i: input){
        i=i.toLowerCase();
        //  System.out.println("i "+i);
        char[] array= i.toCharArray();

        for(char a: array){
        if(map.containsKey(a))
            sum+=map.get(a);
        else
            continue;
        }

        }
        System.out.print(sum);
        System.out.println();

        }
}

我的解决方案似乎非常适合其中一个测试用例，例如 . ABbCcc-> 152，这映射正确但是So I just go consult Professor Dalves -> 392（根据我的代码）。但预计会646根据提供的测试用例返回一个美丽值。

任何帮助调试我的代码或改进我的算法的建议将不胜感激。

4

2 回答 2

2

首先，谢谢你把我的想法搞砸了：P

现在，据我了解的基本前提是，一个角色出现得越多，它就会变得越漂亮。

所以考虑到这一点，你需要找出来计算单个字符出现的次数。我正在考虑尝试一些花哨的正则表达式，但我的正则表达式技能相当差：P

相反，我选择创建一个将字符映射到事件的简单对象。实际上，您实际上并不需要该角色，但我将其用于调试。你可以简单地用一个Map<Character, Integer>代替......

您也可以轻松地使用int[]26 个元素的数组。每个元素代表一个字符（即a == 0和z == 25）

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Hack {

    public static void main(String[] args) {
        new Hack();
    }

    public Hack() {
        System.out.println("152 = " + getBeauty("ABbCcc"));
        System.out.println("754 = " + getBeauty("Good luck in the Facebook Hacker Cup this year!"));
        System.out.println("491 = " + getBeauty("Ignore punctuation, please :)"));
        System.out.println("729 = " + getBeauty("Sometimes test cases are hard to make up."));
        System.out.println("646 = " + getBeauty("So I just go consult Professor Dalves\t"));
    }

    protected int getBeauty(String value) {

        int sum = 0;
        value = value.toLowerCase();
        char[] values = value.toCharArray();
        Map<Character, Beauty> mapBeauty = new HashMap<>(26);
        for (char c : values) {
            if (Character.isLetter(c)) {
                Beauty beauty = mapBeauty.get(c);
                if (beauty == null) {
                    beauty = new Beauty(c);
                    mapBeauty.put(c, beauty);
                }
                beauty.add();
            }
        }

        List<Beauty> beauties = new ArrayList<>(mapBeauty.values());
        Collections.sort(beauties);
        int weight = 26;
        for (Beauty beauty : beauties) {
            int bweight = weight * beauty.getOccurance();
//            System.out.println(beauty.getValue() + " @ " + beauty.getOccurance() + " x " + weight + " = " + bweight);
            sum += bweight;
            weight--;
        }

        return sum;

    }

    public class Beauty implements Comparable<Beauty> {

        private char value;
        private int occurance;

        public Beauty(char value) {
            this.value = value;
            occurance = 0;
        }

        public char getValue() {
            return value;
        }

        public void add() {
            occurance++;
        }

        public int getOccurance() {
            return occurance;
        }

        @Override
        public int compareTo(Beauty o) {
            return o.getOccurance() - getOccurance();
        }

    }

}

哪个输出...

152 = 152
754 = 754
491 = 491
729 = 729
646 = 646
于 2013-04-21T09:17:23.327 回答
1

对于一个我不确定这个哈希表。实际上没有任何理由存储键和值，因为它们在字符串之间不一致。

除此之外，您应该尝试做的是确定字符串中出现最多的字符，与它的大小写或相对字母位置无关。一旦找到出现最多的那个，将其赋值为 26 乘以它出现的次数，然后将值存储在累加器中。继续下一个出现次数第二多的字符，依此类推。

ABbCcc -> c = 26，b = 25，a = 24

->-> 做数学 = 152

所以我就去咨询 Dalves 教授 -> s = 26; o = 25; u,t,r,e,l = 24 - 20; 剩下的得到 19 - 10。

->-> 做数学 = 646

希望能有所帮助！

于 2013-04-21T09:16:45.633 回答