d107 - NOIP 2008 1.笨小猴
題目描述
題目要求判斷給定的單詞是否為 "Lucky Word"。一個單詞被視為 Lucky Word 如果其出現次數最多的字母與出現次數最少字母的差值是一個質數。輸出包含 "Lucky Word" 或 "No Answer" 以及差值或 0。
解題思路
程式碼首先統計每個字母在輸入單詞中出現的次數，使用一個大小為 26 的整數陣列 b 儲存。然後，程式碼找到出現次數最多的字母 (max) 和出現次數最少的字母 (min)。接著，計算 max - min 的值。最後，程式碼檢查 max - min 是否為質數（2, 3, 5, 7 或其他質數）。如果它是質數，則輸出 "Lucky Word" 和 max - min 的值；否則，輸出 "No Answer" 和 0。
複雜度分析
- 時間複雜度: O(n)，其中 n 是輸入單詞的長度。程式碼需要遍歷單詞一次來統計字母出現次數，然後遍歷 26 個字母來找到最大和最小值。
- 空間複雜度: O(1)。程式碼使用一個固定大小的陣列
b(大小為 26) 來儲存字母出現次數，因此空間複雜度是常數。
程式碼
#include <iostream>
#include <string>
using namespace std;
int main(){
string a;
while(cin >> a){
int b[26]={0},max=0,min=100;
for(int i=0;i<a.length();i++){
b[a[i]-97]++;
}
for(int i=0;i<26;i++){
if(b[i]>max)
max=b[i];
if(b[i]<min&&b[i]!=0)
min=b[i];
}
max-=min;
if(max==2||max==3||max==5||max==7)
cout << "Lucky Word\n" << max;
else if(max%2==0||max%3==0||max%5==0||max%7==0||max==1)
cout << "No Answer\n0" ;
else
cout << "Lucky Word\n" << max;
}
}