Some About Cycle

发表于   |  

判断环

#141 Linked List Cycle

Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?

设两个指向头部的变量one & two，one每次前进一个节点，two另一个每次前进两个。

  • 如果链表中存在环，则最后两个变量都会指向同一个节点。
    • 设两变量都已在环中，两者相距x步。当one继续走x步时，two走了2x步，这时两者重合。
  • 若果链表中没有环，则最后two的指针会走向链尾null。
1
2
3
4
5
6
7
8
9
10
11
12
public boolean hasCycle(ListNode head) {
       if (head == null)
           return false;
       ListNode one = head, two = head;
       while (two.next != null && two.next.next != null) {
           one = one.next;
           two = two.next.next;
           if (one == two)
               return true;
       }
       return false;
   }

找出环的起点

#142 Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
Follow up:
Can you solve it without using extra space?


设链表头部节点与环起始节点的距离为d，环的长度为r。
当one变量走了k步时，两变量重合(two走了2k步，two领先one n 圈)，设此时与环起始节点的距离为s。

  • 2k - k = nr -> k = nr
  • k = d + s + mr -> nr = d + s + mr -> d + s = (n - m)r
    从该式可以看出，从s点处再走d步，就能走完整个环，回到环的起点。
    s点与链表头到环起始节点的距离都是d步。
    这时让两个变量分别从s点和链表头走，每次走一步，到两者重合的时候，该点就是环的起始节点了。
    注意要先判断链表中是否有环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public ListNode detectCycle(ListNode head) {
       if (head == null)
           return null;
       ListNode one = head, two = head;
       while (two.next != null && two.next.next != null) {
           one = one.next;
           two = two.next.next;
           if (one == two)
               break;
       }
       if (two.next == null || two.next.next == null) return null;
       
       one = head;
       while (one != two) {
           one = one.next;
           two = two.next;
       }
       return one;
   }

找出重复的数字

#287 Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Note:
You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.

这题的标签有two point和binary search两个，对于这种完全乱序的序列，想不到该怎么应用二分法(事实证明是思考角度完全错了)。

two point

这题的思路是上一题的延伸，可以将数组index与value的对应关系转化为链表(感觉好腻害)。

0 1 2 3 4 5
2 5 5 1 4 3
转换成更直观的形式
↓
1 2 3 4 5 6
2 5 5 1 4 3

可以看出，重复的数会有至少两个节点指向它，这将形成环(也可能是自己指向自己，这也是环)。然后这就变成了上面的找环的起始节点的问题了。
因为数组中的数一定是小于等于n的，所以可以确定没有任何数会指向n，因此可以拿它做头部节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int findDuplicate(int[] nums) {
       int len = nums.length;
       int one = len, two = len;
       do {
           one = nums[one-1];
           two = nums[nums[two-1]-1];
       } while (one != two);
       one = len;
       while (one != two) {
           one = nums[one-1];
           two = nums[two-1];
       }
       return one;
   }

上面这个做法和二分法并没有半毛钱关系，直到我在讨论区看到了这个 → Two Solutions (with explanation): O(nlog(n)) and O(n) time , O(1) space, without changing the input array
一开始在[1,n]区间中找，得到mid。然后数出数组中所有小于等于mid的数的个数count，若count>mid，说明重复数存在于前半区域中，则下一个搜索区间为[1,mid]，否则为[mid,n]。(耗时)

1
2
3
4
5
6
7
8
9
10
11
12
13
public int findDuplicate(int[] nums) {
       int left = 1, right = nums.length-1;
       while (left < right) {
           int mid = left + (right - left) / 2;
           int count = 0;
           for (int i = 0; i < nums.length; i++)
               if (nums[i] <= mid)
                   count++;
           if (count > mid) right = mid;
           else left = mid + 1;
       }
       return left;
   }

Nice Day ~