数学

一个十位数，每一位的数字都不相同，且必须满足以下条件，求该十位数

阮一峰老师在微博发了一个问题（原题见此），一个十位数，每一位的数字都不相同，且必须满足以下条件，求该十位数。

一个十位数，每一位的数字都不相同，且必须满足以下条件，求该十位数。

a 可被1整除

ab 可被2整除

abc 可被3整除

abcd 可被4整除

abcde 可被5整除

abcdef 可被6整除

abcdefg 可被7整除

abcdefgh 可被8整除

abcdefghi 可被9整除

abcdefghij 可被10整除

对于不懂算法的我来说，这只能靠暴力求解来解决。

暴力求解一点也不难：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function find (start, end) {
  const d1 = new Date()
  console.log('==START==', d1.toJSON())

  for (let i = start; i < end; i++) {
    const num = i.toString()

    if (Number(num.substring(0, 2)) % 2 !== 0) continue
    if (Number(num.substring(0, 3)) % 3 !== 0) continue
    if (Number(num.substring(0, 4)) % 4 !== 0) continue
    if (Number(num.substring(0, 5)) % 5 !== 0) continue
    if (Number(num.substring(0, 6)) % 6 !== 0) continue
    if (Number(num.substring(0, 7)) % 7 !== 0) continue
    if (Number(num.substring(0, 8)) % 8 !== 0) continue
    if (Number(num.substring(0, 9)) % 9 !== 0) continue
    if (Number(num.substring(0, 10)) % 10 !== 0) continue

    const s = new Set()
    for (let j = 0; i < 10; j++) i.set(num.substring(j, j + 1))
    if (s.size !== 10) continue

    console.log(num)
  }

  const d2 = new Date()
  console.log('==END==', d2.toJSON())
  console.log('==COST==', (d2 - d1) / 1000)
}

find(1000000000, 1100000000)

我的 MacBook Pro 2015 款，执行上面从 1000000000 ~ 1100000000 （约所有循环的1%+）就要 25 秒左右。要想所有数据都跑一遍（有可能有多个解），估计怎么也要半小时。这个时间是绝对不能忍的。

很快就发现问题了，这题其实很明显能看出，第 10 位是 0，第 5 位是5。

可是第 5 位是 5 不会用，那先把最后一位是 0 优化下，第一个数还是 1000000000，循环以 10 递增即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function find (start, end) {
  const d1 = new Date()
  console.log('==START==', d1.toJSON())

  for (let i = start; i < end; i = i + 10) {
    const num = i.toString()

    if (Number(num.substring(0, 2)) % 2 !== 0) continue
    if (Number(num.substring(0, 3)) % 3 !== 0) continue
    if (Number(num.substring(0, 4)) % 4 !== 0) continue
    if (Number(num.substring(0, 5)) % 5 !== 0) continue
    if (Number(num.substring(0, 6)) % 6 !== 0) continue
    if (Number(num.substring(0, 7)) % 7 !== 0) continue
    if (Number(num.substring(0, 8)) % 8 !== 0) continue
    if (Number(num.substring(0, 9)) % 9 !== 0) continue

    const s = new Set()
    for (let j = 0; j < 10; j++) s.add(num.substring(j, j + 1))
    if (s.size !== 10) continue

    console.log(num)
  }

  const d2 = new Date()
  console.log('==END==', d2.toJSON())
  console.log('==COST==', (d2 - d1) / 1000)
}

find(1000000000, 1100000000)

果真，效率提升 10 倍！从 1000000000 ~ 1100000000 （约所有循环的1%+）就要 2 秒多就行了。从 1000000000 ~ 2000000000 （约所有循环的10%+）现在只需要 20 多秒。全部算下来估计不到 4 分钟。

我感觉，循环里面上来先数字转字符串，再进行截取，这个效率应该不是很高，但是自己想了很久，也没想出来好的数字截取方案，不过还是能凑合处理解决下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function find (start, end) {
  const d1 = new Date()
  console.log('==START==', d1.toJSON())

  for (let i = start; i < end; i = i + 10) {
    const num = i.toString()
    if (((i / 100000000) | 0) % 2 !== 0) continue
    if (((i / 10000000) | 0) % 3 !== 0) continue
    if (((i / 1000000) | 0) % 4 !== 0) continue
    if (((i / 100000) | 0) % 5 !== 0) continue
    if (((i / 10000) | 0) % 6 !== 0) continue
    if (((i / 1000) | 0) % 7 !== 0) continue
    if (((i / 100) | 0) % 8 !== 0) continue
    if (((i / 10) | 0) % 9 !== 0) continue

    const s = new Set()

    for (let j = 0; j < 10; j++) s.add(num.substring(j, j + 1))
    if (s.size !== 10) continue

    console.log(num)
  }

  const d2 = new Date()
  console.log('==END==', d2.toJSON())
  console.log('==COST==', (d2 - d1) / 1000)
}

find(1000000000, 2000000000)

思路是：先把数字进行除法，之后 |0 取得整数部分即可。

这么处理后，从 1000000000 ~ 2000000000 （约所有循环的10%+）现在只需要 10 多秒了！又提升了一倍！这个写法全算一遍也就 2 分钟不到了。

