82. Remove Duplicates from Sorted List II

二刷 06/2022

Version #1 Not Optimal 

站在一个点上同时向前看和向后看，如果都没有相等的value证明不是一个duplicate点，就接到答案上

看了之前的答案感觉这个写法不是最优的

Time O(N)

Space O(1)

Runtime: 1 ms, faster than 79.44% of Java online submissions for Remove Duplicates from Sorted List II.

Memory Usage: 43.8 MB, less than 38.44% of Java online submissions for Remove Duplicates from Sorted List II.

class Solution {

    public ListNode deleteDuplicates(ListNode head) {

        ListNode dummy = new ListNode(0);

        ListNode curr = dummy;

        ListNode prev = null;

        while (head != null) {

            if ((prev == null || prev.val != head.val) && (head.next == null || head.next.val != head.val)) {

                curr.next = head;

                curr = curr.next;

            }

            prev = head;

            head = head.next;

            curr.next = null;

        }

        return dummy.next;

    }

}

Version #2 Better

Time O(N)

Space O(1)

Runtime: 1 ms, faster than 79.44% of Java online submissions for Remove Duplicates from Sorted List II.

Memory Usage: 43.1 MB, less than 76.10% of Java online submissions for Remove Duplicates from Sorted List II.

class Solution {

    public ListNode deleteDuplicates(ListNode head) {

        ListNode dummy = new ListNode(0);

        dummy.next = head;

        ListNode slow = dummy;

        ListNode fast = head;

        while (fast != null) {

            while (fast.next != null && fast.val == fast.next.val) {

                fast = fast.next; // reach the last duplicate node

            }

            // The fast has skipped duplicates

            if (slow.next != fast) {

                slow.next = fast.next;

            } else {

                slow = slow.next;

            }

            fast = fast.next;

        }

        return dummy.next;

    }

}

一刷

有重复的就向后跳
如果跳了证明有重复 就prev.next = curr.next 此时prev不变
如果没跳prev向后移动一位
76.20 %

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode curr = head;
        //    p        c
        // 1->2->3->3->4->4->5
        while (curr != null) {
            while (curr.next != null && curr.next.val == curr.val) {
                curr = curr.next;
            }
            if (curr != prev.next) {
                prev.next = curr.next;
            } else {
                prev = prev.next;
            }
            curr = curr.next;
        }
        return dummy.next;
    }
}

80. Remove Duplicates from Sorted Array II

Two Pointers

Better Solution
2.05 %
class Solution {
    public int removeDuplicates(int[] nums) {
        int p = 0;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i == 0 || nums[i] != nums[i - 1]) {
                count = 0;
            } else {
                count++;
            }
            if (count < 2) {
                nums[p] = nums[i];
                p++;
            }
        }
        return p;
    }
}

2.05 %
class Solution {
    public int removeDuplicates(int[] nums) {
        int p = 0;
        int i = 0;
        int start = 0;
        while (i < nums.length) {
            start = i;
            while (i < nums.length && nums[i] == nums[start]) {
                if (i - start < 2) {
                    nums[p] = nums[i];
                    p++;
                }
                i++;
            }
        }
        return p;
    }
}

885. Spiral Matrix III

找到规律发现走的是 1, 1, 2, 2, 3, 3, 4, 4
所以用Step表示每一次转向，走的实际步数是step / 2
把list变成array

return res.toArray(new int[R * C][2]);

 45.43 %
class Solution {
    public int[][] spiralMatrixIII(int R, int C, int r0, int c0) {
        List<int[]> result = new ArrayList<>();
        int[] curr = new int[]{r0, c0};
        result.add(new int[]{r0, c0});
        int step = 0;
     
        while (result.size() < R * C) {
            for (int i = 0; i <= step / 2; i++) {
                curr[0] = curr[0] + dirs[step % 4][0];
                curr[1] = curr[1] + dirs[step % 4][1];
                if (isValid(curr, R, C)) {
                    result.add(new int[]{curr[0], curr[1]});
                }
            }
            step++;
        }
        int[][] array = new int[result.size()][];
        return result.toArray(array);
    }
    private int[][] dirs = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
 
    private boolean isValid(int[] pos, int R, int C) {
        return pos[0] >= 0 && pos[0] < R && pos[1] >= 0 && pos[1] < C;
    }
 
}

142. Linked List Cycle II

二刷 08/2022

Version #1 Floyd's Tortoise and Hare

------a-------x-----b-------

                   |                   |

                   -------c-------

搜287看证明

Time O(N)

Space O(1)

Runtime: 1 ms, faster than 58.84% of Java online submissions for Linked List Cycle II.

Memory Usage: 45 MB, less than 63.18% of Java online submissions for Linked List Cycle II.

public class Solution {

    public ListNode detectCycle(ListNode head) {

        ListNode slow = head, fast = head;

        while (fast != null && fast.next != null) {

            slow = slow.next;

            fast = fast.next.next;

            if (slow == fast) {

                break;

            }

        }

        if (fast == null || fast.next == null) {

            return null;

        }

        slow = head;

        while (slow != fast) {

            slow = slow.next;

            fast = fast.next;

        }

        return slow;

    }

}

一刷
Proof

I have seen the accepted answer as proof elsewhere too. However, while its easy to grok, it is incorrect. What it proves is

x=z$x=z$ (which is obviously wrong, and the diagram just makes it seem plausible due to the way it is sketched).

What you really want to prove is (using the same variables as described in the diagram in the accepted answer above):

z=x mod (y+z)$z=xmod(y+z)$

(y+z)$(y+z)$ is the loop length, L$L$

so, what we want to prove is:

z=x mod L$z=xmodL$

Or that z is congruent to x (modulo L)

Following proof makes more sense to me:

Meeting point, M=x+y$M=x+y$

2(x+y)=M+kL$2(x+y)=M+kL$, where k$k$ is some constant. Basically, distance travelled by the fast pointer is x+y$x+y$ plus some multiple of loop length, L$L$

x+y=kL$x+y=kL$

x=kL−y$x=kL-y$

The above equation proves that x$x$ is the same as some multiple of loop length, L$L$ minus y$y$. So, if the fast pointer starts at the meeting point, M$M$ or at x+y$x+y$, then it will end up at the start of the loop.

x = kL - y = (k+1)L + (L-y) = (k+1)L + z
-> x % L = z

53.34 %
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                break;
            }
        }
        if (fast == null || fast.next == null) {
            return null;
        }
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}