【LeetCode Solutions】LeetCode 160 ~ 165 题解

LeetCode 160. 相交链表（简单）

【题目描述】

给你两个单链表的头节点 headA 和 headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null。

图示两个链表在节点 c1 开始相交：

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须保持其原始结构。

自定义评测：

评测系统的输入如下（你设计的程序不适用此输入）：

• intersectVal：相交的起始节点的值。如果不存在相交节点，这一值为 0。
• listA：第一个链表。
• listB：第二个链表。
• skipA：在 listA 中（从头节点开始）跳到交叉节点的节点数。
• skipB：在 listB 中（从头节点开始）跳到交叉节点的节点数。

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被视作正确答案。

【示例 1】

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

【示例 2】

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

【示例 3】

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：No intersection
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null。

【提示】

listA 中节点数目为 $m$
listB 中节点数目为 $n$
$1<=m,n<=3\ast 10^4$
$1<=Node.val<=10^5$
$0<=skipA<=m$
$0<=skipB<=n$
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

进阶：你能否设计一个时间复杂度 $O(m+n)$、仅用 $O(1)$ 内存的解决方案？

【分析】

本题的思想也具有跳跃性，我们用两个指针 p 和 q 分别从 headA 和 headB 开始走，当 p 走到尽头后就从 headB 再重新开始走，当 q 走到尽头后就从 headA 再重新开始走。

假设 headA 到相交点的距离为 $a$，headB 到相交点的距离为 $b$，相交点到终点的距离为 $c$，那么 p 从 headA 走到尽头再从 headB 走到相交点的距离为 $a+c+b$；同理 q 从 headB 走到尽头再从 headA 走到相交点的距离也为 $b+c+a$。

因此这样在两个指针都走到尽头并交换起点继续走的时候一定能在链表的相交点相遇，如果没有相交，那么最后两个指针会同时为空，这样两个指针也是相等，因此代码就很好写，只要两个指针走到相等的时候就能判断结果。

【代码】

