LeetCode 650: 2 Keys Keyboard 解題與思考

[原題鏈接]

題目描述

一個(gè)鍵盤只有兩種操作：
1、復(fù)制當(dāng)前所有字符串（不能部分復(fù)制）
2、粘貼剪貼板上的字符串

當(dāng)前輸入為一個(gè)字符“A”，輸入n（n < 1000），輸出最少需要經(jīng)過多少步操作，才能得到n個(gè)“A”

思路

最先注意到，既然不能部分復(fù)制，那么也就是說，假如n是個(gè)質(zhì)數(shù)，那么最少就需要n次操作（1次復(fù)制，n-1次粘貼）。

那么將當(dāng)前結(jié)果乘以質(zhì)數(shù)n，也需要n次操作。

有了上面的結(jié)論，那么我們只需要將其分解質(zhì)因數(shù)，操作數(shù)就相當(dāng)于質(zhì)因數(shù)之和。

算法

1、準(zhǔn)備一個(gè)result數(shù)組，初始化為0
2、準(zhǔn)備一個(gè)1到1000質(zhì)數(shù)表，準(zhǔn)備質(zhì)數(shù)表的同時(shí)順便準(zhǔn)備一個(gè)哈希表，用來直接判斷該數(shù)是不是質(zhì)數(shù)。
3、從1開始到1000，假設(shè)當(dāng)前數(shù)為i，再假設(shè)now = i;

假如now不是質(zhì)數(shù)，則一直除以質(zhì)數(shù)表中的數(shù)，每成功整除一次，result[i]就加這個(gè)質(zhì)數(shù)。

now為質(zhì)數(shù)時(shí)，result[i]加now

4、result[n]即為所求

附：準(zhǔn)備質(zhì)數(shù)表的算法如下：
1、初始：質(zhì)數(shù)表prime為空，哈希表isPrime每一項(xiàng)都為0
2、從2開始到1000，假設(shè)當(dāng)前數(shù)為i，judge = true;
3、將質(zhì)數(shù)表中每個(gè)項(xiàng)與i取模，假如模為0，則使judge為false
4、若judge為true，則加入質(zhì)數(shù)表，使isPrime[i] = 1，否則不進(jìn)行任何操作。

代碼 #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這個(gè)數(shù)的處理上就行了