前言
从三月份到现在，大大小小笔试了十几家公司（主要是因为一直solo code，没人内推），然后也能感觉到自己的进步把。从编程题只能ac一题到后来的ak。今天面腾讯的时候，面试官还一度怀疑我专门去刷了腾讯的笔试题。因此，我想开始做算法，也就是大家都知道的leetcode啦。其实真的蛮有意思的，建议前途未卜的在校大学生都可以去试一下。。算法的确有他独特的魅力。这个专栏我打算加进一块是，把我见到的有意思的算法题给拿出来，跟大家分享交流。
题目
input: n
output: 一个可以被1到n的所有整数整除的最小整数,
由于整数过大，输出这个整数对987654321取余的结果
这里给同学提个醒。。再往下直接就是我写得解题思路了，希望大家可以先自己思考一下这个问题。
解题思路
我这里先给出一个，我跟别人交流之后，感觉是可以继续发展的想法：
- 先求
1和2的最小公倍数a1， 然后求a1和3的最小公倍数a2，依次类推最后求出的就是一个可以被所有数整除的最小整数
但是这个方法最大的问题就在于，我们求两个数的最小公倍数的时候，用到的方法非常麻烦，具体大家可以某度质因数分解之类的方法。
然后我在做这个题的时候，其实也用到了类似质因数分解，只是其实我们可以更好的利用到因数这一个特性。
我用一个比较小的例子来说明我的思想吧：
下文题到的因数列表的意思是，恰好能够构成整数的因数的集合
有同学说我因数列表没说明白，那我在这举个例子，12 = 2 * 3 * 2,那么[2, 3, 2]就是他的因数列表
-
n = 1的时候，这个最大整数要可以被1整除就行，那么这个数就是1，因数列表是[1] -
n = 2的时候，这个最大整数要可以被1, 2整除，那么这个数就是1 * 2 = 2,因数列表是[1, 2] -
n = 3的时候，这个最大整数要可以被1, 2, 3整除，那么这个数就是1 * 2 * 3 = 6，因数列表是[1, 2, 3]
看到这里其实还看不出什么，但是接下来就是重头戏了
-
n = 4的时候，这个最大整数要可以被1, 2, 3, 4整除，这时候我们发现，n = 3的时候求出来的6包含了因数[2, 3]，而2又恰好是4的因数，那么其实可以发现，这个新的最小整数只要在旧的最小整数6的基础上增添一个新的因数，让4也可以在最小整数的因数列表里面找到所有的因数，那么也就是，我们在原本的因数列表里加入一个新的因数4 / 2 = 2(4 / 2 中的 2 来自 6 的因数列表里的 2)，也就是新的因数列表是[1, 2, 3, 2]，此时的最小整数是1 * 2 * 3 * 2 = 12
看到这里，我相信大家已经可以明白我的思路了，解决问题的方法就是，求输入为n的最小整数，也就是要在输入为n-1的最小整数的因数列表里面找出n的因数，然后把最后没有找出来的因数给加入到因数列表里面。
而寻找因数的过程可以归结如下：
-
list// 因数列表，index// 因数列表下标索引，用于循环 -
k = n / list[index], 如果k是个整数，说明list[index]是n的一个因数，那么n = k，也就是说，找到了一个因数之后，我们下次要找因数的n就没有那么大了，毕竟已经有一个因数了。 - 如果
k不是一个整数，说明list[index]不是n的因数，不做任何处理 index++
好了，现在我们可以求出输入为n的时候的因数列表了。
一个新的问题来了，计算机没办法表示出这个因数列表的乘积，我们要怎么求出它对987654321的余数呢。答案就是 ((a % c) * (b % c)) % c = (a * b) % c。在这个题里，也就是，我们不断用result乘因数列表里的数的时候，我们就result = result % 987654321，可以在保持结果不变的情况下减少result的值，乘完因数列表里所有的数后的result就是结果
代码
我一个切图仔。。还是js写得舒服一点，用其他语言实现的话，其实理解了我的解题思路应该不难。（by the way）动态数组是真的好用嘻嘻嘻。
function solution (n) {
const list = [] // 因数列表
let result = 1 // 结果
for (let i = 1; i <= n; i++) { // 依次在不同的n值时的list添加新的因数
let newFactor = i // 这个新的因数初始为i
// 在list中寻找i的因数,并且减小newFactor
for(let j = list.length; j >= 0; j--) {
if (newFactor === 1) {
// 此时的i可以被list中若干个数相乘得到
break
}
let item = list[j]
if (newFactor % item === 0) { // 如果这个数可以被list[j]整除
newFactor /= item // 缩小newFactor
}
}
if (newFactor !== 1) { // 如果这个因数还有剩余部分
list.push(newFactor) // 把剩余部分添加进list
// 并且把因数乘入result
result = (result * newFactor) % 987654321
}
}
return result
}
附上测试图把：
那么这个算法题就到这了，如果大家又什么好的想法或者我的有什么问题，欢迎在讨论区和我交流（虽然我知道你们都不想看这又臭又长的）
更好的解法
在评论区里，@JMC_给出了效率更高的解法，本来想补上他的思路的，发现我的文笔有限，说不清楚，大家可以看他的代码JMC_的解法C++版
JMC_的原话是：
刚测试了一下你的代码，发现你这个时间复杂度是O(n*n)。其实算1-n的最小公倍数的话，只要算1-n中的质数的贡献就可以了，每个质数p的贡献就是p的最大幂（小于等于n ），然后将所有的贡献累乘起来就是答案了，这样时间复杂度就会降成O(n)。
我用javascript重写了一下，大家可以用node运行一下，然后自己模仿程序运行的过程应该就可以理解了。
function work (n) {
const isprime = [] // 判断一个数是否是质数
const prime = [] // 质数列表
let result = 1
for (let i = 2; i <= n; i++) {// 一开始我们认为每一个数都可能是自身的幂
isprime[i] = i
}
for (let i = 2; i <= n; i++) { //线性筛
if (isprime[i] == i) { //i为质数
prime.push(i)
result = (result * i) % 987654321
}
for (let j = 0; i * prime[j] <= n; j++) { // 遍历质数列表
if (isprime[i] === prime[j]) { // i * prime[j]为质数的幂
isprime[i*prime[j]] = prime[j]
result = (result * prime[j]) % 987654321
}
else isprime[i * prime[j]] = 0
if (i % prime[j] == 0) break
}
console.log(i)
console.log('isprime')
console.log(isprime)
console.log('prime')
console.log(prime)
console.log('\n\n\n')
}
return result
}