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

[Checkson]

236. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

       _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4_      7       9
         /  \
         3   5

示例1：

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例2：

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明：

• 所有节点的值都是唯一的。
• p、q 为不同节点且均存在于给定的二叉搜索树中。

解法一（递归）

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    if (root === null || root === p || root === q) {
        return root;
    }
    // 若q和p分别在root左右两边
    if ((root.val > p.val && root.val < q.val) ||
        (root.val < p.val && root.val > q.val)) {
        return root;
    }
    // 若q和p都在root的左边
    if (p.val < root.val && q.val < root.val) {
        return lowestCommonAncestor(root.left, p, q);
    } else {
        return lowestCommonAncestor(root.right, p, q);
    }
};

解析：

这种递归的解法，抓住二叉搜索树的特点（根节点，比其所有左子树上的所有节点大，比其所有右子节点上的节点小）。

• 我们先判断根节点是否为空，或者是否等于q和p节点其中之一。
• 然后我们判断q、p节点是分别在root节点的左右两边。若满足这个条件，这时候就可以返回root了。
• 最后我只需判断q和p节点，是都在root节点的左边，还是在root节点的右边，然后递归者三个步骤，就得出答案了。

这种方法写法简洁，但是递归毕竟是递归，非常吃内存消耗。若这棵二叉搜索树层次非常深，递归方式将会产生非常深的调用栈，对于我们这种对性能追求极致的"极客"来说，是容忍不了。那么我们看看下面比较通用的、非递归的解法。

解法二（非递归）

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    if (root == null || p == null || q == null) {
        return root;
    }
    var queue = [],
        nodes = [],
        rear = -1,
        front = -1;
    nodes.push(root);
    queue.push(-1);
    rear++;
    while (front != rear) {
        front++;
        var node = nodes[front];
        if (node.left) {
            nodes.push(node.left);
            queue.push(front);
            rear++;
        }
        if (node.right) {
            nodes.push(node.right);
            queue.push(front);
            rear++;
        }
    }
    var pIndex = null, qIndex = null;
    for (var i = 0, len = nodes.length; i < len; i++) {
        if (p.val === nodes[i].val) {
            pIndex = i;
        } else if (q.val === nodes[i].val) {
            qIndex = i;
        }
    }
    var queue1 = [],
        queue2 = [];
    while (pIndex != -1 || qIndex != -1) {
        if (pIndex != -1) {
            queue1.push(pIndex);
            pIndex = queue[pIndex];   
        }
        if (qIndex != -1) {
            queue2.push(qIndex);
            qIndex = queue[qIndex];
        }
    }
    var foundIndex = -1;
    for (var i = 0, len1 = queue1.length; i < len1; i++) {
        for (var j = 0, len2 = queue2.length; j < len2; j++) {
            if (queue1[i] === queue2[j]) {
                foundIndex = queue1[i];
                break;
            }
        }
        if (foundIndex > -1) {
            break;
        }
    }
    return foundIndex > -1 ? nodes[foundIndex] : null;
};

215. 数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例1：

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例2：

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

这道题目并不困难，将数组从大到小排序后，然后找出下标为 k - 1 的元素就可以了，这里我介绍三种基础且常见的排序算法。

冒泡排序：

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    var len = nums.length;
    for (var i = 0; i < len - 1; i++) {
        for (var j = 0; j < len - i - 1; j++) {
            if (nums[j] < nums[j + 1]) {
                var temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
    }
    return nums[k - 1];
};

选择排序：

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    var len = nums.length;
    for (var i = 0; i < len; i++) {
        var max = nums[i], z = i;
        for (var j = i; j < len; j++) {
             if (nums[j] > max) {
                 max = nums[j];
                 z = j;
             }
        }
        if (z !== i) {
            var temp = nums[i];
            nums[i] = nums[z];
            nums[z] = temp;
        }
    }
    return nums[k - 1];
};

插入排序：

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    var len = nums.length;
    for (var i = 1; i < len; i++) {
        var j = i - 1, temp = nums[i];
        while (j > -1 && temp > nums[j]) {
            nums[j + 1] = nums[j];
            j--;
        }
        nums[j + 1] = temp;
    }
    return nums[k - 1];
};

122. 买卖股票的最佳时机 II

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

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意： 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例2：

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例3：

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

题解（贪心算法）：

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

解析：

贪心算法，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

可以看出，我们总是求解 maxPro > 0 的时候，因为这个是赚钱的情况。只要满足 maxPro > 0，那么证明股票这时候买入卖出就会赚，而且会又叠加效应，否则，并不会去股票交易，因为会出现亏损。