Lexi's Leetcode solutions

Posts Tagged ‘list

思路:

  1. 因为没有random access,所以用in order的方式,一个一个遍历element,然后assign给parent
  2. 平时正常array convert bst都是用pre order的方式,root算好,然后left=.., right =…
  3. 一般你做树的bottom up是post order,left做出来,right做出来,root取决于这两个值
  4. 这里为什么要in order呢? 左,中,右的方式,正好是sorted。所以每次做完子树,然后下一个节点就是下一个位置。但是什么时候是个头呢,因为h.next会一直存在的,但是你的子树怎么知道什么时候返回到上一层?所以就要用p, q两个指针了,p代表当前sub list的头,q是尾。但是不要真的用他们来random access,就是用来stop就行了。
public TreeNode sortedListToBST(ListNode head) {
    int len = 0;
    ListNode dummy = head;
    while (dummy != null) {
       len++;
    dummy = dummy.next;
    }
    ListNode[] curr = new ListNode[1];
    curr[0] = head;
    return convert(curr, 0, len - 1);
}
private TreeNode convert(ListNode[] curr, int p, int q) {
    if (p > q)
        return null;
    int mid = (p + q) / 2;
    TreeNode left = convert(curr, p, mid - 1);
    TreeNode root = new TreeNode(curr[0].val);
    curr[0] = curr[0].next;
    TreeNode right = convert(curr, mid + 1, q);
    root.left = left;
    root.right = right;
    return root;
}
Advertisements
Tags: , , ,

a->b->c->d->e => a->e->b->d->c,要求inplace,不能用额外空间(要不然直接reverse成另一个就好办了),不能直接改动list的值。

这题有点写长了,过一阵看看网上有没有好点的做法。O(n)。

算法:

  1. 过一遍算出总长度len
  2. 再过一遍找到中点或第二部分的第一个点(a->b->c->d->e和a->b->c->d的都是c)
  3. reverse后半部分,变成a->b->c<-d<-e 或者 a->b->c<-d,最后中点c的next置空
  4. 两头穿插合并,直到找到c这点。c肯定是一起找到(奇数)或者右半部分先找到(偶数)
public void reorderList(ListNode head) {
    if (head == null)
        return;
    ListNode p = head;
    int len = 0;
    while (p != null) {
        len++;
        p = p.next;
    }
    p = head;
    for (int k = 0; k < len / 2; k++) {
        p = p.next;
    } //p points to mid point
    ListNode curr = p.next, next;
    p.next = null;
    while (curr != null) { //开始reverse后半部分
        next = curr.next;
        curr.next = p;
        p = curr;
        curr = next;
    }//now p points to the last ele
    ListNode h = head;
    while (h.next != p && h != p) {
        ListNode tempH = h.next;
        ListNode tempP = p.next;
        h.next = p;
        p.next = tempH;
        h = tempH;
        p = tempP;
    }
}
Tags:

几道典型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;
    }

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

  • 比如反转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:

看别人思路:这个既然要rotate,不如先连起来loop,这样怎么也不怕null pointer exception了。然后再找到该断开的地方断开。

public ListNode rotateRight(ListNode head, int n) {

    if (head == null || n == 0)
        return head;
    ListNode p = head;
    int len = 1;//since p is already point to head
    while (p.next != null) {
        len++;
        p = p.next;
    }
    p.next = head; //form a loop
    n = n % len;
    for (int i = 0; i < len - n; i++) { //len-n一画就出来了
        p = p.next;
    } //now p points to the prev of the new head
    head = p.next;
    p.next = null;
    return head;
}
Tags:

keep 3个pointer:

  • prevStart:要reverse的section的前一个节点
  • start:section第一个
  • end:section最后一个

然后就每次reverse好了section,和prevStart连上就行了,然后prevStart 越过k个,接着做。这是个练习linked list的好题。

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode prevStart = dummy;
    while (prevStart != null) {
        ListNode start = prevStart.next;
        ListNode end = prevStart;
        for (int i = 0; i < k; i++) {
            end = end.next;
            if (end == null)
                return dummy.next;
        }
        prevStart.next = reverse(start, end);
        for (int i = 0; i < k; i++) {
            prevStart = prevStart.next;
        }
    }
    return dummy.next;
}
private ListNode reverse(ListNode start, ListNode end) {
    ListNode prev = start;
    ListNode curr = start.next;// want to make curr point to prev
    ListNode afterEnd = end.next;
    while (curr != afterEnd) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    start.next = afterEnd;
    return end;
}

 

Tags:
  • generic list题的test cases
    1. normal case
    2. 1个ele
    3. 整个是个loop
    4. partial loop
  • 有可能删了元素的题:
    1. 小心head是不是被删了,要不要换新的
    2. prev指针一定要有,直接用一个指针指前一个,但是想删/动下一个,相比写p, p.next != null什么的,最好再keep一个prev指针,不容易乱套。即使多了一个var,总比写不对强!!
    3. 一般是Node head, Node prev, Node i, Node j四个指针。一定要写代码之前弄明白i, j都是什么物理意义!

Tags: