每日一题（精华版）

发表于 2022-06-03 更新于 2022-06-23 分类于算法阅读次数：

本文字数： 8.4k 阅读时长 ≈ 8 分钟

本文收录了 Leetcode 每日一题中，比较值得记录的算法题。

写在前面

Easy	Medium	Hard
😍	😏	🤔

🤔 829. 连续整数求和

题目描述

829. 连续整数求和

给定一个正整数 n，返回连续正整数满足所有数字之和为 n 的组数。

示例 1:

输入: n = 5
输出: 2
解释: 5 = 2 + 3，共有两组连续整数([5],[2,3])求和后为 5。

示例 2:

输入: n = 9
输出: 3
解释: 9 = 4 + 5 = 2 + 3 + 4

示例 3:

输入: n = 15
输出: 4
解释: 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5

提示:

1 <= n <= 109

解法：找规律

/**
 * @param {number} n
 * @return {number}
 */
var consecutiveNumbersSum = function(n) {
    let res = 0;
    let i = 1;
    while (i > 0) {
        const sum = (1 + (i - 1)) * (i - 1) / 2;
        if (n - sum <= 0) break;
        if ((n - sum) % i === 0) {
            res++;
        }
        i++;
    }
    return res;
};

思路

当 $n = 9$ 时，由于 $2 + 3 + 4 = 9$，设 $x = 2$，则 $x + (x + 1) + (x + 2) = 9$ 。

现在开始找规律！

当连续 1 个正整数之和等于 n 时：
$$
n = x
$$
当连续 2 个正整数之和等于 n 时：
$$
n = x + (x + 1)
= (2 * x) + 1
$$
当连续 3 个正整数之和等于 n 时：
$$
n = x + (x + 1) + (x + 2)
= (3 * x) + (x + 2)
$$
当连续 4 个正整数之和等于 n 时：
$$
n = x + (x + 1) + (x + 2) + (x + 3)
= (4 * x) + (1 + 2 + 3)
$$
当连续 i 个正整数之和等于 n 时：
$$
n = x + (x + 1) + (x + 2) + (x + 3) + … + (x + (i - 1))
= (i * x) + (1 + 2 + 3 + … + (i - 1))
$$
变形可得：
$$
x = \frac{n - (1 + 2 + 3 + … + (i - 1))}{i}
$$
由等差数列的求和公式 $S = \frac{(1+n)*n}{2}$，可将上式写为：
$$
x = \frac{n - sum}{i}
= \frac{n - \frac{(1 + (i-1)) * (i-1)}{2}}{i}
$$
综上所述，当 x 为正整数，也就是 (n - sum) % i === 0 时，说明存在连续 i 个正整数之和等于 n，所以 res++ 。

且当 n - sum <= 0 时，说明已没有比 i 个更多的连续正整数之和等于 n，所以应跳出循环。

提交记录

提交结果	执行用时	内存消耗	语言	提交时间	备注
通过	64 ms	41.1 MB	JavaScript	2022/06/03 02:39	找规律

🤔 732. 我的日程安排表 III

题目描述

732. 我的日程安排表 III

当 k 个日程安排有一些时间上的交叉时（例如 k 个日程安排都在同一时间内），就会产生 k 次预订。

给你一些日程安排 [start, end) ，请你在每个日程安排添加后，返回一个整数 k ，表示所有先前日程安排会产生的最大 k 次预订。

实现一个 MyCalendarThree 类来存放你的日程安排，你可以一直添加新的日程安排。

MyCalendarThree() 初始化对象。
int book(int start, int end) 返回一个整数 k ，表示日历中存在的 k 次预订的最大值。

示例：

输入：
[“MyCalendarThree”, “book”, “book”, “book”, “book”, “book”, “book”]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
输出：
[null, 1, 1, 2, 3, 3, 3]

解释：
MyCalendarThree myCalendarThree = new MyCalendarThree();
myCalendarThree.book(10, 20); // 返回 1 ，第一个日程安排可以预订并且不存在相交，所以最大 k 次预订是 1 次预订。
myCalendarThree.book(50, 60); // 返回 1 ，第二个日程安排可以预订并且不存在相交，所以最大 k 次预订是 1 次预订。
myCalendarThree.book(10, 40); // 返回 2 ，第三个日程安排 [10, 40) 与第一个日程安排相交，所以最大 k 次预订是 2 次预订。
myCalendarThree.book(5, 15); // 返回 3 ，剩下的日程安排的最大 k 次预订是 3 次预订。
myCalendarThree.book(5, 10); // 返回 3
myCalendarThree.book(25, 55); // 返回 3

提示：

0 <= start < end <= 109
每个测试用例，调用 book 函数最多不超过 400次

解法：插旗法 / 差分数组

var MyCalendarThree = function() {
  this.booked = new Map();
};

/** 
 * @param {number} start 
 * @param {number} end
 * @return {number}
 */
