比较 hashMap 的值

Question

我在练习一些面试问题，但不知道如何比较hashMap值。前提是您有一个带有字符串的杂志。您必须从杂志中剪下适当数量的字符以形成赎金笔记。我已经成功将字符和字符出现次数添加到了hashMap中，但如何比较这两个hashMap以确定我有足够的字母？任何指导都将不胜感激。

杂志 = {g=2, =14, d=2, e=2, a=4, n=1, o=5, l=4, m=1, .=1, k=1, I=2, h=2, i=6, w=1, T=1, u=1, t=2, s=3, r=1, y=2} 赎金笔记 = {w=1, =3, o=1, l=4, k=1, I=1, y=1, i=2}

String mag = "this is what I said Im going to do. i really like you a lot";
        String ransom = "i will kill you";

        Map<Character,Integer> map = new HashMap<Character,Integer>();
        Map<Character,Integer> ransomMap = new HashMap<Character,Integer>();

        for(int i = 0; i < mag.length() -1; i++)
        {
            char c = mag.charAt(i);
            if(!map.containsKey(c))
            map.put(c, 1);
            else{
                int value = map.get(c);
                map.put(c,++value);
            }
        }

        System.out.println(map);

        for(int i = 0; i < ransom.length()-1; i++ )
        {
        char c = ransom.charAt(i);
        if(!ransomMap.containsKey(c))
            ransomMap.put(c,1);
        else
        {
            int value = (ransomMap.get(c));
            ransomMap.put(c,++value);
        }
        }
        System.out.println(ransomMap);
    }

- Calgar99

Answer 1

检查勒索信中的每个字母，看看报纸中是否有足够的数量：

boolean enoughLetters(Map<Character, Integer> magMap, Map<Character,Integer> ransomMap) {
    for( Entry<Character, Integer> e : ransomMap.entrySet() ) {
        Character letter = e.getKey();
        Integer available = magMap.get(letter);
        if (available == null || e.getValue() > available) return false;
    }
    return true;
}

- Andrew Mao

---

谢谢，那个完美地解决了问题。为了让我清楚地理解解决方案，在ransomHashMap中的每个条目中，首先获取键（字母），然后在杂志hashmap中查找完全相同的键，同时取出附加的值。如果杂志值为空或小于当前条目值，则布尔值为false。如果杂志键不存在，这不会引起某种错误吗？ - Calgar99

如果杂志密钥不存在，则available == null。 - Andrew Mao

+1，虽然你可以使用containsKey()来避免像我一样的空值检查：if (!magMap.containsKey(letter) || magMap.get(letter).getValue() > available) return false; - ach

通常情况下，如果我最终会获取键，则不会使用 containsKey()。这可能是过早的优化，但这已经成为了我的习惯。 :) - Andrew Mao

Answer 2

Andrew的回答可行。但是我通过使用测试驱动开发（TDD）来解决了这个问题。以下是我想出的测试：

@Test
public void whenMagazineHasLessCharactersThanRansomThenYouCanCreateRansom() {
    assertFalse(canMakeRansom("abcdef", "abcdefg"));
}

@Test
public void whenMagazineHasSameCharactersOfRansomThenYouCanCreateRansom() {
    assertTrue(canMakeRansom("abcdefg", "abcdefg"));
}

@Test
public void whenMagazineHasSameCharactersOfRansomButInDifferentOrderThenYouCanCreateRansom() {
    assertTrue(canMakeRansom("abcdefg", "gfedcab"));
}

@Test
public void whenMagazineHasSameCharactersOfRansomButHasMoreThenYouCanCreateRansom() {
    assertTrue(canMakeRansom("aabbccdefg", "agfedcab"));
}

@Test
public void whenMagazineHasSameCharactersOfRansomButRansomHasMoreThenYouCantCreateRansom() {
    assertFalse(canMakeRansom("aabbccdefg", "aaaaagfedcab"));
}

左参数是杂志，右参数是赎金。这段内容太长了，不能作为评论发布，因此我使用了答案。

private boolean canMakeRansom(String magazine, String ransom) {
    Map<Character, Integer> magList = createCharCountMap(magazine);
    Map<Character, Integer> ransomList = createCharCountMap(ransom);
    return magHasAtLeastTheseCharacters(magList, ransomList);   //Andrew's implementation
}

private Map<Character, Integer> createCharCountMap(String chars) {
    HashMap<Character, Integer> charCountMap = new HashMap<Character, Integer>();
    for (char c : chars.toCharArray()) {
        if (charCountMap.containsKey(c)) {
            charCountMap.put(c, charCountMap.get(c) + 1);
        } else {
            charCountMap.put(c, 1);
        }
    }
    return charCountMap;
}

- Daniel Kaplan

---

测试驱动开发，简单来说就是在开发之前定义好你的测试用例。 - ach

我不是为了好的编程实践而想出所有这些酷炫的缩写...但是，你的 canMakeRansom 函数在哪里呢？ - Andrew Mao

你仍然缺少 magHasAtLeastTheseCharacters。 - Andrew Mao

Answer 3

如果我理解问题正确，您可以检查所有字符 [a-z A-Z 0-9 !@#$%^&()(_+{:<}">?]。

- enigma

---

我认为你没有理解这个问题 - 他在问如何比较他得到的两张地图，以及他的“map”中是否有足够的字母来生成“ransom”。 - Michael Rose

遍历ranson的键非常有意义 :) - enigma