Uva 1594 JAVA题解 (其实是算法优化

56 阅读 0 评论 37 点赞

我是靠谱客的博主愉快泥猴桃，最近开发中收集的这篇文章主要介绍Uva 1594 JAVA题解 (其实是算法优化，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

其实也就是

public class Uva1594 {
public static void main(String[] args) {
	Scanner in = new Scanner(System.in);
	int m = in.nextInt();
	while(m-->0) {	
		int n = in.nextInt();
		ArrayList<Integer> haves = new ArrayList<>();
		Set<ArrayList<Integer>>set = new HashSet<>();
		ArrayList<Integer> zero = new ArrayList<>();
		for(int i =0;i<n;i++)
		{
		haves.add(in.nextInt());
		zero.add(0);
		}
		int j = 0;
		while(j++<1002)
		{  
				if(haves.equals(zero)) 
				{	
					System.out.println("ZERO");
					break;
				}
				if(set.contains(haves))  /*保存的是地址*/
				{
					System.out.println("LOOP");
					break;
				}
				else
					set.add(haves);					 
				   int sum = 0;
			    	ArrayList<Integer> havess = new ArrayList<>();
					for(int i =0;i<haves.size();i++)
					{
					 sum =i==haves.size()-1?Math.abs(haves.get(i)-haves.get((0))):Math.abs(haves.get(i)-haves.get((i+1)));
					 havess.add(sum);
					} 		
					haves =havess;
	}
 }
}
}

看代码的直接往前看（此处是我的自我总结可忽略

其实看上去也没做多久但是后期有点心态崩了，还蹦出来几个编译错误，刚开始是我太急提交时忘记改成Main…然后中间几个有的时候是删代码是括号啥的没删除干净，但这样，我还是能算出正确的大难，我也不知道编译器干嘛去了，我晕

其实这个题思路很简单，我犯的错误就主要是时间问题

Time limit的原因

自我反思
刚开始因为输入中给出了每次的N元组的N值，所以我下意识的想使用Int[]数组，因为利用下标很方便。
还有一个原因，因为前几天看过书的原因，心里总觉得利用Arraylist.get(i)会慢（其实书上说的是，有一个前提就是和谁比较来着，结果我只记住了结论…没记住前提
这两个原因都反映了我的知识点还很匮乏…不过全面…
再加上我是晚上想着看看思路，准备明天再打的，发现这道题的确很简单，就直接做了，想着第二天再优化的…

结果利用set<int[]>以及contains来判断是否循环时，它判断的是地址值是否相等，而不是我需要的N元组对应值的判断，于是就反反复复的犯了一些错，于是我为了避免这个错误的出现又"锦上添花"，哪曾想到后面为这个行为付出的接近一个小时的修改…

我编写了判断是否为0的函数，还判断是否为循环的函数，样例和udebug的答案都对了,结果结果结果结果没有出人意料，我的代码超时了，然后试着进行了小修改，刚开始的时候我还能明确的知道，自己的代码有调用几个函数，所以不够快。
到后期，我已经不使用函数，而且我也不使用数组，循环也能很好的退出，程序自己也会结束…我认真的反复的看了我的代码是真的一句话也删不了我自认为最精简的，结果还是TL.
再最后我都要放弃的时候，想着要不出去晒晒太阳或者先睡一觉，我抱着试一试的心态，把使用ArrayList<Arraylist<> 改成了使SET<Arraylist<> 天啦噜成功了！！！！！！（撒花完结
刚开始其实我也是用的set，但是由于int[]的出现，我后期把它改掉了，然后嫌顺手，就直接用了Arraylist，我一个爆哭，我真是太蠢了！

我自己判断的原因可能是可能是HashSet查询的速度比Arraylist快把