Lexi's Leetcode solutions

这个题要用反证法来理解。算法：

1. 从i开始，j是当前station的指针，sum += gas[j] – cost[j] （从j站加了油，再算上从i开始走到j剩的油，走到j+1站还能剩下多少油）
2. 如果sum < 0，说明从i开始是不行的。那能不能从i..j中间的某个位置开始呢？假设能从k (i <=k<=j)走，那么i..j < 0，若k..j >=0，说明i..k – 1更是<0，那从k处就早该断开了，根本轮不到j。
3. 所以一旦sum<0，i就赋成j + 1，sum归零。
4. 最后total表示能不能走一圈。
5. 这个题算法简单，写起来真是够呛。对数组一快一慢双指针的理解还是不行。注意千万不能出现while (i < 0) { i++, A[i]}这种先++然后取值的情况，必须越界。

public int canCompleteCircuit(int[] gas, int[] cost) {
    int i = 0, j = 0;
    int sum = 0;
    int total = 0;
    while (j < gas.length) {
        int diff = gas[j] - cost[j];
        if (sum + diff < 0) {
            i = j + 1;
            sum = 0;
        } else {
            sum += diff;
        }
        j++;
        total += diff;
    }
    return total >= 0 ? i : -1;
}

本来以为是弱智题，但是要求不能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;
}

这题八月轻松过，现在十月看看就彻底不会了。感觉跟array有关的自己想算法的题就能把我吓个好歹。多做多总结！

Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2,1].（length之后的都不管了）。

算法：

1. i从1开始，遇见和上一个不一样的，就放在j指的位置里，j++
2. 要是arr[i] == arr[i – 1]，i继续往后走

public int removeDuplicates(int[] A) {
  if (A.length == 0)
    return 0;
  int j = 1;
  for (int i = 1; i < A.length; i++) {
    if (A[i] != A[i - 1]) {
      A[j] = A[i];
      j++;
    }
  }
  return j;
}