复习笔记1

1 字符串比较

public static void main(String[] args) {
		String a = "123";
		String b = "1" + "2" + "3";
		System.out.println(a == b);// true
		String c = new String("123");
		System.out.println(a == c);// false
		String d = "1" + "2";
		d = d + "3";
		System.out.println(a == d);// false
String e = d.intern();
		System.out.println(a == e);//true
	}

这种题目笔试题中常见，加号被jvm重写为stringbuilder

string有一个池子，初始化时会先从池子里找是否有现成的，所以a和b是一样的
c是new出来的，必须不一样
d分两步，也就是new了两个stringbuilder在做这件事情（这里也就是为什么加号被重写了，也提倡用stringbuilder来处理字符串拼接的原因，另外stringbuffer线程安全），所以相当于县产生了一个“12”的string，在产生“123”，和a已经有区别了。
e需要了解intern方法，他相当于去直接调用之前提到的池子了。所以取到的一定是a。

2 Class

两种方式 class.forname()和a.class
前者会初始化（包括运行static块），后者没有这一步骤
接下来新建的方式都是newInstance()，会完成上面的步骤以及运行new a（）方法。


3 一道算法题，阿里巴巴一次笔试里出现过
给定一个正整数a和一个逆序排好的正整数数组b[]，给出所有由b中元素相加表示a的结果

public class PPP {
	int n = 6;

	@SuppressWarnings("unchecked")
	private void find(int t, int begin, int[] array, ArrayList<Integer> result) {
		if (t == 0) {
			System.out.println(result);
			return;
		}
		for (int i = begin; i < n; i++) {
			ArrayList<Integer> tempList = (ArrayList<Integer>) result.clone();
			int temp = array[i];
			if (temp > t) {
				continue;
			} else {
				tempList.add(temp);
				find(t - temp, i + 1, array, tempList);
				while (i < n - 1) {
					if (array[i + 1] == temp) {
						i++;
					} else {
						break;
					}
				}
			}
		}
	}

	public static void main(String[] args) {
		PPP p = new PPP();
		int[] temp = { 4, 3, 2, 2, 1, 1 };
		ArrayList<Integer> result = new ArrayList<Integer>();
		p.find(6, 0, temp, result);
	}
}

简化题目，先列数组只有六个元素，这个不影响算法
基本思路是剪枝，空间消耗比较大，因为在不断的clone队列。习惯问题，改成数组对于整体算法来说也没什么影响。

4 某年emc的一道算法题
2n+1个数，其中有n个成对出现，1个单独的，找出单独的那个

快排再边里，时间复杂度大概是快排的复杂度o（nlogn）
尝试不排序，开一个hashset
遍历原数组，没看到一个数，如果set里面有，就remove，如果没有，就add
最后将set中的数取出，就为单独的数
hashset查找的复杂度是o（1）
整个算法的时间复杂度应该是o（n）
空间复杂度o（n）