【算法】笨小猴

[NOIP2008]笨小猴_牛客题霸_牛客网

【描述】

eg1中，输入“error”

“e”出现了1次，“r”出现了3次，“o”出现了1次

最大是3，最小是1，3-1=2，2是质数，所以输出“Lucky word”和这个单词

eg2中，输入“Olympic”

所有单词都出现了1次，最大和最小都是1，1-1=0，0不是质数，输出“No Answer”和这个单词

【分析】

解法:模拟+哈希表（统计每个字符出现的个数）+试除法判断质数

思路:统计单词中每个字符出现的次数时，使用数组模拟的哈希表（大小为int[26]），然后在哈希表中找出次数的最大值和最小值

注意:考虑最小值不要考虑0，因为0代表没有出现过

找到这两个数后，将两个数相减，用得到的判断是否为质数（使用试除法）

试除法:从2开始一直循环到根号n，一个一个来除，若n%这个数==0，说明不是质数，如果所有数都模完结果都！=0，说明这是质数

【代码】

import java.util.Scanner;
public class Main
{public static boolean ispirm(int n){if(n < 2) return false;for(int i = 2;i <= Math.sqrt(n);i++){if(n % i == 0) return false;}return true;}public static void main(String[] args){Scanner in = new Scanner(System.in);char[] s = in.next().toCharArray();int[] hash = new int[26];for(int i = 0;i < s.length;i++){hash[s[i] - 'a']++; //减去字符a是为了判断下标的映射关系}int maxn = 0,minn = 1000;for(int i = 0;i < 26;i++){if(hash[i] != 0){minn = Math.min(minn, hash[i]);maxn = Math.max(maxn, hash[i]);}}if(ispirm(maxn - minn)){System.out.println("Lucky Word");System.out.println(maxn - minn);}else{System.out.println("No Answer");System.out.println(0);}}
}