LeetCode 650: 2 Keys Keyboard 解题与思考

LeetCode 650: 2 Keys Keyboard 解题与思考

[原题链接]

题目描述

一个键盘只有两种操作：
1、复制当前所有字符串（不能部分复制）
2、粘贴剪贴板上的字符串

当前输入为一个字符“A”，输入n（n < 1000），输出最少需要经过多少步操作，才能得到n个“A”

思路

最先注意到，既然不能部分复制，那么也就是说，假如n是个质数，那么最少就需要n次操作（1次复制，n-1次粘贴）。

那么将当前结果乘以质数n，也需要n次操作。

有了上面的结论，那么我们只需要将其分解质因数，操作数就相当于质因数之和。

算法

1、准备一个result数组，初始化为0
2、准备一个1到1000质数表，准备质数表的同时顺便准备一个哈希表，用来直接判断该数是不是质数。
3、从1开始到1000，假设当前数为i，再假设now = i;

假如now不是质数，则一直除以质数表中的数，每成功整除一次，result[i]就加这个质数。

now为质数时，result[i]加now

4、result[n]即为所求

附：准备质数表的算法如下：
1、初始：质数表prime为空，哈希表isPrime每一项都为0
2、从2开始到1000，假设当前数为i，judge = true;
3、将质数表中每个项与i取模，假如模为0，则使judge为false
4、若judge为true，则加入质数表，使isPrime[i] = 1，否则不进行任何操作。

代码 #include #include using namespace std; class Solution { vector<int> result; void create_result() { vector<int> prime, isPrime; isPrime.resize(1001); for ( int i = 2; i < 1001; i++ ) { bool judge = true; for ( auto j = prime.begin(); j != prime.end(); j++ ) { if ( i%(*j) == 0 ) { judge = false; break; } } if ( judge ) { isPrime[i] = 1; prime.push_back(i); } } result.push_back(0); result.push_back(0); for ( int i = 2; i < 1001; i++ ) { int step = 0; int now = i; while ( isPrime[now] != 1 ) { for ( auto j = prime.begin(); j != prime.end(); j++) { if ( now % (*j) == 0 ) { step += *j; now = now / (*j); break; } } } step += now; result.push_back(step); } return; } public: int minSteps(int n) { if ( result.size() == 0 ) create_result(); return result[n]; } }; 思考

注意一下在1这个数的处理上就行了