Open
Description
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，那么证明股票这时候买入卖出就会赚，而且会又叠加效应，否则，并不会去股票交易，因为会出现亏损。
Metadata
Metadata
Assignees
Labels
No labels