LeetCode(力扣)答案解析（六）

[Checkson]

121. 买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例1：

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例2：

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

解法一（暴力法）：

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    var len = prices.length,
          ans = 0;
    for (var i = 0; i < len - 1; i++) {
        for (var j = i + 1; j < len; j++) {
            var res = prices[j] - prices[i];
            res > ans && (ans = res);
        }
    }
    return ans;
};

解析：

这种解法的时间复杂度为O(n²)，提交竟然没有超时，很让人惊讶。暴力法的思路很简单，就是逐个元素，用其后的元素减去这个元素，记录最大值。

解法二（动态规划）：

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    var min = prices[0] || 0,
          max = 0;
    for (var i = 1, len = prices.length; i < len; i++) {
        if (prices[i] < min) {
            min = prices[i];
        } else if (prices[i] - min > max) {
            max = prices[i] - min;
        }
    }
    return max;
};

解析：

这种解法的时间复杂度为O(n)，性能有了质的提高。动态规划的解法，思路也是比较简单，遍历prices数组种的数字，并记录最小值，若找到，直接更新最小值；若没找到，将当前遍历的数减去最小值，再和已知最大的值对比，然后重新记录最大值。

141. 环形链表

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

示例1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

题解 （双指针）：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    if (head == null || head.next == null) {
        return false;
    }
    var slow = head,
        fast = head.next;
    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
};

解析：

这种解题思路，非常巧妙。我们用两个指针来遍历链表，其中一个指针比另外一个指针移动快两倍，这样，当快的指针遍历了两次链表，慢的指针就刚好遍历一次链表，若链表有环，最后slow和fast必然相等。否则，链表就不存在环。

160. 相交链表

编写一个程序，找到两个单链表相交的起始节点。

例如，下面的两个链表：

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

在节点 c1 开始相交。

注意：

• 如果两个链表没有交点，返回 null.
• 在返回结果后，两个链表仍须保持原有的结构。
• 可假定整个链表结构中没有循环。
• 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

题解：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    var p1 = headA,
        p2 = headB;
    while (headA != null && headB != null) {
        headA = headA.next;
        headB = headB.next;
    }
    while (headA != null) {
        headA = headA.next;
        p1 = p1.next;
    }
    while (headB != null) {
        headB = headB.next;
        p2 = p2.next;
    }
    while (p1 != null && p2 != null) {
        if (p1 === p2) {
            return p1;
        }
        p1 = p1.next;
        p2 = p2.next;
    }
    return null;
};

解析：

这里思路理解起来也不难。第一个循环只要是找出较长的链表，第二和第三个循环，是为了纠正两个链表的长度，保证在进入第四个循环前，p1和p2两个链表长度一样。那么，在进入第四个循环体内，一切对比就变得非常轻松。