从Leetcode 每日一题练习继续讨论：
650. 两个键的键盘
650. 2 Keys Keyboard
题解
本题题目有点幽默, 一个经典的程序员梗, 程序员键盘上只需要两个键就够了, 一个复制, 一个粘贴. 本题正是一个这样的键盘.
回归题目本身, 第一步可以发现如果n能被一个正整数a整除, 则可以通过将n/a个数的’A’粘贴a-1次得到n个’A’, 加上复制操作总共需要的操作次数为a次. 则可以发现只要将n分解成几个因子相乘, 将这几个因子相加就是一个得到n的操作总数. 接下来的问题就是如何分解能让这个操作总数最小, 这里很容易想到将n分解为质因数, 因为质因数是比较特殊的因数, 这是我们的猜测, 可以通过简单的证明说明分解成质因数一定不大于分解成合数因数的操作次数, 只需证明如果a,b均大于1则a+b(质因数的操作总数)<=a*b(合数因数的操作总数).
首先，我们可以考虑 ab - (a+b)，如果能证明这个差值非负，那么就证明了 ab ≥ a+b。
a*b - (a+b) = ab - a - b
= ab - a - b + 1 - 1
= (a-1)(b-1) - 1
因为a和b都是大于1的正整数，所以 a-1 ≥ 1 且 b-1 ≥ 1
因此，(a-1)(b-1) ≥ 1
所以，(a-1)(b-1) - 1 ≥ 0
这就证明了 ab - (a+b) ≥ 0，即 ab ≥ a+b
由此我们得到只要将n分解成质因数相乘再将这些因子相加就能得到最少的操作总数. 如何将n分解成质因数相乘呢, 只需从2开始不断用n试除质因子, 当无法整除时将质因子加一(不用担心可以被合数整除, 如如果一个数能被6整除, 则从2递增到3时一定已经将这个数除尽了), 直到因子大于等于n的平方根即可. 每次分解出一个质因子都将其加和到操作总数上即得最终的答案.
代码
func minSteps(n int) int {
if n == 1{
return 0
}
d := 2
result := 0
for n > 1 {
for n%d == 0 {
result += d
n /= d
}
d++
if d*d > n {
if n > 1 {
result += n
}
break
}
}
return result
}