1、题干​

列表 arr 由在范围 [1, n] 中的所有整数组成，并按严格递增排序。请你对 arr 应用下述算法：

• 从左到右，删除第一个数字，然后每隔一个数字删除一个，直到到达列表末尾。
• 重复上面的步骤，但这次是从右到左。也就是，删除最右侧的数字，然后剩下的数字每隔一个删除一个。
• 不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。

给你整数 n ，返回 arr 最后剩下的数字。

示例 1：

输入：n = 9
输出：6
解释：
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
arr = [2, 4, 6, 8]
arr = [2, 6]
arr = [6]

示例 2：

输入：n = 1
输出：1

提示：

• 1 <= n <= 109

2、解题思路​

根据题意可知，消除的总轮次为Math.log2(n)，每轮消除后剩下的数字都构成等差数列。

\ 因此可以借助最小值min、最大值max、步长step3个变量来维护等差数列，每轮都更新等差数列的3个变量；最后一轮只剩一个数字，即min与max相等，任取一个返回即可。

\ 需要注意的是奇数轮次是从左到右消除，即最小值必定改变，最大值只在等差数列个数为奇数时改变；偶数轮次则相反，最大值必定改变，最小值只在等差数列个数为奇数时改变。

3、代码​

var lastRemaining = function (n) {
    let min = 1, max = n, step = 1;
    for (let i = 1; i <= Math.log2(n); i++) {
        if (i % 2) {
            if (((max - min) / step + 1) % 2) max -= step;
            min += step;
        } else {
            if (((max - min) / step + 1) % 2) min += step;
            max -= step;
        }
        step *= 2;
    }
    return max;
};

4、执行结果​

1、题干​

对于一个 正整数，如果它和除了它自身以外的所有 正因子 之和相等，我们称它为 「完美数」。

给定一个 整数 n， 如果是完美数，返回 true；否则返回 false。

示例 1：

输入：num = 28
输出：true
解释：28 = 1 + 2 + 4 + 7 + 14
1, 2, 4, 7, 和 14 是 28 的所有正因子。

示例 2：

输入：num = 7
输出：false

提示：

• 1 <= num <= 108

2、解题思路​

在区间 [ 1,$\sqrt{num}$ ] 中找 $num$ 的因子i，是因子则累加i + num / i（i=1时只加1），最后判断因子之和是否等于 $num$ 即可。

3、代码​

var checkPerfectNumber = function (num) {
    let sum = 1;
    for (let i = 2; i * i <= num; i++) {
        if (num % i === 0) sum += i + num / i;
    }
    return num === 1 ? false : sum === num;
};

4、困惑​

题目比较简单，找一个正整数的所有正整数因子只需要遍历到 $\sqrt{n}$ 的结论也一直记着。如果用数学归纳法，举几个例子很容易推出这个结论。

官解这么说：如果 ${n}$ 有一个大于 $\sqrt{n}$ 的因子 $d$，那么它一定有一个小于$\sqrt{n}$的因子$\dfrac{n}{d}$。也就是说 ${n}$ 的因子总是成对出现。

但是有两个关键问题始终让人很困惑：1、为什么遍历终点是 $\sqrt{n}$，2、因子有没有大于 $\sqrt{n}$ 且未被找到的特例。实际上可以用高中数学做个推导，来解答这些困惑。过程有点繁琐，如果对过程不感兴趣可以直接看最后的结论。

5、推导​

假设要找正整数 $n$ 的所有正整数因子 $x$ 和 $y$。（注意：以下推导只考虑正整数范围内的情况）

必然有$xy=n$，移项得到 $y=\dfrac{n}{x}$。

反比例函数

这个函数是不是很眼熟，没错它就是高中数学课本里的反比例函数。以 $y=\dfrac{4}{x}$ 为例，其图形如下：

从上图可以很容易看出，反比例函数上的任意坐标 $(x',y')$ 对应的整数 $x'$ 和 $y'$ 都是 $4$ 的因子。这跟官解所说 ${n}$ 的因子总是成对出现的意思一致。也就是找到一个因子 $x'$ 时，必然找到了另外一个因子 $y'$ 。

