「每日LeetCode」2020年9月14日

本文最后更新于：2023年3月19日 晚上

Lt121.买卖股票的最佳时机、122.买卖股票的最佳时机 II、剑指 Offer 62. 圆圈中最后剩下的数字、剑指 Offer 55 - I. 二叉树的深度

121.买卖股票的最佳时机

Category Difficulty Likes Dislikes
algorithms Easy (54.88%) 1175 -

Tags
array | dynamic-programming
Companies
amazon | bloomberg | facebook | microsoft | uber
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。

示例 1:

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

示例 2:

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

Discussion | Solution

思路

暴力

双重循环，从最后一个开始计算，当前卖出可得的最大利润，计算完再令下标减一，继续计算。

动态规划

  1. 记录【今天之前买入的最小值】
  2. 计算【今天之前最小值买入，今天卖出的获利】，也即【今天卖出的最大获利】
  3. 比较【每天的最大获利】，取最大值即可

解答

暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
 * @lc app=leetcode.cn id=121 lang=javascript
 *
 * [121] 买卖股票的最佳时机
 */

// @lc code=start
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  let max = 0;
  for (let i = prices.length - 1; i >= 0; i--) {
    for (let j = i - 1; j >= 0; j--) {
      if (prices[i] - prices[j] > 0 && prices[i] - prices[j] > max)
        max = prices[i] - prices[j];
    }
  }
  return max;
};
// @lc code=end
1
2
3
4
Accepted
200/200 cases passed (440 ms)
Your runtime beats 10.22 % of javascript submissions
Your memory usage beats 37.05 % of javascript submissions (38.6 MB)

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
 * @lc app=leetcode.cn id=121 lang=javascript
 *
 * [121] 买卖股票的最佳时机
 */

// @lc code=start
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  if (prices.length <= 1) return 0;
  let min = prices[0];
  let max = 0;
  for (const price of prices) {
    min = Math.min(min, price);
    max = Math.max(price - min, max);
  }
  return max;
};
// @lc code=end
1
2
3
4
Accepted
200/200 cases passed (80 ms)
Your runtime beats 81.42 % of javascript submissions
Your memory usage beats 11.25 % of javascript submissions (40.6 MB)

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

Category Difficulty Likes Dislikes
algorithms Easy (63.06%) 847 -

Tags
array | greedy
Companies
bloomberg
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

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

示例  3:

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

提示：

  • 1 <= prices.length <= 3 * 10 ^ 4
  • 0 <= prices[i] <= 10 ^ 4

Discussion | Solution

思路

[7, 1, 5, 6]  第二天买入，第四天卖出，收益最大（6-1），所以一般人可能会想，怎么判断不是第三天就卖出了呢? 这里就把问题复杂化了，根据题目的意思，当天卖出以后，当天还可以买入，所以其实可以第三天卖出，第三天买入，第四天又卖出（（5-1）+ （6-5） === 6 - 1）。所以算法可以直接简化为只要今天比昨天大，就卖出。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
 * @lc app=leetcode.cn id=122 lang=javascript
 *
 * [122] 买卖股票的最佳时机 II
 */

// @lc code=start
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  if (prices.length <= 1) return 0;
  let res = 0;
  for (let i = 1; i < prices.length; i++) {
    if (prices[i] > prices[i - 1]) res += prices[i] - prices[i - 1];
  }
  return res;
};
// @lc code=end
1
2
3
4
Accepted
200/200 cases passed (76 ms)
Your runtime beats 87.1 % of javascript submissions
Your memory usage beats 24.03 % of javascript submissions (38.6 MB)

剑指 Offer 62. 圆圈中最后剩下的数字

0,1,,n-1 这 n 个数字排成一个圆圈，从数字 0 开始，每次从这个圆圈里删除第 m 个数字。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4 这 5 个数字组成一个圆圈，从数字 0 开始每次删除第 3 个数字，则删除的前 4 个数字依次是 2、0、4、1，因此最后剩下的数字是 3。
示例 1：

1
2
3

输入: n = 5, m = 3
输出: 3

示例 2：

1
2
输入: n = 10, m = 17
输出: 2

限制：

  • 1 <= n <= 10^5
  • 1 <= m <= 10^6

