java - Sherlock 和有效字符串，在 5 个测试用例中给了我错误的结果

Question

我正在尝试运行 hackerrank 的程序。这是问题:

如果字符串中的所有字符出现相同的次数，Sherlock 就会认为该字符串有效。如果他可以仅删除字符串中 one 索引处的 一个 个字符，并且其余字符将出现相同的次数，那么它也是有效的。给定一个字符串，判断它是否有效。

例如，如果 s="abc"，则它是有效字符串，因为频率为 {a:1,b:1,c:1}。 abcc 也是如此，因为我们可以删除一个 c，然后在剩余的字符串中每个字符都有 1 个。但是，如果 s='abccc' ，则该字符串无效，因为我们只能删除 1 次出现的 c 。这将留下 {a:1,b:1,c:2} 的字符频率。

这是链接: https://www.hackerrank.com/challenges/sherlock-and-valid-string/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=strings

失败的 5 个测试用例之一是:aaaabbcc 应该给出 false，但它给了我 true。aabbc 应该给出 true，但给我的是 false。

但不知何故，我的 5 个测试用例出现了错误:这是以下程序。

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

public class SherlokValidString
{

    boolean is_valid(String s)
    {
        int count=0;
        HashMap<Character, Integer> map = new HashMap<>();
        char[] str_arr= s.toCharArray();
        for(char c:str_arr)
        {
            if(map.containsKey(c))
            {
                map.put(c, map.get(c)+1);
            }
            else
            {
                map.put(c,1);
            }
        }
        if (map.size()==1)
        {
            return true;
        }
        else {

            List ll=new ArrayList<>(map.values());
            System.out.println(ll);

            Collections.sort(ll);
            int first_element=(int)ll.get(0);

            for(int i=1;i<(ll.size()-1);i++)
            {
                //System.out.println((int)ll.get(i)+1);
                if (first_element==(int)ll.get(i+1))
                {
                    count=0;
                }
                else if(first_element!=(int)ll.get(i+1))
                {
                    count++;
                }
            }
            if(count<=1)
            {
                //System.out.println(count);
                return true;
            }
            else
            {
                return false;
            }
        }
    }

    public static void main(String[] args)
    {
        SherlokValidString svs = new SherlokValidString();
        System.out.println(svs.is_valid("abbccc"));

    }
}

它应该返回 false，它给了我 true。请帮忙。谢谢。

Answer 1

使用 Java 8，人们可以完成一项非常优雅的工作:

public static boolean sherlockStr(String s) {

    // First, we're going to walk over the characters and count how many
    // times each character occurs
    Map<Character, Long> charOccurs = s.chars()
        .mapToObj(t -> (char) t)
        .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));

    // Then we're going to map each amount of characters found to its count,
    // e.g. in the string "aabbcc" each character occurs twice → [2, 2, 2].
    // That will yield a map: [2=3]
    Map<Long, Long> counts = charOccurs.entrySet().stream()
        .map(Map.Entry::getValue)
        .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));

    switch (counts.size()) {
        // If all characters occur an equal number of times, then the map
        // contains just a single entry.
        case 1:
            return true;

        // If there are two different amounts, then the difference between
        // those two must be 1. Also, one of the numbers must occur exactly
        // once.
        case 2:
            Iterator<Long> it = counts.keySet().iterator();
            boolean diff = Math.abs(it.next() - it.next()) == 1;
            return (diff && (counts.values().stream()
                .anyMatch(i -> i == 1)));

        // If the map's size is 3 or more, there are differents of amounts of
        // characters.
        default:
            return false;
    }
}

简而言之:

public static boolean sherlockStr(String s) {
    Map<Long, Long> counts = s.chars()
        .mapToObj(t -> (char) t)
        .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
        .entrySet().stream()
        .map(Map.Entry::getValue)
        .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));

    switch (counts.size()) {
        case 1:
            return true;
        case 2:
            Iterator<Long> it = counts.keySet().iterator();
            return (Math.abs(it.next() - it.next()) == 1 && (counts.values().stream()
                .anyMatch(i -> i == 1)));
        default:
            return false;
    }
}