MyCalendarThree.prototype.book = function(start, end) {
  let k = 0;
  let flags = 0; // 当前旗子数
  this.booked.set(start, this.booked.has(start) ? this.booked.get(start) + 1 : 1); // 进入 => 插旗
  this.booked.set(end, this.booked.has(end) ? this.booked.get(end) - 1 : -1); // 离开 => 拔旗

  // 对 map 的 key 排序
  let arr = Array.from(this.booked);
  arr.sort((a, b) => a[0] - b[0]);
  this.booked = new Map(arr.map(e => [e[0], e[1]]));

  for (const [key, value] of this.booked) {
    flags += value;
    k = Math.max(k, flags);
  }
  
  return k;
};

/**
 * Your MyCalendarThree object will be instantiated and called as such:
 * var obj = new MyCalendarThree()
 * var param_1 = obj.book(start,end)
 */

思路

此方法适合解区间的最大重叠数量（或最大并行数量）的题目。

何为插旗法？

进入一个区间的时候将该点旗子数+1，代表插上一面 🚩 ；离开时将该点旗子数-1，代表拔出一面 🚩 。

若区间之间不重合，则任意连续两个点的旗子数之和必然等于 0 ，如一个为 +1，下一个为 -1；若区间之间重合，则存在连续两个点的旗子数之和必然大于 0，如一个为 +1，下一个也为 +1。

举个例子的话：

① [10, 20]；② [50, 60]；③ [10, 40]；④ [5, 15]

① 时的插旗坐标 <10, 1> <20, -1>，此时任意两个连续点的旗子数之和都为 0。

② 时的插旗坐标 <10, 1> <20, -1> <50, 1> <60, -1>，此时任意两个连续点的旗子数之和都为 0。

③ 时的插旗坐标 <10, 2> <20, -1> <40, -1> <50, 1> <60, -1>，此时存在两点 <10, 2> 和 <20, -1> 的旗子数之和为 1，说明区间存在重叠！

④ 时的插旗坐标 <5, 1> <10, 2> <15, -1> <20, -1> <40, -1> <50, 1> <60, -1>，此时存在两点 <5, 1> 和 <10, 2> 的旗子数之和为 3，说明区间又存在重叠了！

我们还会注意到，如果将所有点的旗子数依次（必须将点由小到大排序）累加，累加过程中出现的最大值，即为区间重叠的最大次数。对应代码的第 21- 24 行。

在本方法中，我们使用 Map 来存储插旗坐标，且正如上文所说，每次更新 Map 都需要对 Map 中的 key 即点的坐标由小到大排序。对应 16 - 19 行代码。

提交记录

提交结果	执行用时	内存消耗	语言	提交时间	备注
通过	816 ms	52 MB	JavaScript	2022/06/06 01:56	插旗法

😍 1037. 有效的回旋镖

题目描述

1037. 有效的回旋镖

给定一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点，如果这些点构成一个回旋镖则返回 true 。

回旋镖 定义为一组三个点，这些点各不相同且 不在一条直线上 。

示例 1：

输入：points = [[1,1],[2,3],[3,2]]
输出：true

示例 2：

输入：points = [[1,1],[2,2],[3,3]]
输出：false

提示：

points.length == 3
points[i].length == 2
0 <= xi, yi <= 100

解法：点斜式判断三点是否共线

/**
 * @param {number[][]} points
 * @return {boolean}
 */
var isBoomerang = function(points) {
  const len = points.length;
  points = Array.from(new Set(points.map(e => e.toString()))).map(e => e.split(','));
  if (points.length < len) return false;

  // 点斜式 y - y1 = k(x - x1)
  if (points[1][0] - points[0][0] !== 0) {
    const k = (points[1][1] - points[0][1]) / (points[1][0] - points[0][0]);
    if ((points[2][1] - points[0][1]) / (points[2][0] - points[0][0]) === k) return false;
  } else {
    if (points[2][0] === points[0][0]) return false;
  }
  
  return true;
};

当然，我这个方法不够简洁，判断三点是否共线可以看这篇文章《数学推导不在一条直线公式》。

将本题收录在本篇博客中，是想强调上述代码的第 7 行：对 points 进行去重时，使用的方法。

我们都知道，数组去重可以使用 Array.from(new Set(要去重的数组)) ，但是由于本题中 points 的元素为数组，因此那样做无法达到去重的目的。所以，我使用 points.map(e => e.toString()) 将 points 的元素全部变为字符串，再对 points 进行去重，然后再将去重后的 points 中的每个字符串元素转回数组。注意 ⚠️ ，如果原来的 points 为 [[0,1],[0,1],[2,1]] 的话，去重后的 points 将为 [['0','1'],['2','1']] 。由于不影响后面的运算，因此就没有继续对其处理。

🤔 30. 串联所有单词的子串

题目描述

30. 串联所有单词的子串

给定一个字符串 s 和一些长度相同的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

示例 1：

输入：s = “barfoothefoobarman”, words = [“foo”,“bar”]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 “barfoo” 和 “foobar” 。
输出的顺序不重要, [9,0] 也是有效答案。

