最近有人问了一个解决hackerrank问题的问题:在岩石中计数宝石

挑战的描述是:


约翰发现了各种岩石。每个岩石都由各种
元素组成,并且每个元素都由从'a'到'z'的小写拉丁字母
表示。一个元素可以在岩石中多次出现。
如果元素在每个岩石中至少出现一次,则称为“宝石元素”。

给定列表中的岩石及其成分,您必须打印出
他拥有许多不同种类的宝石元素。

输入格式

第一行包括N,岩石的数量。接下来的N
行中的每一行都包含岩石的成分。每个成分都由小的英语
字母组成。

输出格式

打印出他拥有的各种宝石元素的数量。

约束

\ $ 1≤N≤100 \ $

每个组合仅包含小的拉丁字母('a'-'z')。 1≤每种成分的长度≤100

样品输入

3
abcdde
baccd
eeabg 


样品输出

2 


说明

只有“ a”,“ b”是两种宝石元素,因为这些特征出现在每个岩石的组成物中。


由于问题中的代码未能产生正确的结果,因此我在编写问题的答案时正在编写答案。

我建议的解决方案可能相当快,但也相对复杂。我确定可以改进和简化它。

我提供了一个简单的main方法,该方法说明了如何使用它并产生示例输出。

public class GemCounter {

    private static final int LETTERCOUNT = 26; 

    // Start with 1 bit set for each element/letter.
    private int gemsSoFar = (1 << LETTERCOUNT) - 1; 

    public GemCounter() {
        // default constructor. Does nothing.
    }

    public void processRock(final String rock) {
        int gotElement = 0; // no bits are set.
        for (int i = 0; i < rock.length(); i++) {
            int element = rock.charAt(i) - 'a';
            if (element >= 0 && element < LETTERCOUNT) {
                // bitwise OR the bit that represents the element
                gotElement |= 1 << element;
            }
        }
        // only bits that were found in this rock
        // and also that have been seen before
        // will remain set.
        gemsSoFar = gemsSoFar & gotElement;
    }

    public int getGemCount() {
        // count the number of bits that are still set.
        return Integer.bitCount(gemsSoFar);
    }

    public static void main(String[] args) {
        String[] rocks = {"abcdde", "baccd", "eeabg"};

        GemCounter gemcount = new GemCounter();
        for (String rock : rocks) {
            gemcount.processRock(rock);
            System.out.printf("Processed %s, got %d gems still%n", rock, gemcount.getGemCount());
        }

        System.out.printf("%d rocks have %d gems%n", rocks.length, gemcount.getGemCount());

    }

}


评论

仅供参考,1 <<元素不是必需的;仅仅元素就足够了。 :)

#1 楼

没什么好说的。

逻辑运算符的用法有点不一致:

    gotElement |= 1 << element;
    gemsSoFar = gemsSoFar & gotElement;


在第二行中最好使用&=,或者在第一行中拼出。

gotElement尚不清楚。 rockElements,也许吗?

在现实生活中,我也反对广泛的评论。

#2 楼

您已添加

public GemCounter() {
    // default constructor. Does nothing.
}


,程序无需使用它,因为


编译器会自动提供一个无参数,任何没有构造函数的类的默认构造函数
。此默认构造函数将调用超类的无参数构造函数。在这种情况下,如果超类没有无参数的
构造函数,
编译器将抱怨,因此您必须验证它是否具有。如果您的类没有
显式超类,则它具有Object的隐式超类,
确实具有无参数构造函数[1]。


因此这也违反了YAGNI


“您根本不需要它”(缩写:YAGNI)是一种极端的编程原则(XP),指出程序员不应添加功能
,直到认为必要为止。 XP联合创始人罗恩·杰弗里斯(Ron Jeffries)写道:“总是在真正需要它们时执行事情,永远不要在您只是预见到需要它们时才执行[2]。




参考文献


[1]“为您的课程提供构造函数。” [在线]。可用:http://docs.oracle.com/javase/tutorial/java/javaOO/constructors.html。[访问:2014年8月27日]。
[2]“您不是会需要它,”维基百科,免费的百科全书。2014年8月24日。


#3 楼

这不是一个不好的解决方案。 processRock()函数的功能尚不清楚,因此为了清楚起见,我将对问题的分解方式和命名进行一些小的调整。

private static final String ALL_ELEMENTS = "abcdefghijklmnopqrstuvwxyz";
private int commonElements = bitsOfRock(ALL_ELEMENTS);

private static int bitsOfRock(String rock) {
    int bits = 0;
    for (int i = 0; i < rock.length(); i++) {
        int element = rock.charAt(i) - 'a';
        if (element >= 0 && element < ALL_ELEMENTS.length()) {
            // bitwise OR the bit that represents the element
            bits |= 1 << element;
        }
    }
    return bits;
}

public void requireElementsOfRock(String rock) {
    commonElements &= bitsOfRock(rock);
}

public int getElementCount() {
    return Integer.bitCount(commonElements);
}


更好的清晰度,以牺牲一些性能为代价,您也可以使用java.util.BitSet