华为机试HJ27 查找兄弟单词
首先看一下题
描述
定义一个单词的“兄弟单词”为：交换该单词字母顺序（注：可以交换任意次），而不添加、删除、修改原有的字母就能生成的单词。
兄弟单词要求和原来的单词不同。例如： ab 和 ba 是兄弟单词。 ab 和 ab 则不是兄弟单词。
现在给定你 n 个单词，另外再给你一个单词 x ，让你寻找 x 的兄弟单词里，按字典序排列后的第 k 个单词是什么？
注意：字典中可能有重复单词。
数据范围： 1≤n≤1000 ，输入的字符串长度满足 1≤len(str)≤10 ， 1≤k<n
输入描述：
输入只有一行。 先输入字典中单词的个数n，再输入n个单词作为字典单词。 然后输入一个单词x 最后后输入一个整数k
输出描述：
第一行输出查找到x的兄弟单词的个数m 第二行输出查找到的按照字典顺序排序后的第k个兄弟单词，没有符合第k个的话则不用输出。
示例1
输入：
3 abc bca cab abc 1输出：
2 bca示例2
输入：
6 cab ad abcd cba abc bca abc 1输出：
3 bca说明：
abc的兄弟单词有cab cba bca，所以输出3 经字典序排列后，变为bca cab cba，所以第1个字典序兄弟单词为bca
一、问题分析
首先读题，仔细看描述中的内容，发现需求是
1.定义一个单词的“兄弟单词”
2.交换该单词字母顺序
3.可以交换任意次
4.而不添加、删除、修改原有的字母就能生成新的单词
5.兄弟单词要求和原来的单词不同
6.现在给定你n个单词，另外再给你一个单词x
7.让你寻找x的兄弟单词里
8.按字典序排列后的第k个单词是什么
9.注意：字典中可能有重复单词
10.输入描述：输入只有一行。先输入字典中的个数n，再输入n个单词作为字典单词。然后输入一个单词x 最后输入一个整数k
11.输出描述：第一行输出查找到x的兄弟单词的个数m 第二行输出查找到的按照字典顺序排序后的第k个兄弟单词，没有符合第k个的话则不用输出
12.数据范围：n（单词数）大于等于1小于等于1000，输入的字符串长度满足len（str）大于等于1小于等于10，k的值小于n，大于等于1
二、解题思路
1.首先我们需要定义一个整数n，用来存储字符串的数量
2.我们还需要定义一个字符串数组str[n][11]用来存储我们的单词
3.我们定义一个字符串x用来存储我们的目标单词
4.我们定义一个整数k用来存储我们按照字典序排列后的目标单词位置
5.我们读取输入的数据，将输入的数据正确的读取到我们的n，str，x，k中
6.为了正确查找到兄弟单词，我们定义两个数组，countx[26]={0},county[26]={0}，再定义一个字符串数组brother[n][11],用来存储我们找到的兄弟单词，定义一个整数m= 0;存储我们找到的兄弟单词数量
7.我们遍历x，将x中的字母的数量按照顺序存储到我们的countx中（利用ascii码是顺序排列的属性）if(islower(countx[x[i])) countx[x[i] - 'a']++;
if(isupper(countx[x[i])) countx[x[i] - 'A]++;
8.然后我们遍历每一个str中的单词，将每一个str中的字母数量也统计一下(遍历之前先qsort一下）
9.统计完之后我们检查，如果countx中所有元素的数量都等于county中的元素数量，那么这是一个兄弟单词
10.我们将兄弟单词存储到我们的brother[m][11]中，m++
11.然后我们输出m的值，换行输出第k个兄弟单词
三、具体步骤
使用的语言是C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
int compare(const void *a, const void *b) {return strcmp((char *)a, (char *)b);
}int main() {int n;scanf("%d", &n);char str[n][11];for(int i = 0; i < n; i++) {scanf("%s", str[i]);}char x[11];int k;scanf("%s %d", x, &k);// printf("k's value is %d\n", k);int countX[26] = {0};int lenX = strlen(x);char brothers[n][11];// char newstr[n][11];int m = 0;// int newstrIndex = 0;// 重新排列str，去重储存到newstr中qsort(str, n, sizeof(str[0]), compare);// strcpy(newstr[newstrIndex++], str[0]);// for(int i = 1; i < n; i++) {// if(!(strcmp(str[i],str[i-1]) == 0)) {// strcpy(newstr[newstrIndex++], str[i]);// printf("%s\n", newstr[newstrIndex-2]);// }// }// printf("x is %s\n", x);// 遍历x，统计字母数量for(int i = 0; i < lenX; i++) {if(islower(x[i])) {countX[x[i] - 'a']++;// printf("countX plus one\n");} else if(isupper(x[i])) {countX[x[i] - 'A']++;}}// 遍历newstrfor(int i = 0; i < n; i++) {int countY[26] = {0};int lenY = strlen(str[i]);for(int j = 0; j < lenY; j++) {if(islower(str[i][j])) {countY[str[i][j] - 'a']++;} else if(isupper(str[i][j])) {countY[str[i][j] - 'A']++;}}int valid = 1;for(int j = 0; j < 26; j++) {if(countX[j] != countY[j]) {valid = 0;break;}}if(valid) {if(!(strcmp(str[i], x) == 0))strcpy(brothers[m++], str[i]);}}printf("%d\n", m);// for(int i = 0; i < m; i++) {// printf("%s\n", brothers[i]);// }if(m > 0) printf("%s\n", brothers[k - 1]);return 0;
}20241101 11：31