HackerEarth练习时间耗尽
HackerEarth练习时间耗尽
提问于 2018-08-27 01:47:47
我从HackerEarth解决了following问题。所有的测试用例都是正确的，除了最后一个测试用例，因为它已经超时了。我试着优化我的解决方案，但我不能更好地优化它。以下是我的解决方案：
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
class TestClass {
public static void main(String args[]) throws Exception {
Scanner sc = new Scanner(System.in);
Set<Integer> perfectNumbers = new HashSet<>();
for (int i = 0; i <= 20; i++) {
perfectNumbers.add(i * i * i);
}
for (int i = 1; i <= 44; i++) {
perfectNumbers.add(i * i);
}
int t = sc.nextInt();
for (int k = 0; k < t; k++) {
int db = 0;
int n = sc.nextInt();
int[] a = new int[1001];
int[] b = new int[1001];
int[] numbers = new int[n];
for (int j = 0; j < n; j++) {
int x = sc.nextInt();
numbers[j] = x;
for (Integer perfect : perfectNumbers) {
if (x == perfect - x) {
b[x]++;
} else if (perfect - x >= 0 && perfect - x <= 1000)
a[perfect - x]++;
}
}
for (int j = 0; j < n; j++) {
db += a[numbers[j]];
}
for (int j = 0; j <= 1000; j++) {
if (b[j] > 1) {
db += b[j] * (b[j] - 1);
}
}
System.out.println(db / 2);
}
}
}回答 1
Stack Overflow用户
回答已采纳
发布于 2018-08-27 01:55:45
也许你应该考虑用更快的方法读取输入，因为Scanner真的很慢。例如，您可以将Scanner包装到BufferedReader中。
我修改了代码。现在它通过了所有测试用例：
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
class TestClass {
public static void main(String args[]) throws Exception {
FastReader sc = new FastReader();
Set<Integer> perfectNumbers = new HashSet<>();
for (int i = 0; i <= 20; i++) {
perfectNumbers.add(i * i * i);
}
for (int i = 1; i <= 44; i++) {
perfectNumbers.add(i * i);
}
int t = sc.nextInt();
for (int k = 0; k < t; k++) {
int db = 0;
int n = sc.nextInt();
int[] a = new int[1001];
int[] b = new int[1001];
int[] numbers = new int[n];
for (int j = 0; j < n; j++) {
int x = sc.nextInt();
numbers[j] = x;
for (Integer perfect : perfectNumbers) {
if (x == perfect - x) {
b[x]++;
} else if (perfect - x >= 0 && perfect - x <= 1000)
a[perfect - x]++;
}
}
for (int j = 0; j < n; j++) {
db += a[numbers[j]];
}
for (int j = 0; j <= 1000; j++) {
if (b[j] > 1) {
db += b[j] * (b[j] - 1);
}
}
System.out.println(db / 2);
}
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new
InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
Integer nr=null;
try {
nr = Integer.parseInt(next());
} catch (Exception e) {
//something went wrong
}
return nr;
}
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/52028826
复制相关文章
相似问题