反比例函数的对称性

反比例函数图像是以 $y=x$ 为对称轴的轴对称图形（反比例函数对称特性）。以 $y=\dfrac{4}{x}$ 为例，其图形如下：

关于 $y=x$ 对称的两个点，他们的坐标是 $x$ 和 $y$ 互换，即任意坐标 $(x',y')$ 的对称点为 $(y',x')$。例如：从上图很容易看出坐标 $(4,1)$ 关于 $y=x$ 对称的点是 $(1,4)$。

由此可得 $n$ 的任意因子对 $(x',y')$ 具有关于 $y=x$ 对称的性质。

而 $y=x$ 与 $y=\dfrac{n}{x}$ 的交点 $Q$ 的坐标是 $(\sqrt{n},\sqrt{n})$。

最后可得，假设遍历因子时取数自 $x$ 轴，在交点 $Q$ 左上侧出现过的任意点 $(x',y')$（其中 $x'<\sqrt{n}$ 且 $y'>\sqrt{n}$），都会在交点的右下侧以 $(y',x')$ 的形式出现。

也就是说，遍历大于 $\sqrt{n}$ 的因子本质上是在重复遍历小于 $\sqrt{n}$ 的因子，只是把小于 $\sqrt{n}$ 时找到的因子对进行 $x$ 、 $y$ 互换位置而已。

因此遍历到 $\sqrt{n}$ 就能找到所有因子，而且没有大于 $\sqrt{n}$ 而未被找到的特例因子，这也就解释了前文提到的两个困惑。

举个例子

$n=36$ 的因子对是 $(1,36)$ $(2,18)$ $(3,12)$ $(4,9)$ $(6,6)$ $(9,4)$ $(12,3)$ $(18,2)$ $(36,1)$

$n=81$ 的因子对是 $(1,81)$ $(3,27)$ $(9,9)$ $(27,3)$ $(81,1)$

可以发现因子对具有回文特性，这也是反比例函数对称性的体现。另外很容易看出$36$ 和 $81$ 这两个数都只要遍历到 $\sqrt{n}$ 即可找到所有因子。

6、小结​

找因子之所以只需要遍历到 $\sqrt{n}$，是因为：

• 因子之间存在反比例函数关系 $y=\dfrac{n}{x}$，所以因子总是成对出现
• 反比例函数关于 $y=x$ 对称，所以所有因子对也关于 $y=x$ 对称
• 而反比例函数 $y=\dfrac{n}{x}$ 图形与对称轴 $y=x$ 的交点是 $(\sqrt{n},\sqrt{n})$
• 所以在反比例函数的图形上，任意处于交点 $(\sqrt{n},\sqrt{n})$ 左上侧的点 $(x',y')$ ，都会在交点的右下侧以 $(y',x')$ 的形式出现（其中 $x'<\sqrt{n}$ 且 $y'>\sqrt{n}$）
• 所以遍历到 $\sqrt{n}$ 就能找到所有因子且不会出现大于 $\sqrt{n}$ 而未被找到的特例因子

也就是说，找因子只需要遍历到 $\sqrt{n}$ 即可，因为遍历大于 $\sqrt{n}$ 的因子本质上是在重复遍历小于 $\sqrt{n}$ 的因子，只是把小于 $\sqrt{n}$ 时找到的因子对进行 $x$ 、 $y$ 互换位置而已。 由于数轴上的数具有连续性（非离散），因此这个结论对于小数也成立。

1、题干​

给你一个字符串 date ，按 YYYY-MM-DD 格式表示一个 现行公元纪年法 日期。返回该日期是当年的第几天。

示例 1：

输入：date = "2019-01-09"
输出：9
解释：给定日期是2019年的第九天。

示例 2：

输入：date = "2019-02-10"
输出：41

提示：

• date.length == 10
• date[4] == date[7] == '-'，其他的 date[i] 都是数字
• date 表示的范围从 1900 年 1 月 1 日至 2019 年 12 月 31 日

解题思路​

