ACM ICPC小组: Hackerank

Question

这是一个黑客简单的问题。

您将获得参加ACM世界总决赛的N人名单.他们中的每一个人要么对某个话题很熟悉，要么就不熟悉。找出一个2人团队所能知道的最多的话题数。并找出有多少团队可以知道最大数量的主题。注:假设a、b和c是三个不同的人，则(a，b)和(b，c)被计算为两个不同的团队。输入格式第一行包含两个整数，N和M，用一个空格分隔，其中N表示人数，M表示主题数。N条线跟着。每一行包含一个长度为M的二进制字符串，如果I‘the行的j’the字符为1，则I‘the人知道j’the主题；否则，他不知道该主题。约束2≤N≤5 0 0≤1≤M≤5 0 0输出格式在第一行，打印2人团队所能知道的最大主题数。在第二行中，打印能够知道主题最大数量的2人团队的数量。

以下是我所写的：

Scanner console = new Scanner(System.in);
int n = console.nextInt();
int m = console.nextInt();
console.nextLine();
String[] arr = new String[n];
for(int p=0; p<n; p++){
    String s = console.nextLine();
    arr[p] = s;
}


Map<Integer, List<List<Integer>>> counts = new HashMap<>();

for(int i = 0; i< n-1; i++){

    String str=arr[i];

    for(int j=i+1; j<n; j++){


        String secondStr = arr[j];

        int count = 0;
        for(int k=0; k<m; k++){

            if(str.charAt(k) == '1' || secondStr.charAt(k) == '1'){
                count ++;
            }

        }

        List<Integer> mapping = new ArrayList<>();
        mapping.add(i+1);
        mapping.add(j+1);

        if(counts.containsKey(count)){
            List<List<Integer>> existingMappings = counts.get(count);
            existingMappings.add(mapping);
            counts.put(count, existingMappings);
        }else{
            List<List<Integer>> newMappings = new ArrayList<>();
            newMappings.add(mapping);
            counts.put(count, newMappings);
        }


    }
}

int max = counts.keySet().stream().mapToInt(Integer::valueOf).max().orElse(0);

int occurences = counts.get(max).size();

System.out.println(max);
System.out.println(occurences);

这起了作用，并通过了挑战。但是它有一种代码气味:太多的循环，甚至内部循环。有什么改进吗？

Answer 1

这一部分可以进行一些优化，就长度而言。

List<Integer> mapping = new ArrayList<>();
mapping.add(i+1);
mapping.add(j+1);

if(counts.containsKey(count)){
    List<List<Integer>> existingMappings = counts.get(count);
    existingMappings.add(mapping);
    counts.put(count, existingMappings);
}else{
    List<List<Integer>> newMappings = new ArrayList<>();
    newMappings.add(mapping);
    counts.put(count, newMappings);
}

Java 8映射有computeIfAbsent。您可以使用它来"getOrCreate“现有映射，如下所示：

List<Integer> mapping = new ArrayList<>();
mapping.add(i+1);
mapping.add(j+1);

counts.computeIfAbsent(count, k -> new ArrayList<>()).add(mapping);

此外，您还可以这样做：

    List<List<Integer>> existingMappings = counts.get(count);
    existingMappings.add(mapping);
    counts.put(count, existingMappings);

当您检索到它时，不需要将它放回地图中，因为您正在检索指向列表的指针，并且正在使用它添加到列表中。请参阅这个德龙，它列出了您放置的列表，然后从地图中检索到的是相同的列表。

好吧，回到这个片段。

List<Integer> mapping = new ArrayList<>();
mapping.add(i+1);
mapping.add(j+1);

counts.computeIfAbsent(count, k -> new ArrayList<>()).add(mapping);

new ArrayList构造函数可以接受一个initialSize参数。因为您只需要向列表中添加两个整数，所以可以提供这些信息并节省内存空间。

List<Integer> mapping = new ArrayList<>(2);

您的算法可能会更优化--如果一个团队同时知道7个主题，并且只剩下6个主题需要检查，并且顶级团队目前知道14个主题，则不需要计算团队的主题知识。类似地，没有理由存储每个团队知道多少主题，只有知道最大数量的主题和当前发现的最大数量的主题的团队。

然而，我认为，当我们看到循环，你不能真正摆脱它们。

您知道，需要有两个循环来组成团队(在人员上迭代人员)，还有一个循环需要检查主题(遍历主题)。你可以用一些巧妙的技巧把二进制字符串转换成整数，但是当你这样做的时候，你会在二进制字符串中的字符上循环--毕竟，它必须读取字符串。你只是不使用for循环。

所以我们注定至少会有三个循环。你能做的就是把计数循环放到一个单独的函数中。这将“摆脱”其中一个循环。静态分析器的构建并不考虑到这些挑战--看到一个有3个嵌套循环的方法通常意味着该方法做了太多的工作。

Answer 2

您的解决方案不是最佳的，但您应该尝试更好的方法。

您可以使用BigInteger方法或BitSet类进行优化，并使其变得简单。

要组建一个团队，你必须使用按位或

以下是解决办法--

   // 1st approach
    static int[] acmTeam(String[] topic) {

        int n = topic.length;
        BigInteger[] bi = new BigInteger[n];

        for (int i = 0; i < n; i++)
            bi[i] = new BigInteger(topic[i], 2);

        int maxTopic = 0;
        int teamCount = 0;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                BigInteger iuj = bi[i].or(bi[j]);
                int bitCount = iuj.bitCount();
                if (bitCount > maxTopic) {
                    maxTopic = bitCount;
                    teamCount = 1;
                } else if (bitCount == maxTopic) {
                    teamCount++;
                }
            }
        }

        int result[] = { maxTopic, teamCount };
        return result;
    }



// 2nd approach--using java BitSet class
    static int[] acmTeamUsingBitSet(String[] topic) {
        int teamCount = 0, maxTopic = 0;
        int size = topic.length;

        BitSet[] bitset = new BitSet[size];
        for (int i = 0; i < size; i++) {
            BigInteger b1 = new BigInteger(topic[i], 2);
            bitset[i] = BitSet.valueOf(b1.toByteArray());
        }
        for (int i = 0; i < size - 1; i++) {
            BitSet bitset1 = bitset[i];
            for (int j = i + 1; j < size; j++) {
                BitSet bitset2 = bitset[j];
                BitSet tmpset = new BitSet();
                tmpset.or(bitset1);
                tmpset.or(bitset2);
                if (tmpset.cardinality() > maxTopic) {
                    maxTopic = tmpset.cardinality();
                    teamCount = 1;
                } else if (maxTopic == tmpset.cardinality()) {
                    teamCount++;
                }
            }

        }
        int result[] = { maxTopic, teamCount };
        return result;

    }

您可以参考这个链接获得详细的视频解释。