Lexi's Leetcode solutions

Posts Tagged ‘一快一慢双指针

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

  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;
}

 

Advertisements

几道典型two pointers一快一慢题。记住j要匀速的走,i指向最终想要的数组的最后一个元素(或者倒数第二个,或者第一个可以被change的。。因题而异)。做的挺焦躁的,记下来对比练习:

1. Remove Elements:一个数组,删掉所有出现的x,返回新长度。

  • 两个pointer,一个正常走,一个指向真正去掉x的数组的长度。
  • public int removeElement(int[] A, int elem) {
        int i = 0;
        for (int j = 0; j < A.length; j++) {
            if (A[j] != elem) { //should be used 
                A[i] = A[j];
                i++;
            }
        }
        return i;
    }

2. 一个排好序的数组,删掉所有重复,让新数组每个数字只出现一次,返回新数组长度。不许用额外空间。

  • i指向最后一个保证valid的元素
  • j指向当前exam的元素,所以从1开始;当A[j] == A[i]的时候,说明A[j]是个invalid的,所以接着走
  • 可以看出来j肯定走的比i快,所以不用担心i的出界问题
  • public int removeDuplicates(int[] A) {
        if (A.length == 0)
            return 0;
        int i = 0; //right most valid element
        for (int j = 1; j < A.length; j++) {
            if (A[j] != A[i]) { //when not equals to right most valid, means this is also valid, extend the valid array
                i++;
                A[i] = A[j];
            }
        }
        return i + 1; 
    }

3.每个数字最多出现两次,比如1, 1, 1, 2, 2, 3 => 1, 1, 2, 2, 3

  • 同样,是当前exam的元素和valid array的最后一个(其实这里是倒数第二个)元素比较,而不是A[j]和A[j – 1]比较。后者就要混乱很多。
  • public int removeDuplicates(int[] A) {
        if (A.length < 2)
            return A.length;
        int i = 1;
        for (int j = 2; j < A.length; j++) {
            if (A[j] == A[i - 1]) {
                continue;
            } else {
                i++;
                A[i] = A[j];
            }
         }
         return i + 1;
    }

4. 单链表,删除所有出现过两次或以上的元素,比如1->1->2->2->2 => null

  • 同样,i指向最后一个valid元素,j是当前exam的
  • 但是当A[i] == A[j]的时候,i要缩短,所以要keep一个prev pointer
  • j一定要每次都往后走,保证匀速,千万别i动了j却没动。就挂在这了。
  • public ListNode deleteDuplicates(ListNode head) {
        if (head == null)
            return null;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy, i = head, j = head.next;
        while (j != null) {
            if (i.val == j.val) {
                while (j != null && i.val == j.val) {
                    i.next = j.next; //remove j
                    j = j.next;
                }
                prev.next = i.next; //remove i
                i = prev.next;
                j = i == null ? null : i.next;
            } else {
                j = j.next;
                i = i.next;
                prev = prev.next;
            }
        }
        return dummy.next;
    }

这题完全没印象,后来发现是之前做用了string.indexOf这个函数cheat成功了。这也是two pointers一快一慢的练习题,挺难做的,需要重做。

  • i:当前unique substring的头
  • j:当前unique substring的尾
  • 注意最后可能忘记算最后一段的长度了(因为dup那个条件已经不存在)
public int lengthOfLongestSubstring(String s) {
    int i = 0, len = 0, n = s.length();
    char A[] = s.toCharArray();
    Set<Character> set = new HashSet<Character>();
    for (int j = 0; j < n; j++) {
        if (set.contains(A[j])) { //found dup
            len = Math.max(len, j - i);
            while (i < n && A[i] != A[j]) {
                set.remove(A[i]);
                i++;
            }
            i++;
        } else {
            set.add(A[j]);
        }
    }
    return Math.max(len, n - i);
}

这题八月轻松过,现在十月看看就彻底不会了。感觉跟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;
}