• 计算当前时间与开年时间的差值，得到毫秒数差值
• 毫秒数差值再除以1天的毫秒总数（86400000ms），得到天数差值
• 天数差值再加1即可

例：计算date=2019-01-09是第几天

• 计算2019-01-09跟开年时间2019-01-01的天数差值
• 即(new Date('2019-01-09') - new Date('2019-01-01')) / 86400000 + 1
• 结果为 9

这种解法只是取巧，实际依赖于Date API，底层实现还是要考虑闰年等情况

代码​

var dayOfYear = function (date) {
    return (new Date(date) - new Date(date.slice(0, 5) + '01-01')) / 86400000 + 1;
};

1、题干​

根据 逆波兰表示法，求该后缀表达式的计算结果。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

• 整数除法只保留整数部分。
• 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：
该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

提示：

• 1 <= tokens.length <= 104
• tokens[i] 要么是一个算符（"+"、"-"、"*" 或 "/"），要么是一个在范围 [-200, 200] 内的整数

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

• 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
• 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

• 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
• 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

执行结果​

解题思路​

• 遍历tokens中的所有元素
• 遇到数字则入栈
• 遇到运算符，则取栈顶两个元素计算，结果入栈
• 遍历结束，栈中只剩运算结果

代码​

const evalRPN = tokens => {
    return tokens.reduce((acc, cur) => {
        if ('0' <= cur[cur.length - 1] && cur[cur.length - 1] <= '9') return acc.push(+cur), acc;
        const n2 = acc.pop(), n1 = acc.pop();
        if (cur === '+') return acc.push(n1 + n2), acc;
        if (cur === '-') return acc.push(n1 - n2), acc;
        if (cur === '*') return acc.push(n1 * n2), acc;
        if (cur === '/') return acc.push(Math.trunc(n1 / n2)), acc;
    }, [])[0];
};

1、题干​

根据 逆波兰表示法，求该后缀表达式的计算结果。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

• 整数除法只保留整数部分。
• 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：
该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

提示：

• 1 <= tokens.length <= 104
• tokens[i] 要么是一个算符（"+"、"-"、"*" 或 "/"），要么是一个在范围 [-200, 200] 内的整数

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

• 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
• 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

• 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
• 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

执行结果​

解题思路​

• 遍历tokens中的所有元素
• 遇到数字则入栈
• 遇到运算符，则取栈顶两个元素计算，结果入栈
• 遍历结束，栈中只剩运算结果

代码​

const evalRPN = tokens => {
    return tokens.reduce((acc, cur) => {
        if ('0' <= cur[cur.length - 1] && cur[cur.length - 1] <= '9') return acc.push(+cur), acc;
        const n2 = acc.pop(), n1 = acc.pop();
        if (cur === '+') return acc.push(n1 + n2), acc;
        if (cur === '-') return acc.push(n1 - n2), acc;
        if (cur === '*') return acc.push(n1 * n2), acc;
        if (cur === '/') return acc.push(Math.trunc(n1 / n2)), acc;
    }, [])[0];
};

1、题干​

给定一个 24 小时制（小时:分钟 "HH:MM"）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。

示例 1：

输入：timePoints = ["23:59","00:00"]
输出：1

示例 2：

输入：timePoints = ["00:00","23:59","00:00"]
输出：0

提示：

• 2 <= timePoints.length <= 2 * 104
• timePoints[i] 格式为 "HH:MM"

2、解法1-API排序​

前置处理：先排除3种特殊情况

• 鸽巢原理：timePoints.length > 1440，最小差值为0。因为分钟数最多1440种情况，如果分钟数量超过1440，则必定有重复值。
• 哈希去重：new Set(timePoints).size < timePoints.length，表示有重复值，最小差值为0。可以只用哈希去重而不用鸽巢原理，这里两个都用一是为省空间，二是为下一个限制条件提前去重。
• 相邻原理（瞎扯的）：timePoints.length > 720最小差值为1。因为分钟数最多1440种情况，如果分钟数超过一半而没有重复值，则必定有分钟数相邻。

