查找字符串中最常见的字符

Question

我已经开始尝试解决TopCoder问题了。“StringDup”问题要求我们：

创建一个名为StringDup的类。给定一个仅由字母和数字组成的字符串，确定哪个字符在字符串中重复最多('A‘与’a‘不同)。如果有领带，则应返回字符串中第一个出现的字符(从左到右)。

有什么办法可以使我的解决方案更好或更有效吗？有什么东西我错过了吗？我对Java很陌生，我认为这是一个很好的学习方法。

public class StringDup {

    public char getMax(String word)
    {
        int characterCount = 0;
        int maxCharacter = 0;
        char maxCharacterChar = '.';

        char[] cArray = word.toCharArray();

        for(int i =0; i < cArray.length; i++)
        {
            int characterASCII = (int)cArray[i];
            characterCount = 0;

            //System.out.print("Chracter ASCII: " + characterASCII + "\n");
            for(int x = 0; x < cArray.length; x++)
            {
                if(characterASCII == (int)cArray[x])
                {
                    characterCount ++;
                    //System.out.print("Character Count for " + characterASCII + " " +  characterCount  + "\n");
                    if(characterCount > maxCharacter)
                    {
                        maxCharacter = characterCount;
                        maxCharacterChar = cArray[i];
                    }
                }
            }
        }
        return maxCharacterChar;
    }
}

它被称为使用主方法。

StringDup frequentChar = new StringDup();
System.out.print(frequentChar.getMax("sssdkljgh"));

Answer 1

你的算法有两个循环，这是不必要的。

这个问题是为了寻找一个特殊的“诡计”要做.这个诀窍是用相反的顺序处理数据.

考虑一下这个循环：

public static char getMax(String word) {
    if (word == null || word.isEmpty()) {
        throw new IllegalArgumentException("input word must have non-empty value.");
    }
    char maxchar = ' ';
    int maxcnt = 0;
    // if you are confident that your input will be only ascii, then this array can be size 128.
    int[] charcnt = new int[Character.MAX_VALUE + 1];
    for (int i = word.length() - 1; i >= 0; i--) {
        char ch = word.charAt(i);
        // increment this character's cnt and compare it to our max.
        if (++charcnt[ch] >= maxcnt) {
            maxcnt = charcnt[ch];
            maxchar = ch;
        }
    }
    return maxchar;
}

注意以下几点：

• 验证输入。
• 为每个字符创建一个计数器数组。
• 向后工作..。如果这是最大计数(或等于它)，那么我们有一个新的赢家。
• 输入字符没有验证.您可能应该将字符限制为指定的a-zA-Z0-9集.上面的解决方案将适用于任何字符串。

一些额外的笔记..。

• 在Java中，标准代码样式将打开的{大括号放在与块声明(if条件、方法声明等)相同的行上。把支撑放在一个新的线上是一个C的事情做，并被皱眉。
• x不是任何事物的好变量名，除非它是多维数组中的协调器(通常与(x, y, ...)链接)。在您的用例中，您应该使用变量j，因为这是按照约定在i循环中使用的变量。

Answer 2

当前，如果输入无效(例如，空字符串)，则返回.。它不在规范中，所以我认为它不应该这样做。早早坠机。当它用无效的输入调用方法时，它是客户端代码中的一个错误。客户可能会对意想不到的.结果产生更大的副作用。我会在这里扔一个IllegalStateException。参见:实用程序员:从熟练工人到硕士，由安德鲁亨特和大卫托马斯:死程序告诉没有谎言。

如果允许使用外部库，则可以使用番石榴的MultisetS和Iterables以更高的抽象级别编写它：

import static com.google.common.base.Preconditions.checkArgument;

import java.util.List;

import org.apache.commons.lang3.StringUtils;

import com.google.common.base.CharMatcher;
import com.google.common.base.Predicate;
import com.google.common.collect.Iterables;
import com.google.common.collect.LinkedHashMultiset;
import com.google.common.collect.Multiset;
import com.google.common.collect.Multisets;
import com.google.common.primitives.Chars;

public class StringDup {

    public char getMax(final String word) {
        checkArgument(StringUtils.isNotEmpty(word), 
            "empty input is not allowed");

        final Predicate<Character> allValidPredicate 
                = new Predicate<Character>() {
            @Override
            public boolean apply(final Character c) {
                return CharMatcher.JAVA_LETTER_OR_DIGIT.matches(c);
            }
        };

        final List<Character> inputCharList 
            = Chars.asList(word.toCharArray());
        final Iterable<Character> validInputChars 
            = Iterables.filter(inputCharList, allValidPredicate);
        final Multiset<Character> countedChars 
            = LinkedHashMultiset.create(validInputChars);
        checkArgument(!countedChars.isEmpty(), 
            "Input does not contain any valid chars: %s", word);
        final Multiset<Character> highestCountFirst 
            = Multisets.copyHighestCountFirst(countedChars);
        return highestCountFirst.iterator().next();
    }
}

最后，使用JUnit进行一些单元测试，以确保它按预期工作：

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class StringDupTest {

    @Test(expected = IllegalArgumentException.class)
    public void testNullInput() throws Exception {
        getMax(null);
    }

    @Test(expected = IllegalArgumentException.class)
    public void testEmptyStringInput() throws Exception {
        getMax("");
    }

    @Test
    public void test() {
        assertEquals('h', getMax("asdfffhjhhhhx"));
        assertEquals('f', getMax("asdfffhj#hfhhx"));
        assertEquals('A', getMax("AAaa"));
        assertEquals('a', getMax("AAaaa"));
        assertEquals('a', getMax("a"));
        assertEquals('a', getMax("a2"));
        assertEquals('2', getMax("a22"));
    }

    @Test(expected = IllegalArgumentException.class)
    public void testOnlyInvalidChars() throws Exception {
        getMax("#");
    }

    private char getMax(final String input) {
        return new StringDup().getMax(input);
    }
}