LeetCode -- 88 and 160

本篇博客讲解LeetCode 88 和 160。

LeetCode 88

Description

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

  • The number of elements initialized in nums1 and nums2 are m and n respectively.
  • You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

1
2
3
4
5
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

Output: [1,2,2,3,5,6]

Solution

问题的关键在于$O(N)$的时间和$O(1)$的空间,也就是说必须在原地操作

用$(i,j,k)$分别表示$arr_1,arr_2$和$arr_3$中的位置,因为是原地操作,所以$arr_3 = arr_1$。

正常的从前向后的合并,$i\leftarrow 1, j\leftarrow 1, k \leftarrow m+1​$,不能保证$i < k​$。

不妨转换一下思路,从后向前合并。

$i\leftarrow m, j\leftarrow n, k\leftarrow m+n$,这样能保证$i < k$。

Python Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
i, j, k = m - 1, n - 1, n + m - 1
while i >= 0 and j >= 0:
if nums1[i] >= nums2[j]:
nums1[k] = nums1[i]
i -= 1
k -= 1
else:
nums1[k] = nums2[j]
j -= 1
k -= 1
while i >= 0:
nums1[k] = nums1[i]
k -= 1
i -= 1
while j >= 0:
nums1[k] = nums2[j]
k -= 1
j -= 1

LeetCode 160

Description

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

img

begin to intersect at node c1.

Example 1:

img

1
2
3
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Example 2:

img

1
2
3
Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [0,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:

img

1
2
3
4
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

Notes:

  • If the two linked lists have no intersection at all, return null.
  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Your code should preferably run in $O(n)$ time and use only $O(1)$ memory.

Solution 1: $O(MN)$

在A上暴力枚举C,将$C\rightarrow C.next$断开,判断B是否能到达尾部。

Solution 2: $O(N\log M)$

Solution 1的改进,显然$judge$函数是单调的,可以二分答案,二分查找C到$Head_A$的距离。

Solution 3: $O(1)$

基于尝试判断的方法显然是不行的,效率太低。

这里有一个奇思妙想:设三段的长度分别为$a, b, c$,那么显然有

$$a + c + b = b + c + a $$

$$||A \rightarrow C || + ||C\rightarrow D|| + ||B\rightarrow C|| = ||B \rightarrow C || + ||C\rightarrow D|| + ||A\rightarrow C||$$

所以设置两个指针$p, q​$,

  • 同时分别从A, B出发,前进速度一样,每次前进一格。
  • 当$p$到达D,$p$下一步转移到B。
  • 当$q$到达D,$q$下一步转移到A。

那么显然,$p, q$第一次相遇的位置就是C。

C++ Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
bool bo1 = false, bo2 = false;
auto p = headA, q = headB;
for (; p && q && p != q; ) {
if (p->next == NULL) {
p = headB;
if (!bo1)
bo1 = true;
else
break;
}
else
p = p->next;

if (q->next == NULL) {
q = headA;
bo2 = true;
}
else
q = q->next;
}
if (p == q)
return p;
else
return NULL;
}
};
------ 本文结束------
0%