我正在编码一个问题（参考--http://www.codechef.com/FEB11/problems/THREECLR/）
以下是我的代码
import java.io.*;
import java.util.*;
public class Main {
static String ReadLn (int maxLg) // utility function to read from stdin
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";
try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}
if ((car < 0) && (lg == 0)) return (null); // eof
return (new String (lin, 0, lg));
}
public static boolean iscontains(HashMap<Integer,HashSet<Integer>> resultmap,HashSet<Integer> b, int index)
{
boolean result=false;
for(Iterator<Integer> iter = b.iterator();iter.hasNext();)
{ int tmp=Integer.valueOf(iter.next().toString());
if(resultmap.get(index).contains(tmp))
result=true;
}
return result;
}
public static void main(String[] args) throws InterruptedException, FileNotFoundException {
try {
HashMap<Integer,HashSet<Integer>> pairlist = new HashMap<Integer,HashSet<Integer>>();
String input=null;
StringTokenizer idata;
int tc=0;
input=Main.ReadLn(255);
tc=Integer.parseInt(input);
while(--tc>=0)
{
input=Main.ReadLn(255);
idata = new StringTokenizer (input);idata = new StringTokenizer (input);
int dishnum= Integer.parseInt(idata.nextToken());
int pairnum= Integer.parseInt(idata.nextToken());
while (--pairnum>=0)
{
input=Main.ReadLn(255);
idata = new StringTokenizer (input);idata = new StringTokenizer (input);
int dish1=Integer.parseInt(idata.nextToken());
int dish2=Integer.parseInt(idata.nextToken());
if(pairlist.containsKey((Integer)dish1))
{
HashSet<Integer> dishes=new HashSet<Integer>();
dishes=pairlist.get(dish1);
dishes.add(dish2);
pairlist.put(dish1, dishes);
}
else
{
HashSet<Integer> dishes=new HashSet<Integer>();
dishes.add(dish2);
pairlist.put(dish1, dishes);
}
}
int maxrounds=1;
HashMap<Integer,HashSet<Integer>> resultlist = new HashMap<Integer,HashSet<Integer>>();
HashSet<Integer> addresult=new HashSet<Integer>();
addresult.add(1);
resultlist.put(1,addresult);
System.out.print("1");
for(int i=2;i<=dishnum;i++)
{
boolean found_one=false;
boolean second_check=false;
int minroundnum=maxrounds;
boolean pairlistcontains=false;
pairlistcontains=pairlist.containsKey(i);
for(int j=maxrounds;j>=1;j--)
{
if(!found_one){
if(pairlistcontains)
{
if(!iscontains(resultlist,pairlist.get((Integer) i),j))
{
for(Iterator<Integer> resultiter = resultlist.get(j).iterator();resultiter.hasNext();)
{
if(pairlist.get(resultiter.next()).contains(i))
second_check=true;
}
if(second_check==false)
{
found_one=true;
minroundnum=j;
j=0;
//second_check=false;
}
}
}
else
{
for(Iterator<Integer> resultiter = resultlist.get(j).iterator();resultiter.hasNext();)
{
if(pairlist.get(resultiter.next()).contains(i))
second_check=true;
}
if(second_check==false)
{
found_one=true;
minroundnum=j;
j=0;
//second_check=false;
}
}
second_check=false;
}
}
if((minroundnum==maxrounds)&&(found_one==false))
{
++minroundnum;
++maxrounds;
}
else
{
found_one=false;
}
HashSet<Integer> add2list=new HashSet<Integer> ();
if(resultlist.containsKey(minroundnum))
{
add2list=resultlist.get(minroundnum);
add2list.add(i);
}
else
{
add2list.add(i);
}
resultlist.put(minroundnum,add2list);
System.out.print(" ");
System.out.print(minroundnum);
}
if((tc !=-1))
System.out.println();
}
}
catch(Exception e){System.out.println(e.toString());}
}}
我已经在 Ideone 等在线评委上检查了这段代码，并得到了预期的结果。但是当我提交此代码时，我收到超出时间限制的错误。我已经在 Ideone 上使用足够大的输入集测试了这段代码，执行时间不到 1 秒。它似乎有一个错误或内存泄漏，似乎耗尽了我生活中所有的快乐。 任何指示/提示将不胜感激。
谢谢
编辑1--
感谢大家的回复，我使用以下 python 脚本生成的输入运行了代码 --
import random
filename="input.txt"
file=open(filename,'w')
file.write("50")
file.write("\n")
for i in range(0,50):
file.write("500 10000")
file.write("\n")
for j in range(0,10000):
file.write(str(random.randrange(1,501))+" "+str(random.randrange(1,501)))
file.write("\n")
file.close()
我的代码在上述脚本提供的输入上执行花费了高达 71052 毫秒的时间。我现在必须将执行时间至少降低到 8000 毫秒。 我正在尝试按照 rfeak 的建议替换 HashMap 和 HashSet，并且我也想知道记忆化在这种情况下是否会有帮助。请指教。
编辑2-- 使用数组重新编码我的算法似乎有效。只是，在不同时间重新提交相同的代码给了我接受的解决方案和超出了时间限制：D 我想到了另一种使用哈希图进一步优化的方法。 非常感谢大家的帮助！
您的程序在本地运行时使用了多少内存？
如果他们在没有足够内存的情况下运行您的 Java 程序，您可能会花费大量时间尝试进行垃圾收集。这可能会毁掉你的一秒钟。
如果你需要节省时间和内存（待定...），我有2个建议。
将
HashSet<Integer>BitSet将
Map<Integer,X>X[]翻转位 给定两个数字 A 和 B。编写一个程序来计算要翻转的位数，以将数字 A 更改为数字 B。翻转数字的一位意味着将一位从 1 更改为 0，反之亦然。
输入格式
第一行输入包含T——测试用例的数量。接下来的 T 行每行包含 2 个整数 A 和 B，用空格分隔。
输出格式
对于每个测试用例，打印将 A 转换为 B 所需的位翻转数，并用新行分隔。
限制
1 <= T <= 100000
0<= A, B <= 109
示例
输入
4
20 10
16 8
1 153
549 24
输出
4
2
3
6