后续步骤：把时间字符串转为分钟数，直接API排序并计算最小差值

• 将timePoints中的时间字符串HH:MM转成分钟数(0-1400)，构建出新的分钟数数组times
• 对times进行升序排序
• 在times数组末尾推入1440+times[0](最小分钟数)，使得最小时间和最大时间的差值计算常规化
• 对相邻分钟数求差值，最后返回最小差值

3、复杂度​

• 时间复杂度：$O(C)$，其中$2<=C<=720*log720$
• 空间复杂度：$O(C)$

4、代码​

var findMinDifference = function (timePoints) {
    if (timePoints.length > 1440 || new Set(timePoints).size < timePoints.length) return 0;
    if (timePoints.length > 720) return 1;

    const times = timePoints.map(p => 60 * (p[0] + p[1]) + 1 * (p[3] + p[4]));
    times.sort((a, b) => a - b).push(1440 + times[0]);

    return times.reduce((a, c, i) => i ? Math.min(a, c - times[i - 1]) : a, 1440);
};

5、执行结果​

6、解法2-计数排序​

前置处理：先排除3种特殊情况（同解法1）

• 鸽巢原理：timePoints.length > 1440，最小差值为0。因为分钟数最多1440种情况，如果分钟数量超过1440，则必定有重复值。
• 哈希去重：new Set(timePoints).size < timePoints.length，表示有重复值，最小差值为0。可以只用哈希去重而不用鸽巢原理，这里两个都用一是为省空间，二是为下一个限制条件提前去重。
• 相邻原理（瞎扯的）：timePoints.length > 720最小差值为1。因为分钟数最多1440种情况，如果分钟数超过一半而没有重复值，则必定有分钟数相邻。

后续步骤：把时间字符串转为分钟数，使用计数排序并计算最小差值

• 创建以分钟数为下标的数组 times，将 timePoints 中的时间字符串HH:MM转成分钟数，对 times 中的分钟数进行计数
• 对相邻分钟数求差值，计算出最小差值 minDiff
• 计算最小时间和最大时间的差值，并与上一步的最小值比较，最终结果是：Math.min(minDiff, 1440 + minTime - maxTime);

7、复杂度​

• 时间复杂度：$O(C)$，其中$C=1440$
• 空间复杂度：$O(C)$

8、代码​

var findMinDifference = function (timePoints) {
    if (timePoints.length > 1440 || new Set(timePoints).size < timePoints.length) return 0;
    if (timePoints.length > 720) return 1;

    const times = new Array(1440).fill(0);
    for (const p of timePoints) {
        times[60 * (p[0] + p[1]) + 1 * (p[3] + p[4])] += 1;
    }

    let minDiff = 1440, prev = -1440, minTime;
    for (let i = 0; i < times.length; i++) {
        if (minTime === undefined && times[i]) minTime = i;
        if (times[i]) minDiff = Math.min(minDiff, i - prev), prev = i;
    }

    return Math.min(minDiff, 1440 + minTime - prev);
};

9、执行结果​

1、题干​

给定一个 24 小时制（小时:分钟 "HH:MM"）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。

示例 1：

输入：timePoints = ["23:59","00:00"]
输出：1

示例 2：

输入：timePoints = ["00:00","23:59","00:00"]
输出：0

提示：

• 2 <= timePoints.length <= 2 * 104
• timePoints[i] 格式为 "HH:MM"

解法1

执行结果​

解题思路​

前置处理：先排除几种特殊情况：timePoints.length > 1440、timePoints.length > 720、new Set(timePoints).size < timePoints.length。

• timePoints.length > 1440或new Set(timePoints).size < timePoints.length，则必定有重复值，最小差值为0
• timePoints.length > 720最小差值为1。因为分钟数最多1440种情况，如果分钟数量超过一半，则必定有分钟数相邻

后续步骤：把时间字符串转为分钟数，直接排序并计算最小差值

• 将timePoints中的时间字符串HH:MM转成分钟数(0-1400)，构建出新的分钟数数组times
• 对times进行升序排序
• 在times数组末尾推入1440+times[0](最小分钟数)，使得最小时间和最大时间的差值计算常规化
• 对相邻分钟数求差值，最后返回最小差值

