蓝桥杯练习题十四 - 次数差（c++）

墨蓝 2023-09-30 15:52 24阅读 0赞

> 题目如下

问题描述  
x星球有26只球队，分别用 a ~ z 的26个字母代表。他们总是不停地比赛。  
在某一赛段，哪个球队获胜了，就记录下代表它的字母，这样就形成一个长长的串。  
国王总是询问：获胜次数最多的和获胜次数最少的有多大差距？  
（当然，他不关心那些一次也没获胜的，认为他们在怠工罢了）  
输入格式  
一个串，表示球队获胜情况（保证串的长度<1000）  
输出格式  
要求输出一个数字，表示出现次数最多的字母比出现次数最少的字母多了多少次。  
样例输入1  
abaabcaa  
样例输出1  
4  
提示  
a 出现 5 次，最多；c 出现1次，最少。  
5 - 1 = 4  
样例输入2（这里貌似题目写错了，输出应为4）  
bbccccddaaaacccc  
样例输出2  
6  
以下选项错误的是？

> A.

int cnt[1001];
    int main()
    {
        string s;
        cin >> s;
        int max1 = -1, min1 = 1001;
        for (int i = 0; i < s.length(); i++)
        {
            for (int j = 0; j <= s.length(); j++)
            {
                if (s[i] == s[j])
                {
                    cnt[i]++;
                }
            }
        }
        for (int i = 0; i < s.length(); i++)
        {
            if (cnt[i] > max1)
            {
                max1 = cnt[i];
            }
            if (cnt[i] < min1)
            {
                min1 = cnt[i];
            }
        }
        cout << max1 - min1 << endl;
        return 0;
    }

> B.

int main()
    {
        char s[1000];
        scanf("%s", &s);
        int len = strlen(s);
        int helper[256] = {0};
        int max = 0, min = len;
        for (int i = 0; i < len; i++)
        {
            helper[s[i]]++;
        }
        for (int i = 0; i < 256; i++)
        {
            if (helper[i] > max)
            {
                max = helper[i];
            }
            if (helper[i] < min && helper[i] != 0)
            {
                min = helper[i];
            }
        }
        printf("%d\n", max - min);
        return 0;
    }

> C.

const int N = 1010;
    int cnt[26];
    char a[N];
    char b[27] = {"abcdefghijklmnopqrstuvwxyz"};
    
    int main()
    {
        cin >> a;
        for (int i = 0; i < 26; i++)
            for (int j = 0; a[j]; j++)
                if (b[i] == a[j + 1])
                    cnt[i]++;
    
        int maxn = 0, minn = 1000;
        for (int i = 0; i <= 26; i++)
            if (cnt[i])
            {
                maxn = max(maxn, cnt[i]);
                minn = min(minn, cnt[i]);
            }
    
        cout << maxn - minn << endl;
        return 0;
    }

> D.

int a[26];
    
    int main()
    {
        string str;
        cin >> str;
        for (int i = 0; i < str.length(); i++)
        {
            a[str[i] - 'a']++;
        }
        sort(a, a + 26);
        for (int i = 0; i < 26; i++)
        {
            if (a[i] != 0)
            {
                cout << a[25] - a[i] << endl;
                break;
            }
        }
        return 0;
    }

> 题目解析

惯例先吐槽这类选择题，太折磨人了，还是那句话，做对一道题很容易，难的是用多种方法做出同一道题。此选项在官方题库中会变换，以本博客中为例。

题目大家也看完了，如果是你，你会怎么做？先来说说博主的思路吧：

*  一大串字母组成的字符串，里面有很多字母是重复的，这是关键；
 *  找出里面出现次数最多的字母和出现次数最少的字母，出现0次的不算；
 *  用出现次数最多的字母减去出现次数最少的字母得到的值就是我要的那个数字；
 *  题目中没有说要知道最大的字母和最小的字母，这也是个突破点。

那么问题来了，怎么找到出现次数最大和最小的字母？

如果是我，会将a～z的字母列出来，分别计算每个字母出现的次数，再通过冒泡排序法，找出最大和最小的两个数字，特别强调，这里一定要忽略出现0次的数字，最大数减最小书就得到了这个值。

这样一说，是不是就觉得不难了？接着我们看看四个选项都是怎么做的：

A选项：

好巧不巧，恰好是和博主刚刚说的方法是一样的，在寻找最大最小数时略有差异，它是先计算出每个字母出现的次数，再通过比较的方式取出最大值和最小值，这也给了博主启发，却是这种方式要比冒泡或者选择排序这两种方式的效率要高，因为少了个内部for循环，计算的次数就少了。

B选项：

博主发现B选项和A选项有异曲同工之妙，首先是找出每个字母出现的次数，方法却略微不同，这里采用的是多维数组的形式，for循环长度是字符串的长度，s\[i\]是i位置的字符，其随i的自增，若相同字符，helper\[x\]就+1，这样就获得了每个字符出现的次数的一个数组，接下来计算出现次数最多的字符和最少的字符就可以了。计算的方式和A选项是一样的。

就目前AB两个选项而言，B选项的效率明显是要高于A选项的，这个不接受反驳。

C选项：

大体看起来计算方法是没错的，当看到第一个for循环的时候还是发现了问题，if怕断中b\[i\]==a\[j+1\]似乎是有问题的，第一次出现的字符我们默认是一次，这里直接忽略了第一位，那最大值不变，但是总值要小1，最小值很可能就改变了，本来出现一次的是最小值，结果直接变成了0，最小值变化，结果是有可能和原值一样的，但存在一定的概率，我们不敢赌每次都一样，所以C一定是错误的。

D选项：

到C我们就可以结束了，不过我们还是继续看下D选项是怎么做的。打眼一看，流程没错，细看过程，不懂的点在a\[str\[i\]-'a'\]，这个是c语法，其实博主对c的一些语法也不是特别懂，那我们来猜下这里的意思，str\[i\]是一个字符，字符减去初始字符'a'，那就是0，这里我们就得到每个字符代表的0-25的位置。

有人会说，B选项里不是也有个多维数组吗？那里面似乎没有这么做，直接用字符代表位置啊，啥情况？那是因为B里直接用字符，使用的是BASIC码表的东西，其中ASCII码范围0-255，所以B选项helper大小才是256。如果说的不对，欢迎指正。

> 总结

终于结束了，这道题不是很难，但是博主对这种选项题真是头疼，前面看过的一些比较简单的题目有的也跳过去了，有些有意义的就和大家做个分享，题目多是对基础算法的考察，做程序，基础还是要做好的，建议大家有时间还是要学学c/c++，基础的东西往往兼容性更高，使用的范围也很广，做一些深入研究的时候很有使用价值，特别是偏底层的一些东西，相信你已经多多少少接触到了，不妨现在就开始学习吧。