1. 笨小猴题目解析与算法思想这道题目来自NOIP2008提高组的第一题题目描述非常有趣笨小猴的词汇量很小每次做英语选择题都很头疼。但它发现了一种神奇的方法——统计单词中出现次数最多和最少的字母如果两者的差是质数就认为这是个Lucky Word很可能就是正确答案。这个题目看似简单却蕴含了两个重要的算法思想哈希统计和质数判定。我们先来看题目要求的具体实现步骤输入一个单词仅包含小写字母长度小于100统计每个字母出现的次数找出出现次数最多和最少的字母注意只统计确实出现的字母计算两者的差值判断这个差值是否是质数根据判断结果输出相应信息在实际编程中我们需要特别注意几个边界情况当所有字母出现次数相同时差值为0当差值为1时如aabb和aabbc的情况当单词中只包含一种字母时如aaaaa2. 哈希统计的三种实现方式哈希统计是这道题的核心技术我们可以用多种方式来实现字母频率统计。下面介绍三种常见方法并分析它们的优缺点。2.1 数组映射法ASCII码直接映射这是最直接的方法利用字符的ASCII码作为数组下标int chNum[128] {}; // 初始化所有元素为0 for(int i 0; i strlen(s); i) { chNum[s[i]]; // 直接使用字符的ASCII码作为下标 }这种方法的特点是实现简单直观访问速度快时间复杂度O(1)浪费空间只用了a-z的部分其他位置都闲置适用于所有ASCII字符不限于小写字母2.2 数组偏移法小写字母专用针对题目明确只有小写字母的情况我们可以优化空间使用int chNum[26] {}; // 只需要26个位置 for(int i 0; i s.length(); i) { chNum[s[i]-a]; // 通过减去a的ASCII码得到0-25的索引 }这种方法的优势空间利用率高只需要26个元素的数组仍然保持O(1)的访问速度代码仍然简洁专为小写字母设计不适用于其他字符2.3 STL map容器法对于更通用的场景可以使用C的map容器#include map #include algorithm std::mapchar, int charCount; for(char c : word) { charCount[c]; }这种方法的特点是代码更加现代和通用自动处理各种字符类型内存使用更智能只存储实际出现的字符访问速度稍慢O(log n)需要包含额外头文件在实际比赛中考虑到性能和代码简洁性第二种方法数组偏移法通常是首选。但在实际工程中第三种方法可能更受欢迎因为它更灵活且不易出错。3. 质数判定的算法优化判断一个数是否为质数是本题的另一个关键点。我们先看最基本的实现然后逐步优化。3.1 基础试除法最直观的方法是试除法bool isPrime(int n) { if(n 2) return false; for(int i 2; i n; i) { if(n % i 0) return false; } return true; }这个方法的问题很明显当n很大时效率极低O(n)时间复杂度做了很多不必要的检查如偶数判断3.2 优化试除法我们可以立即进行几项优化bool isPrime(int n) { if(n 2) return false; if(n 2) return true; // 2是唯一的偶质数 if(n % 2 0) return false; // 排除其他偶数 for(int i 3; i sqrt(n); i 2) { // 只检查奇数 if(n % i 0) return false; } return true; }优化点包括单独处理2的情况排除所有偶数只需检查到√n因为如果n有大于√n的因数那么它必然有小于√n的对应因数步长改为2只检查奇数这样时间复杂度降为O(√n)对于本题的数据范围n100已经完全够用。3.3 埃拉托斯特尼筛法思想虽然对于单次判断试除法已经足够但如果我们预先知道需要判断哪些数可以使用埃氏筛法预先计算质数表const int MAX 100; bool isPrime[MAX1]; void initPrimes() { memset(isPrime, true, sizeof(isPrime)); isPrime[0] isPrime[1] false; for(int i 2; i MAX; i) { if(isPrime[i]) { for(int j i*2; j MAX; j i) { isPrime[j] false; } } } }这种方法的特点是预处理时间复杂度O(n log log n)之后每次查询都是O(1)适合需要多次查询的场景需要额外的存储空间对于本题而言由于只需要一次质数判断使用优化后的试除法更为合适。4. 完整代码实现与测试现在我们把各个部分组合起来给出两种完整的实现方案并进行测试分析。4.1 字符数组版本#include iostream #include cstring #include cmath using namespace std; bool isPrime(int n) { if(n 2) return false; if(n 2) return true; if(n % 2 0) return false; for(int i 3; i sqrt(n); i 2) { if(n % i 0) return false; } return true; } int main() { char word[100]; cin word; int counts[26] {0}; int len strlen(word); // 统计字母频率 for(int i 0; i len; i) { counts[word[i]-a]; } // 找出最大最小频率 int maxn 0, minn 100; for(int i 0; i 26; i) { if(counts[i] 0) { if(counts[i] maxn) maxn counts[i]; if(counts[i] minn) minn counts[i]; } } // 计算结果 int diff maxn - minn; if(isPrime(diff)) { cout Lucky Word endl diff; } else { cout No Answer endl 0; } return 0; }4.2 STL string版本#include iostream #include string #include algorithm #include cmath using namespace std; bool isPrime(int n) { if(n 2) return false; if(n 2) return true; if(n % 2 0) return false; for(int i 3; i*i n; i 2) { if(n % i 0) return false; } return true; } int main() { string word; cin word; int counts[26] {0}; // 统计字母频率 for(char c : word) { counts[c-a]; } // 使用STL算法找最大最小值 int maxn *max_element(counts, counts26); int minn 100; for(int n : counts) { if(n 0 n minn) { minn n; } } // 计算结果 int diff maxn - minn; if(diff 1 isPrime(diff)) { cout Lucky Word endl diff; } else { cout No Answer endl 0; } return 0; }4.3 测试用例分析我们设计几个典型测试用例来验证程序的正确性普通情况差为质数输入error解释r出现3次其他字母出现1次3-12是质数预期输出Lucky Word\n2差值不是质数输入olympic解释所有字母出现1次1-10不是质数预期输出No Answer\n0单字母单词输入aaaaa解释只有a出现5次5-50不是质数预期输出No Answer\n0差值为1非质数输入aabbc解释最大2次最小1次2-11不是质数预期输出No Answer\n0边界情况长单词输入abcdefghijklmnopqrstuvwxyz所有字母各出现1次解释1-10不是质数预期输出No Answer\n0通过这些测试用例我们可以全面验证程序的正确性和鲁棒性。在实际编程比赛中设计全面的测试用例是确保得高分的关键。
