统计字符串每个字符出现频率

输入一个字符串，统计每个字符的出现频率，然后判定最大频率与最小频率的差值 cnt：
如果 cnt 是质数，则输出 "Lucky Word" 和 差值；
否则输出 "No Answer" 和 0。

2. #include <bits/stdc++.h>
3. using namespace std;
5. bool valid(int n)//判断是否为质数
6. {
7.   if (n <= 1) return false;
8.     if (n == 2) return true;
9.     if (n % 2 == 0) return false;
11.     int sqrtN = static_cast<int>(sqrt(n));
12.     for (int i = 3; i <= sqrtN; i += 2) {
13.         if (n % i == 0) return false;
14.     }
16.     return true;
17. }
19. int main()
20. {
21.   unordered_map<char,int> fre;
23.   string str;
24.   cin >> str;
26.   for(char c : str)
27.   {
28.     // if (islower(c))
29.     fre[c]++;
30.   }
32.   int maxx = INT_MIN; //初始化
33.   int minn = INT_MAX;
35.   for(auto & [ _ ,fret ] : fre)
36.   {
37.     if(fret > maxx)
38.     maxx = max(fret,maxx);
40.     if(fret <minn)
41.     minn = min(fret,minn);
42.   }
43. //第二种写法
44.    for(auto & pairr : fre)
45.   {
46.     if(pairr.second > maxx)
47.     maxx = max(pairr.second , maxx);
49.     if(pairr.second < minn)
50.     minn = min(pairr.second , minn);
51.   }
53.   int cnt = maxx - minn;
54.   
55.   if(valid(cnt))
56.   {
57.     cout << "Lucky Word"<<endl;
58.     cout << cnt << endl;
59.   }
60.   else
61.   {
62.     cout << "No Answer"<<endl;
63.     cout << 0 << endl;
64.   }
65.   return 0;
66. }

复制代码

2. bool valid(int n){
3.   if(n < 2){
4.     return false;  // 小于2的数不是质数
5.   } else {
6.     for(int i = 2; i * i <= n; i++){
7.       if(n % i == 0){
8.         return false;  // 有其他因数，不是质数
9.       }
10.     }
11.   }
12.   return true;  // 没有找到因数，是质数
13. }

复制代码

 

2. bool valid(int n)//判断是否为质数
3. {
4.   if (n <= 1) return false;
5.     if (n == 2) return true;
6.     if (n % 2 == 0) return false;
8.     int sqrtN = static_cast<int>(sqrt(n));
9.     for (int i = 3; i <= sqrtN; i += 2) {
10.         if (n % i == 0) return false;
11.     }
13.     return true;
14. }

复制代码

质数
质数（英文名：Prime number）又称素数，是指在大于1的天然数中，除了1和它自己以外不再有其他因数的天然数。
质数又称素数。 一个大于1的天然数，除了1和它自身外，不能被其他天然数整除的数叫做质数；否则称为合数（规定1既不是质数也不是合数）。

2. int sqrtN = (int)sqrt(n);  // C 风格
3. int sqrtN = static_cast<int>(sqrt(n));  // C++ 风格（更推荐）

复制代码

static_cast<int>(sqrt(n))是C++ 的 显式范例转换（范例安全）

2. int sqrtN = static_cast<int>(sqrt(n));
3. for (int i = 3; i <= sqrtN; i += 2) {
4.     if (n % i == 0) return false;
5. }

复制代码

原理：

如果一个数 n 可以被某个数 i 整除（i * j == n），那肯定有一对因数 (i, j)。

•         如果 i > sqrt(n)，那么对应的 j 肯定是 < sqrt(n)
  
•         以是检查到 sqrt(n) 就能覆盖全部大概的因数对，凌驾了就重复了。
  

举个例子：

判定 n = 49 是否为质数：

•         它的因数对是 (1,49) 和 (7,7)
  
•         凌驾 sqrt(49)=7 再查着实没意义了
  

为什么只查奇数：i += 2？

•         由于偶数除了 2 自己，不大概是质数
  
•         以是我们在函数开头已经判定了 if (n % 2 == 0) return false;，后面只查奇数更快！
  

527