思路

模拟队列

使用队列特性模拟圆圈，将报数的前几个移动到队列末尾，移出第一个。当 n 很大时，造成超时。

数学公式-约瑟夫环

约瑟夫环是一个经典的数学问题，我们不难发现这样的依次报数，似乎有规律可循。为了方便导出递推式，我们重新定义一下题目。
问题： N 个人编号为 1，2，……，N，依次报数，每报到 M 时，杀掉那个人，求最后胜利者的编号。
这边我们先把结论抛出了。之后带领大家一步一步的理解这个公式是什么来的。
递推公式：

  • 表示，N 个人报数，每报到 M 时杀掉那个人，最终胜利者的编号
  • 表示，N-1 个人报数，每报到 M 时杀掉那个人，最终胜利者的编号

下面我们不用字母表示每一个人，而用数字。
1、2、3、4、5、6、7、8、9、10、11
表示 11 个人，他们先排成一排，假设每报到 3 的人被杀掉。

  • 刚开始时，头一个人编号是 1，从他开始报数，第一轮被杀掉的是编号 3 的人。
  • 编号 4 的人从 1 开始重新报数，这时候我们可以认为编号 4 这个人是队伍的头。第二轮被杀掉的是编号 6 的人。
  • 编号 7 的人开始重新报数，这时候我们可以认为编号 7 这个人是队伍的头。第三轮被杀掉的是编号 9 的人。
  • ……
  • 第九轮时，编号 2 的人开始重新报数，这时候我们可以认为编号 2 这个人是队伍的头。这轮被杀掉的是编号 8 的人。
  • 下一个人还是编号为 2 的人，他从 1 开始报数，不幸的是他在这轮被杀掉了。
  • 最后的胜利者是编号为 7 的人。

下图表示这一过程（先忽视绿色的一行）

现在再来看我们递推公式是怎么得到的！
将上面表格的每一行看成数组，这个公式描述的是：幸存者在这一轮的下标位置

  • f(1,3)f(1,3))：只有 1 个人了，那个人就是获胜者，他的下标位置是 0
  • f(2,3)=(f(1,3)+3)%2=3%2=1f(2,3)=(f(1,3)+3)%2=3%2=1：在有 2 个人的时候，胜利者的下标位置为 1
  • f(3,3)=(f(2,3)+3)%3=4%3=1f(3,3)=(f(2,3)+3)%3=4%3=1：在有 3 个人的时候，胜利者的下标位置为 1
  • f(4,3)=(f(3,3)+3)%4=4%4=0f(4,3)=(f(3,3)+3)%4=4%4=0：在有 4 个人的时候，胜利者的下标位置为 0
  • ……
  • f(11,3)=6f(11,3)=6

解答

模拟队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @param {number} n
 * @param {number} m
 * @return {number}
 */
var lastRemaining = function (n, m) {
  let queue = [...Array(n).keys()];
  while (queue.length > 1) {
    let count = (m - 1) % queue.length;
    queue = queue.concat(queue.splice(0, count));
    queue.shift();
  }
  return queue.shift();
};

数学公式-约瑟夫环

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * @param {number} n
 * @param {number} m
 * @return {number}
 */
var lastRemaining = function (n, m) {
  let p = 0;
  for (let i = 2; i <= n; i++) {
    p = (p + m) % i;
  }
  return p;
};

剑指 Offer 55 - I. 二叉树的深度

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例如：
给定二叉树 [3,9,20,null,null,15,7]，

1
2
3
4
5
3
 / \
9  20
  /  \
 15   7

返回它的最大深度  3 。

提示：

  1. 节点总数 <= 10000

注意：本题与主站 104  题相同：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

思路

树题套路，最小规模解析，再递归即可。如果为叶子节点，返回 1。如果两个节点都有，返回 1+左边或右边子树的最大深度。只有左右节点其中一个，返回 1+左右子树的深度。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function (root) {
  return visit(root);
};

const visit = (root) => {
  if (!root) return 0;
  if (!root.left && !root.right) return 1;
  else if (root.left && root.right)
    return 1 + Math.max(visit(root.left), visit(root.right));
  else if (root.left) return 1 + visit(root.left);
  else return 1 + visit(root.right);
};