Lexi's Leetcode solutions

本来以为是弱智题，但是要求不能duplicate之后，发现代码还真不好写了。难怪通过率只有16%这么低。

• 如何处理“和上一个一样就不要做了”这种duplicate情况？（形成自己的代码习惯）
  • if (i > 0 或类似condition && num[i] == num[i – 1]) continue;
  • 这样可以保证永远笼罩在while (some condition)的保证之下，用continue就不会出现越界等情况。
  • 如果是递归，外层没有while，则用while (boundary &&  num[i] == num[i – 1[) {i++;}

public ArrayList<ArrayList> threeSum(int[] num) {
    ArrayList<ArrayList> result = new ArrayList<ArrayList>();
    Arrays.sort(num);
    for (int i = 0; i < num.length; i++) { 			
        if (i > 0 && num[i] == num[i - 1])
            continue;
	int x = 0 - num[i];
	int p = i + 1, q = num.length - 1;
	while (p < q) {
            if (p > i + 1 && num[p] == num[p - 1]) {
                p++;
                continue;
            }
            if (q < num.length - 1 && num[q] == num[q + 1]) {
                q--;
                continue;
            }
	    if (num[p] + num[q] == x) {
                ArrayList triple = new ArrayList();
		triple.add(num[i]);
		triple.add(num[p]);
		triple.add(num[q]);
		result.add(triple);
	    } else if (num[p] + num[q] < x) {
		p++;
	    } else {
	        q--;
	    }
	}
    }
    return result;
}

这题不好想，还是看了答案才明白。中心思路是：每个bar头顶能接多少水，取决于它两边有木有比自己高的两个木板，有的话自己上方就被trap住了，trap的volumn是（两边比自己高的那两个模板中的短板-自己的高度）×1。
然后就要考虑怎么求在每个木板i，他的左边最高板和右边最高板的值呢？用dp一试就出来了。这个就是因为很熟练LIS了，所以一下就做出来了。这种接水题也是，现在觉得难，多做几道思路就清晰了吧。

public int trap(int[] A) {
    int[] left = new int[A.length];
    int[] right = new int[A.length];
    for (int i = 0; i < A.length; i++) {
        left[i] = i > 0 ? Math.max(left[i - 1], A[i]) : A[i];
    }
    for (int i = A.length - 1; i >= 0; i--) {
        right[i] = i < A.length - 1 ? Math.max(right[i + 1], A[i]) : A[i];
    }
    int res = 0;
    for (int i = 1; i < A.length - 1; i++) { //two edges can't trap nothin'
        int lowBar = Math.min(left[i - 1], right[i + 1]);
        if (lowBar > A[i])
            res += lowBar - A[i];
    }
    return res;
}