整体时间复杂度为$O(C)$，其中$2<=C<=720*log720$

代码​

var findMinDifference = function (timePoints) {
    if (timePoints.length > 1440 || new Set(timePoints).size < timePoints.length) return 0;
    if (timePoints.length > 720) return 1;

    const times = timePoints.map(p => p.split(':').reduce((a, c, i) => a + (+c) * (i ? 1 : 60), 0));
    times.sort((a, b) => a - b).push(1440 + times[0]);

    return times.reduce((a, c, i) => i ? Math.min(a, c - times[i - 1]) : a, 1440);
};

2、解法2​

执行结果​

解题思路​

前置处理：先排除几种特殊情况：timePoints.length > 1440、timePoints.length > 720、new Set(timePoints).size < timePoints.length。

• timePoints.length > 1440或new Set(timePoints).size < timePoints.length，则必定有重复值，最小差值为0
• timePoints.length > 720最小差值为1。因为分钟数最多1440种情况，如果分钟数量超过一半，则必定有分钟数相邻

后续步骤：把时间字符串转为分钟数，使用计数排序并计算最小差值

• 创建以分钟数为下标的数组times，将timePoints中的时间字符串HH:MM转成分钟数，对times中的分钟数进行计数
• 对相邻分钟数求差值，计算出最小差值
• 计算最小时间和最大时间的差值，并与上一步的最小值比较，最终结果是：Math.min(min, 1440 + minTime - maxTime);

整体时间复杂度为$O(C)$，其中$2<=C<=1440$

代码​

var findMinDifference = function (timePoints) {
    if (timePoints.length > 1440 || new Set(timePoints).size < timePoints.length) return 0;
    if (timePoints.length > 720) return 1;

    const times = new Array(1440).fill(0);
    for (let p of timePoints) {
        times[p.split(':').reduce((a, c, i) => a + (+c) * (i ? 1 : 60), 0)] += 1;
    }

    let min = 1440, prev = -1440, minTime;
    for (let i = 0; i < times.length; i++) {
        if (minTime === undefined && times[i]) minTime = i;
        if (times[i]) min = Math.min(min, i - prev), prev = i;
    }

    return Math.min(min, 1440 + minTime - prev);
};

1、题干​

给定一个 24 小时制（小时:分钟 "HH:MM"）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。

示例 1：

输入：timePoints = ["23:59","00:00"]
输出：1

示例 2：

输入：timePoints = ["00:00","23:59","00:00"]
输出：0

提示：

• 2 <= timePoints <= 2 * 104
• timePoints[i] 格式为 "HH:MM"

解法1

执行结果​

解题思路​

前置处理：先排除几种特殊情况：timePoints.length > 1440、timePoints.length > 720、new Set(timePoints).size < timePoints.length。

• timePoints.length > 1440或new Set(timePoints).size < timePoints.length，则必定有重复值，最小差值为0
• timePoints.length > 720最小差值为1。因为分钟数最多1440种情况，如果分钟数量超过一半，则必定有分钟数相邻

后续步骤：把时间字符串转为分钟数，直接排序并计算最小差值

• 将timePoints中的时间字符串HH:MM转成分钟数(0-1400)，构建出新的分钟数数组times
• 对times进行升序排序
• 在times数组末尾推入1440+times[0](最小分钟数)，使得最小时间和最大时间的差值计算常规化
• 对相邻分钟数求差值，最后返回最小差值

整体时间复杂度为$O(C)$，其中$2<=C<=720*log720$

代码​

var findMinDifference = function (timePoints) {
    if (timePoints.length > 1440 || new Set(timePoints).size < timePoints.length) return 0;
    if (timePoints.length > 720) return 1;

    const times = timePoints.map(p => p.split(':').reduce((a, c, i) => a + (+c) * (i ? 1 : 60), 0));
    times.sort((a, b) => a - b).push(1440 + times[0]);

    return times.reduce((a, c, i) => i ? Math.min(a, c - times[i - 1]) : a, 1440);
};

