Lexi's Leetcode solutions

Archive for October 11th, 2013

原来反转单链表有另一种简洁的做法,看来每道题过了之后一定还得看别人答案才行,这才能做到“做的多了就会了”。

  • 比如反转b->c->d:a->b->c->d->e => a->d->c->b->e
  • 三个variable
    1. prevM:指向反转部分的前一个元素a
    2. prev:指向已经反转成功的最后一个元素,永远是prevM.next,不需要改动。
    3. curr:想往prevM后面塞的那个元素。
  • 算法:每次拿出右边的新元素,往prevM后面插,最后curr==不需要反转的section的第一个节点时退出
public ListNode reverseBetween(ListNode head, int m, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode prevM = dummy, prev, curr;
    for (int i = 1; i <= n; i++) {
        if (i < m) {
            prevM = prevM.next;
        } else if (i == m) {
            prev = prevM.next;
            curr = prev.next;
        }else {
            prev.next = curr.next;
            curr.next = prevM.next;
            prevM.next = curr;
            curr = prev.next;
        }
    }
    return dummy.next;
}
Tags:

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