我面临HackerRank解决方案超时

Question

我正在解决黑客排名的问题 黑客排名ICPC团队问题

我创建了以下代码作为问题的解决方案。

import java.math.BigInteger;
import java.util.Scanner;
public class ACMICPCTeam {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),m=sc.nextInt(),count=0,maxCount=0,teams=0;
sc.nextLine();
String subjectArray[]=new String[n];
for(int i=0;i<n;i++){
subjectArray[i]=sc.nextLine();
}
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
String temp=""+(new BigInteger(subjectArray[i]).add(new BigInteger(subjectArray[j])));
//System.out.println(temp);
count=temp.replace("0","").length();
if(count>maxCount)
{
maxCount=count;
teams=1;
}
else if(count==maxCount)
{
teams++;
}
}
}
System.out.println(maxCount);
System.out.println(teams);
sc.close();
}
}

所以我要做的是添加两个团队的主题，并计算结果字符串的非零。最高计数是科目数，最高计数是知道最大科目数的团队。即使花了很多时间，我也无法找到比这更好的解决方案，我仍然面临超时，因为它效率不高。

我已经通过问题的论坛，但没有帮助。

Answer 1

不要为此使用字符串逻辑。

在进入循环之前，即在读取它们时，将字符串解析为BitSet。

然后使用方法or(BitSet set)和cardinality()。

我刚刚完成了挑战。无超时。

Answer 2

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

您可以利用 BigInteger 方法或 BitSet 类来简化它。

要组建团队，您必须使用按位 OR

以下是解决方案——

// 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;
}

您可以参考此链接以获取详细的视频说明。

Answer 3

我在Java 8上得到了很好的结果。

static int[] acmTeam(String[] topic) {
List<List<Integer>> res = IntStream.range(0, topic.length)
.mapToObj(s -> IntStream.range(0, topic[s].length()).boxed()
.collect(Collectors.groupingBy(i -> topic[s].charAt(i))))
.map(m -> m.get('1'))
.collect(toList());

long maxTopic = 0;
int teamCount = 0;

for (int i = 0; i < res.size(); i++) {
for (int j = i + 1; j < res.size(); j++) {
long topics = Stream.concat(res.get(i).stream(), res.get(j).stream()).distinct().count();
if (topics >  maxTopic) {
maxTopic = topics;
teamCount = 1;
} else if (topics == maxTopic) {
teamCount++;
}
}
}
return new int[]{(int) maxTopic, teamCount};
}