2、解法2​

执行结果​

解题思路​

前置处理：先排除几种特殊情况：timePoints.length > 1440、timePoints.length > 720、new Set(timePoints).size < timePoints.length。

• timePoints.length > 1440或new Set(timePoints).size < timePoints.length，则必定有重复值，最小差值为0
• timePoints.length > 720最小差值为1。因为分钟数最多1440种情况，如果分钟数量超过一半，则必定有分钟数相邻

后续步骤：把时间字符串转为分钟数，使用计数排序并计算最小差值

• 创建以分钟数为下标的数组times，将timePoints中的时间字符串HH:MM转成分钟数，对times中的分钟数进行计数
• 对相邻分钟数求差值，计算出最小差值
• 计算最小时间和最大时间的差值，并与上一步的最小值比较，最终结果是：Math.min(min, 1440 + minTime - maxTime);

整体时间复杂度为$O(C)$，其中$2<=C<=1440$

代码​

var findMinDifference = function (timePoints) {
    if (timePoints.length > 1440 || new Set(timePoints).size < timePoints.length) return 0;
    if (timePoints.length > 720) return 1;

    const times = new Array(1440).fill(0);
    for (let p of timePoints) {
        times[p.split(':').reduce((a, c, i) => a + (+c) * (i ? 1 : 60), 0)] += 1;
    }

    let min = 1440, prev = -1440, minTime;
    for (let i = 0; i < times.length; i++) {
        if (minTime === undefined && times[i]) minTime = i;
        if (times[i]) min = Math.min(min, i - prev), prev = i;
    }

    return Math.min(min, 1440 + minTime - prev);
};

1、题干​

有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。

示例 1:

输入: k = 5

输出: 9

1、解题思路​

一开始没想到动态规划、三指针、步进法这些方案，看了题解还是觉得这些规律或方案有点难想到。我的第一反应是：这个问题好像可以用BFS+Set去重来解决。

1.1、转换思路​

根据这个方向，实际上可以把问题转换成：已知一棵树的根是1，第一层节点是根节点与 3、5、7相乘的结果，第二层节点是第一层节点与 3、5、7相乘的结果，以此类推； 求这棵树中按广度遍历的第k个子节点的值。于是写下了这段代码：

var getKthMagicNumber = function(k) {
    let nums = [1];

    while (nums.length) {
        const set = new Set();

        for (let i = 0; i < nums.length; i++) {
            k--;
            if (!k) return nums[i];
            set.add(3 * nums[i]);
            set.add(5 * nums[i]);
            set.add(7 * nums[i]);
        }

        nums = [...set];
    }
};

1.2、测试出错​

写完之后测试出错，是因为忽略了一个很重要的条件：按顺序排列。在上述代码中用于遍历树的 nums 代表的是每一层节点，它始终是单调递增的。虽然每一层节点都单调递增，但是随着层数增加，下一层的节点却有可能小于上一层节点。

1.3、解决问题​

要解决这个问题也不难，只要把所有节点都放入 nums 中，并且保证它的单调性就OK了。

1.4、整体方案​

因此，使用BFS + Set去重 + 单调栈的方式就能解出这道题，问题的关键点有以下3个：

• 使用非递归的BFS方式进行遍历
• 使用Set去除重复的数字
• 使用单调栈保证数字升序排列

2、代码​

var getKthMagicNumber = function (k) {
    const nums = [1];
    const set = new Set();

    for (let i = 0; i < k; i++) {
        if (i + 1 === k) return nums[i];
        const arr = [3 * nums[i], 5 * nums[i], 7 * nums[i]];

        arr.forEach(n => {
            if (set.has(n)) return;
            set.add(n);

            if (n >= nums[nums.length - 1]) return nums.push(n);

            // 以上代码是常规逻辑：BFS + Set去重 
            // 以下代码是为了保证 nums 的单调性
            const arr = [];
            while (n < nums[nums.length - 1]) {
                arr.unshift(nums.pop());
            }
            nums.push(n, ...arr);
        });
    }
};