网络喷子键盘侠的输入框上已经键入了一句喷人的话,现在他的键盘上只有两个键可用
C:拷贝,可以把输入框的所有内容拷贝下来
P:粘贴,可以在输入框结尾处添加刚刚拷贝的所有内容
请问他至少需要按多少次,可以把输入框里的话复制N次发送出去呢?
样例
如果不可能,则返回{-1, “”}。
我们保证 N >= 0
1 2 3 4 5 6 7 8 9 10 11
| N = 0 做不到,返回 -1, "" N = 1 0次: N = 2 2次:CP N = 12 7次:CPCPCPP
|
分析
有的同学可能会误以为这是一个动态规划的题目,
可能是因为有一道题叫做“矩阵乘法”,这个题目相比来说很类似。
实际上因为它可以完全用贪心法,所以没有必要动态规划。
直接采用因式分解,然后把因子加起来就可以了。
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| func KeyPress(N int) (int, string) { var seq string if N <= 0 { return -1, seq } var result = 0 for i := 2; i <= N; { if N%i == 0 { N = N / i result += i seq = seq + "C" for j := 1; j < i; j++ { seq = seq + "P" } } else { i++ } } return result, seq }
|