/**
 * 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) {
        ListNode *p = headA, *q = headB;
        while (p != q) p = p ? p->next : headB, q = q ? q->next : headA;
        return p;
    }
};

LeetCode 162. 寻找峰值（中等）

【题目描述】

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设 nums[-1] 与 nums[n] 为负无穷大。

你必须实现时间复杂度为 $O(logn)$ 的算法来解决此问题。

【示例 1】

输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。

【示例 2】

输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5 
解释：你的函数可以返回索引 1，其峰值元素为 2；
     或者返回索引 5， 其峰值元素为 6。

【提示】

$1<=nums.length<=1000$
$-2^{31}<=nums[i]<=2^{31}-1$
对于所有有效的 $i$ 都有 nums[i] != nums[i + 1]

【分析】

本题展现了二分不一定要求数组具有单调性。首先本题不可能无解，设左端点下标为 $i$，那么如果 $i+1$ 是降序的，那么 $i$ 就是峰值，因此只能是升序；同理如果 $i+2$ 是降序的，那么 $i+1$ 就是峰值，因此还是只能升序。容易发现如果整个序列中间某个地方出现了降序一定都会产生峰值，如果整个序列都是升序，那么右端点就是峰值。所以无论如何都至少存在一个峰值。

现在来看看如何二分确定峰值在哪。假设二分的中点为 nums[mid]，将其与下一个数进行比较：

• nums[mid] < nums[mid + 1]：右半部分区间一定存在峰值，因为右半区间只要出现降序就一定存在峰值，否则如果全是升序那么右端点也会是峰值，而左半部分如果全是升序是可能不存在峰值的；
• nums[mid] > nums[mid + 1]：左半部分区间一定存在峰值，因为左半区间只要出现升序再降序就一定存在峰值，否则如果全是降序那么左端点也会是峰值。

本题的边界情况需要考虑清楚，可以画个图结合代码的注释进行理解。

【代码】

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;  // mid 是下取整，因此 mid + 1 不可能越界，mid 等于 n 的唯一情况是 l = r = n
            if (nums[mid] > nums[mid + 1]) r = mid;  // 这种情况 nums[mid] 可能是峰值
            else l = mid + 1;  // nums[mid] < nums[mid + 1] 时 nums[mid] 不可能是峰值
        }
        return r;
    }
};

LeetCode 164. 最大间距（中等）

【题目描述】

给定一个无序的数组 nums，返回数组在排序之后，相邻元素之间最大的差值。如果数组元素个数小于 2，则返回 0。

您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。

【示例 1】

输入: nums = [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。

【示例 2】

输入: nums = [10]
输出: 0
解释: 数组元素个数小于 2，因此返回 0。

【提示】

$1<=nums.length<=10^5$
$0<=nums[i]<=10^9$

【分析】

本题的思路很难。首先我们遍历一遍数组找出最大值 MAX 和最小值 MIN，然后将 MIN ~ MAX 分成若干个等长的区间（假设区间统一为左开右闭），这样每个区间内可能会有若干个数，也可能一个数都没有。

划分完区间需要满足答案不在每个区间内部，即区间内相邻元素的差值均小于最大差值。那么这样答案就在区间之间，只需要维护每个区间的最小值与最大值，然后遍历一遍每个区间，答案一定是某个区间的最小值与其前一个区间的最大值之差。

那么区间长度如何确定才能满足条件？假设分为 $n-1$ 个区间，每个区间长度为 $len$，那么区间内最多有 $len$ 个数（假如区间为 (0, len]），区间内的最大差值为 $len-1$。如果每个区间都取最大差值还无法覆盖整个区间，说明全局的最大差值不在任何一个区间内，即 $(n-1)(len-1)<MAX-MIN$，化简后可以得到 $len$ 的范围：

$$\begin{gathered} (n-1)(len-1)\le MAX-MIN-1 \\ =len-1\le (MAX-MIN-1)/(n-1) \\ =len\le (MAX-MIN+n-2)/(n-1) \end{gathered}$$

【代码】

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        struct Range {
            int min, max;
            bool has_num;  // 区间是否存在元素
            Range() : min(INT_MAX), max(INT_MIN), has_num(false) {}
        };
        int n = nums.size();
        int MIN = INT_MAX, MAX = INT_MIN;
        for (int x: nums) MIN = min(MIN, x), MAX = max(MAX, x);
        if (n < 2 || MAX == MIN) return 0;  // 还可以特判一下是不是所有元素都相同
        vector<Range> r(n - 1);
        int len = (MAX - MIN + n - 2) / (n - 1);  // 区间长度
        for (int x: nums) {
            if (x == MIN) continue;  // 由于区间是左开右闭的，因此最小值不算在任何区间内
            int k = (x - MIN - 1) / len;  // 区间索引，注意要先减去 MIN，例如第一个区间为 [MIN, MIN + len - 1]
            r[k].min = min(r[k].min, x), r[k].max = max(r[k].max, x), r[k].has_num = true;
        }
        int res = 0;
        for (int i = 0, last = MIN; i < n - 1; i++)  // last 为上一个区间的最大值
            if (r[i].has_num) res = max(res, r[i].min - last), last = r[i].max;
        return res;
    }
};

LeetCode 165. 比较版本号（中等）

【题目描述】

给你两个版本号字符串 version1 和 version2，请你比较它们。版本号由被点 '.' 分开的修订号组成。修订号的值是它转换为整数并忽略前导零。

比较版本号时，请按从左到右的顺序依次比较它们的修订号。如果其中一个版本字符串的修订号较少，则将缺失的修订号视为 0。

返回规则如下：

• 如果 version1 < version2 返回 -1；
• 如果 version1 > version2 返回 1；
• 除此之外返回 0。

【示例 1】

输入：version1 = "1.2", version2 = "1.10"
输出：-1
解释：version1 的第二个修订号为 "2"，version2 的第二个修订号为 "10"：2 < 10，所以 version1 < version2。

【示例 2】

输入：version1 = "1.01", version2 = "1.001"
输出：0
解释：忽略前导零，"01" 和 "001" 都代表相同的整数 "1"。

【示例 3】

输入：version1 = "1.0", version2 = "1.0.0.0"
输出：0
解释：version1 有更少的修订号，每个缺失的修订号按 "0" 处理。

【提示】

$1<=version1.length,version2.length<=500$
version1 和 version2 仅包含数字和 '.'
version1 和 version2 都是有效版本号
version1 和 version2 的所有修订号都可以存储在 32 位整数中

【分析】

本题就很简单了，直接按照提议模拟即可，遍历两个字符串将对应位置的版本号转换为整数进行比较。

【代码】

class Solution {
public:
    int compareVersion(string version1, string version2) {
        int n = version1.size(), m = version2.size();
        int i = 0, j = 0;
        while (i < n || j < m) {
            int a = i, b = j, v1 = 0, v2 = 0;
            while (a < n && version1[a] != '.') v1 = v1 * 10 + (version1[a] - '0'), a++;  // 不加括号可能会溢出
            while (b < m && version2[b] != '.') v2 = v2 * 10 + (version2[b] - '0'), b++;
            if (v1 < v2) return -1;
            else if (v1 > v2) return 1;
            i = a + 1, j = b + 1;
        }
        return 0;
    }
};