示例 2：

输入：s = “wordgoodgoodgoodbestword”, words = [“word”,“good”,“best”,“word”]
输出：[]
示例 3：

输入：s = “barfoofoobarthefoobarman”, words = [“bar”,“foo”,“the”]
输出：[6,9,12]

提示：

1 <= s.length <= 104
s 由小写英文字母组成
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] 由小写英文字母组成

⛔️ 解法：回溯算法【超时】

最近做题生疏了，看到这道题第一反应竟然是回溯算法 😅。

思路：将 words 中的所有元素进行全排列（需要考虑重复元素），然后对字符串 s 使用 indexOf() 方法，求出全排列后的每个元素在 s 中的下标。

例如：s = "barfoothefoobarfooman" words = ["foo","bar","foo"]，对 words 进行全排列，得 subStrs = [ 'foobarfoo', 'foofoobar', 'barfoofoo' ]，再对 subStrs 中的每个元素求出其在 s 中的下标即可。

代码如下：

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function(s, words) {
  const res = [];
  const subStrs = [];
  const track = [];
  const map = new Map();
  words.forEach((word, i) => {
    map.set(i, 0);
  })
  backtrack(track, 0);
  for (let str of subStrs) {
    let idx = s.indexOf(str);
    while(idx !== -1) {
      res.push(idx);
      idx = s.indexOf(str, idx + 1);
    }
  }
  return Array.from(new Set(res));

  function backtrack(track, start) {
    if (track.length === words.length) {
      const str = track.join('');
      if (!subStrs.includes(str)) subStrs.push(str);
      return;
    }
    for (let i = 0; i < words.length; i++) {
      if (map.get(i) === 1) continue;
      track.push(words[i]);
      map.set(i, 1);
      backtrack(track, i + 1);
      track.pop();
      map.set(i, 0);
    }
  }
};

然鹅，在执行这个用例时，会超出时间限制。查看提交记录

解法：滑动窗口

**既然这道题是子串问题，那么我们第一时间就应该想到用“滑动窗口”来解决这道题。**起初，我是这样写的：

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function(s, words) {
  let res = [];
  let need = new Map(), window = new Map();
  for (let word of words) {
    need.has(word) ? need.set(word, need.get(word) + 1) : need.set(word, 1);
  }
  
  let left = 0, right = 0;
  let valid = 0;
  while(right < s.length) {
    const strR = s.slice(right, right + words[0].length);
    right += words[0].length;
    if (need.has(strR)) {
      window.has(strR) ? window.set(strR, window.get(strR) + 1) : window.set(strR, 1);
      if (need.get(strR) === window.get(strR)) valid++;
    }

    while (valid === need.size) {
      if (right - left === words[0].length * words.length) res.push(left);
      const strL = s.slice(left, left + words[0].length);
      left += words[0].length;
      if (need.has(strL)) {
        if (need.get(strL) === window.get(strL)) valid--;
        window.set(strL, window.get(strL) - 1);
      }
    }
  }
  
  return res;
};

注意，题干中有说 words 中的单词的长度都相同，所以滑动窗口可以每次滑动 words[0].length 个字符，如代码第 17 行和第 26 行所示。

但是当执行这个用例时，出现了错误。简单来说就是当 s = "ababaab" words = ["ab","ba","ba"] 时，输出 [] 而不是 [1]，所以我们应该考虑截断 s 的第 0 ~ words[0].length - 1 个字符。就像在上例中，我们需要将 s 截断为 "babaab" 才能求出正确答案。

因此，正确的代码如下：

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function(s, words) {
  let res = [];
  let need = new Map();
  for (let word of words) {
    need.has(word) ? need.set(word, need.get(word) + 1) : need.set(word, 1);
  }
  
  for (let start = 0; start < words[0].length; start++) {
    let window = new Map();
    let left = start, right = start;
    let valid = 0;
    while(right < s.length) {
      const strR = s.slice(right, right + words[0].length);
      right += words[0].length;
      if (need.has(strR)) {
        window.has(strR) ? window.set(strR, window.get(strR) + 1) : window.set(strR, 1);
        if (need.get(strR) === window.get(strR)) valid++;
      }

      while (valid === need.size) {
        if (right - left === words[0].length * words.length) res.push(left);
        const strL = s.slice(left, left + words[0].length);
        left += words[0].length;
        if (need.has(strL)) {
          if (need.get(strL) === window.get(strL)) valid--;
          window.set(strL, window.get(strL) - 1);
        }
      }
    }
  }
  
  return res;
};

提交记录

提交结果	执行用时	内存消耗	语言	提交时间	备注
超出时间限制	N/A	N/A	JavaScript	2022/06/23 02:08	⛔️ 回溯算法
通过	76 ms	43.4 MB	JavaScript	2022/06/23 01:50	滑动窗口
解答错误	N/A	N/A	JavaScript	2022/06/23 01:37	⛔️ 应考虑截断