其实这个方法还不太好，因为每次 for 循环，上来第一行都要对 i.toString()，这个有浪费。继续优化下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function find (start, end) {
  const d1 = new Date()
  console.log('==START==', d1.toJSON())

  for (let i = start; i < end; i = i + 10) {
    if (((i / 100000000) | 0) % 2 !== 0) continue
    if (((i / 10000000) | 0) % 3 !== 0) continue
    if (((i / 1000000) | 0) % 4 !== 0) continue
    if (((i / 100000) | 0) % 5 !== 0) continue
    if (((i / 10000) | 0) % 6 !== 0) continue
    if (((i / 1000) | 0) % 7 !== 0) continue
    if (((i / 100) | 0) % 8 !== 0) continue
    if (((i / 10) | 0) % 9 !== 0) continue

    const s = new Set()
    for (let j = 0; j < 10; j++) s.add(i.toString().substring(j, j + 1))
    if (s.size !== 10) continue

    console.log(i)
  }

  const d2 = new Date()
  console.log('==END==', d2.toJSON())
  console.log('==COST==', (d2 - d1) / 1000)
}

find(1000000000, 2000000000)

从 1000000000 ~ 2000000000 （约所有循环的10%+）现在只需要 0.5 秒了！

从 1000000000 ~ 10000000000 现在只需要 7.2 秒！

看来 toString 很伤性能啊。

这个成绩可以轻松解出答案：3816547290。

继续努力优化下试试。我记得创建变量是伤性能的，所以把 Set 放在外层，不过缺点是 每次要 clear：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function find (start, end) {
  const d1 = new Date()
  console.log('==START==', d1.toJSON())

  const s = new Set()

  for (let i = start; i < end; i = i + 10) {
    if (((i / 100000000) | 0) % 2 !== 0) continue
    if (((i / 10000000) | 0) % 3 !== 0) continue
    if (((i / 1000000) | 0) % 4 !== 0) continue
    if (((i / 100000) | 0) % 5 !== 0) continue
    if (((i / 10000) | 0) % 6 !== 0) continue
    if (((i / 1000) | 0) % 7 !== 0) continue
    if (((i / 100) | 0) % 8 !== 0) continue
    if (((i / 10) | 0) % 9 !== 0) continue

    s.clear()
    for (let j = 0; j < 10; j++) s.add(i.toString().substring(j, j + 1))
    if (s.size !== 10) continue
    console.log(i)
  }

  const d2 = new Date()
  console.log('==END==', d2.toJSON())
  console.log('==COST==', (d2 - d1) / 1000)
}

find(1000000000, 10000000000)

经过尝试，从 1000000000 ~ 10000000000 还是需要将近 7.2 秒，基本上没有提升。

之所以没有性能提升，我认为从第一层循环中，已经过滤了大量无效数据，最终走到第二层循环的数据很少了，所以提升基本上肉眼不可见。

后续我也尝试对第二层循环进行多次调整，比如把 i.toString().substring() 改成先数组切割，之后数组写入 set 中。但由于上面刚刚说到的，由于进入第二循环的数据已经很少了，所以怎么优化基本上都不可见明显效果。

最后我也尝试把 continue 去掉，换成最常规的 if：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function find (start, end) {
  const d1 = new Date()
  console.log('==START==', d1.toJSON())

  const s = new Set()

  for (let i = start; i < end; i = i + 10) {
    if (
      (((i / 100000000) | 0) % 2 === 0) &&
      (((i / 10000000) | 0) % 3 === 0) &&
      (((i / 1000000) | 0) % 4 === 0) &&
      (((i / 100000) | 0) % 5 === 0) &&
      (((i / 10000) | 0) % 6 === 0) &&
      (((i / 1000) | 0) % 7 === 0) &&
      (((i / 100) | 0) % 8 === 0) &&
      (((i / 10) | 0) % 9 === 0)
    ) {
      s.clear()
      for (let j = 0; j < 10; j++) s.add(i.toString().substring(j, j + 1))
      if (s.size === 10) console.log(i)
    }
  }

  const d2 = new Date()
  console.log('==END==', d2.toJSON())
  console.log('==COST==', (d2 - d1) / 1000)
}

find(1000000000, 10000000000)

测试发现没有任何优化效果。我一直以为 continue 性能差，现在看来完全多虑了。

除了人工优化了下第一层循环的步进，其余 100% 都是暴力求解，我只能做到 7.2 秒左右的成绩了。其实主要是不会算法，只能暴力求解。

从 1000000000 ~ 10000000000，用时 7.2 秒。

相当于 (10000000000-1000000000) / 7.2 = 1250000000

也就是每秒遍历 12.5 亿个数字，这么一看感觉好快啊。

小结

for 循环次数越少，速度越快。即便循环 100 次，其中 90 次进入循环第一行都被断掉了，也远不如只循环 10 次。

for 循环，里面写 continue 并不会影响性能。

循环能直接用 Number 数字类型就不要转 String 字符串。字符串的 substring toString 非常伤性能。

尽可能少的创建变量，尤其是再循环里面。（难道是反复 alloc free 内存造成的？）

–END–