华为笔试——字符串排序、去重、反转等算法（C语言版）
最近刷题记录太多，字符串又是华为笔试非常爱考的知识点，设计字符串的读入、存取、字符的判断、比较、去重、排序等操作。根据华为近几年笔试中出现的题目，依次剖析每道题目的思想和算法实现。
注：题目的编号对应牛客网《华为机试》中的题目编号
目录
HJ2.写出一个程序，接受一个由字母和数字组成的字符串，和一个字符，然后输出输入字符串中含有该字符的个数。不区分大小写。
HJ4.计算字符个数:连续输入字符串，请按长度为8拆分每个字符串后输出到新的字符串数组；长度不是8整数倍的字符串请在后面补数字0，空字符串不处理。
HJ5写出一个程序，接受一个十六进制的数，输出该数值的十进制表示。（多组同时输入 ）
HJ10.编写一个函数，计算字符串中含有的不同字符的个数。字符在ACSII码范围内(0~127)，换行表示结束符，不算在字符里。不在范围内的不作统计。多个相同的字符只计算一次
HJ11.数字颠倒：输入一个整数，将这个整数以字符串的形式逆序输出程序不考虑负数的情况，若数字含有0，则逆序形式也含有0，如输入为100，则输出为001
HJ12.字符串反转：写出一个程序，接受一个字符串，然后输出该字符串反转后的字符串。（字符串长度不超过1000）
HJ13.句子逆序：将一个英文语句以单词为单位逆序排放。例如“I am a boy”，逆序排放后为“boy a am I”所有单词之间用一个空格隔开，语句中除了英文字母外，不再包含其他字符
HJ.20密码验证合格程序.密码要求:1.长度超过8位2.包括大小写字母.数字.其它符号,以上四种至少三种3.不能有相同长度大于2的子串重复
HJ23.实现删除字符串中出现次数最少的字符，若多个字符出现次数一样，则都删除。输出删除这些单词后的字符串，字符串中其它字符保持原来的顺序。
HJ1.计算字符串最后一个单词的长度，单词以空格隔开。
输入描述:
一行字符串，非空，长度小于5000。
输出描述:
整数N，最后一个单词的长度。
思路：这道题的关键在于理解字符串如何存储的，scanf()函数每次从第一个非空白字符，开始读取字符并存储遇到空白字符停止，因此，示例中的"hello"和“world”是两个字符串，如果定义一个字符数组str[5000][5000]存储的话，str[1]='hello'，str[2]='world'，当然可以不用那么复杂，只需要记录最后一个字符串即可；而输入函数自动保存了最后一次的字符串。见代码部分理解
#include <stdio.h>
#include <string.h>
int main()
{
char str[1000];
int n=0;
while(scanf("%s",str) != EOF)//输入多个字符串
{}//不做任何操作，str保存的是最后一个字符串
n=strlen(str);//得到最后一个字符串
printf("%d",n);//输出字符串长度
}HJ2.写出一个程序，接受一个由字母和数字组成的字符串，和一个字符，然后输出输入字符串中含有该字符的个数。不区分大小写。
输入描述:
第一行输入一个有字母和数字以及空格组成的字符串，第二行输入一个字符。
输出描述:
输出输入字符串中含有该字符的个数。
思路：在处理字符串时要考虑多个字符串中的空格、换行等，如果不对换行进行处理，则下个字符串将会保存’\n‘；因此在处理时，可以用getchar()函数将换行吸收。
另外注意题目中要求比较的字符不区分大小写，因此在比较时考虑大小写。小写字母的ASCII比大写字母的大，两者相差固定值32
#include<stdio.h>
#include<string.h>
int main()
{
char str[1000];
char s;
char s2;
int len;
int n;
while(scanf("%s",str)!=EOF)
{
getchar();//吸收换行
scanf("%c",&s);
len=strlen(str);
n=0;
for(int i=0;i<len;i++)
{
if(str[i]==s)
{
n++;
}
else if(str[i]+32==s)//如果是大写则+32转小写
{
n++;
}
else if(str[i]-32==s)//如果是小写则-32转大写
{
n++;
}
}
printf("%d\n",n);
}
}HJ4.计算字符个数:连续输入字符串，请按长度为8拆分每个字符串后输出到新的字符串数组；长度不是8整数倍的字符串请在后面补数字0，空字符串不处理。
输入描述:
连续输入字符串(输入2次,每个字符串长度小于100)
输出描述:
输出到长度为8的新字符串数组
思路：第一次输入abc之后会输入一个换行，因此先用getchar（）函数进行吸收；第二次输入时才能得到正确的字符串；
1.先将原字符串按顺序输出；采取输出单个字符%c格式输出，每8个元素进行换行
2.计算要补齐0的个数，对最后一行进行缺值填充
#include<stdio.h>
#include<string.h>
int main()
{
char str[100];
int len;
int n1,n2;
while(scanf("%s",str)!=EOF)
{
getchar();//吸收换行
len=strlen(str);
n1=len%8;
n2=8-n1;//n2表示要补多少0
//先将原字符串输出
for(int j=0;j<len;j++)
{
printf("%c",str[j]);
if((j+1)%8==0)//由于下标从0开始
{
printf("\n");//每输出8个字符换行
}
}
//将最后一行元素补0
if(n1>0)
{
for(int i=0;i<n2;i++)
{
printf("0");
}
}
printf("\n");
}
}
HJ5写出一个程序，接受一个十六进制的数，输出该数值的十进制表示。（多组同时输入 ）
输入描述:
输入一个十六进制的数值字符串。
输出描述:
输出该数值的十进制字符串。
思路： 十六进制输入的格式是0x 字符串；十六进制转十进制时，从右往左进行转换；
A-E转换10-15，并乘以相应位数的16的次方。
#include <stdio.h>
#include <math.h>
int main()
{
char a[100];
int len;
int i;
while (scanf("%s",a)!=EOF)
{
int sum=0;
len = strlen(a);
//printf("%d",len);
for (i = 0; i < len; i++)//a[0]到a[len-1]
{
//十六进制 0-9 10-15用A-F
//从左至右分别为高位到低位，第一位 a[0]*16^(len-1) 最后一位 a[0]*16^(0)
if ('0' <= a[i]&&a[i]<= '9')
{
sum += (a[i] -'0') * pow(16, (len - 1 - i));
//因为在存储时保存的是数字的字符形式，所以a[i]-'0'才表示真正的数字
}
else if ('A' <= a[i]&&a[i] <= 'F')
{
sum += (a[i]-'A'+10)*pow(16, (len - 1 - i));
//a[i]-'A'+10是将'A'-'Z'映射到0-15之间
}
}
printf("%d\n",sum);
}
return 0;
}
HJ10.编写一个函数，计算字符串中含有的不同字符的个数。字符在ACSII码范围内(0~127)，换行表示结束符，不算在字符里。不在范围内的不作统计。多个相同的字符只计算一次
输入描述:
输入N个字符，字符在ACSII码范围内。
输出描述:
输出范围在(0~127)字符的个数。
思路：与前一题类似，也是定义个标记重复的数组，可见华为笔试很喜欢考这种题目。只不过要将字符先转为数字的ACSII表示。 不在重复叙述。
#include<stdio.h>
#include<string.h>
int main()
{
char str[1000];
int len;
int n;
while(scanf("%s",str)!=EOF)
{
int arr[128]={0};//重复数字标记
int count=0;
getchar();//吸收换行，
len=strlen(str);
for(int i=0;i<len;i++)
{
n=str[i];//char类型转为int型的ACSII码
if(arr[n]==0)
{
arr[n]=1;//标记重复位
count++;//计数器加1
}
}
printf("%d\n",count);
}
}
HJ11.数字颠倒：输入一个整数，将这个整数以字符串的形式逆序输出程序不考虑负数的情况，若数字含有0，则逆序形式也含有0，如输入为100，则输出为001
思路：不需要额外存储空间，只需让数字逆序输出即可，即每次输出最后一个数字，用到数字的取整num/10和取余num%0
#include <stdio.h>
int main()
{
int num;
int n;
scanf("%d",&num);//读入
while(num)
{
n=num%10;
printf("%d",n);//将每次最后一位输出
num=num/10;//去除最后一位后的元素更新为当前num值
}
printf("\n");
}
HJ12.字符串反转：写出一个程序，接受一个字符串，然后输出该字符串反转后的字符串。（字符串长度不超过1000）
思路：字符串反转与数字反转思路相同，都是将数据拆分成单独的个体，按照逆序的方式排列；
可以将反转后的数据存储，之和输出；
也可以在反转的同时立刻输入，不需要占用额外的地址空间。
#include<stdio.h>
#include<string.h>
int main()
{
char str[1000];//存储输入字符串
char str2[1000]=" ";//存储反转后的字符串
int len;
scanf("%s",str);
len=strlen(str);//获取字符串长度
for(int i=0;i<len;i++)
{
str2[len-1-i]=str[i];//存储字符串2
}
printf("%s",str2);//输入反转后的字符串2
}HJ13.句子逆序：将一个英文语句以单词为单位逆序排放。例如“I am a boy”，逆序排放后为“boy a am I”所有单词之间用一个空格隔开，语句中除了英文字母外，不再包含其他字符
输入描述:
将一个英文语句以单词为单位逆序排放。
输出描述:
得到逆序的句子
思路：这道题很简单，定义一个二维数组，以换行位为标记；遇到换行符后，将之前保存在字符数组中的字符串进行反向输出；之后另字符数组下标从0开始，继续读入下一行元素。
#include<stdio.h>
#include<string.h>
int main()
{
char str[1000][1000];//定义字符数组
int n=0;
int len;
while(scanf("%s",str[n])!=EOF)
{
if(getchar()!='\n')//如果没有到换行，
{
n++;//继续读入数组
}
else//否则，对读入的str[0][1000]到str[n][1000]的元素
{
len=n;
for(int i=len;i>=0;i--)//进行逆序输出
{
printf("%s ",str[i]);
}
printf("\n");
n=0;//重设数组从0开始进行下一行字符串的逆序操作
}
}
}HJ14.给定n个字符串，请对n个字符串按照字典序排列。
输入描述:
输入第一行为一个正整数n(1≤n≤1000),下面n行为n个字符串(字符串长度≤100),字符串中只含有大小写字母。输出描述:
数据输出n行，输出结果为按照字典序排列的字符串。
思路：定义字符数组，先存储，在对数组进行排序。
采用strcpy对相邻字符串大小比较；采用冒泡排序对字符串按照递增排序；
注意：冒泡排序外循环从0开始到len-1，内循环从0开始，到len-1-j
#include<stdio.h>
#include<string.h>
int main()
{
char str[1000][100];
int n;
int i;
char temp[100]=" ";
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
{
scanf("%s",str[i]);
}
for(int j=0;j<n-1;j++)//冒泡排序
for(int k=0;k<n-1-j;k++)//每趟排序确定尾部一个值
{
if(strcmp(str[k], str[k+1])>0)
{
strcpy(temp,str[k]);//用strcpy函数进行字符串交换
strcpy(str[k],str[k+1]);
strcpy(str[k+1],temp);
}
}
for(int m=0;m<n;m++)
{
printf("%s\n",str[m]);
}
}
}HJ.20密码验证合格程序.密码要求:1.长度超过8位2.包括大小写字母.数字.其它符号,以上四种至少三种3.不能有相同长度大于2的子串重复
输入描述:
一组或多组长度超过2的子符串。每组占一行
输出描述:
如果符合要求输出：OK，否则输出NG
思路：本题的1.2条件比较好判断，即对字符串长度进行判断和对出现的小写字母、大写字母、数字以及其他的统计；
第三个限制条件需要比较三个连续的字符串之和是否出现，如出现则验证失败。这里可以用两个for循环进行，外循环i从0开始，内循环每次从i的第三个数开始；每次比较两个循环中连续的三个数是否对应相等。
详见代码。
注意：三个条件是并列的，最后输出OK时必须保证前三个条件均不满足，即if(flag==0)不能去掉，之前没加，只有90%的测试用例通过。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
char s[100];
while(scanf("%s",s)!=EOF )
{ int flag=0;
//第一个条件判断不满足直接后面的就不用判断了
int len=strlen(s);
if(len<=8)
{ printf("NG\n");flag=1;continue;}
//第二个条件判断，不满足则退出
int count=0,num=0,low=0,upper=0,other=0;
for(int i=0;i<len;i++)
{
if(s[i]>='0'&&s[i]<='9')
num=1;
else if(s[i]>='A'&&s[i]<='Z')
low=1;
else if(s[i]>='a'&&s[i]<='z')
upper=1;
else
other=1;
}
count=num+low+upper+other;
if(count<3)
{ printf("NG\n");flag=1;continue;}
//第三个条件判断
for(int i=0;i<=len-3;i++)
for(int k=i+3;k<len;k++)
{
if(s[i]==s[k]&&s[i+1]==s[k+1]&&s[i+2]==s[k+2])
{ printf("NG\n");flag=1;continue;}
}
//如果flag==0表示满足3个条件，所以输出ok
if(flag==0)
printf("OK\n");
}
return 0;
}HJ.21简单密码
密码是我们生活中非常重要的东东，我们的那么一点不能说的秘密就全靠它了。哇哈哈. 接下来渊子要在密码之上再加一套密码，虽然简单但也安全。
假设渊子原来一个BBS上的密码为zvbo9441987,为了方便记忆，他通过一种算法把这个密码变换成YUANzhi1987，这个密码是他的名字和出生年份，怎么忘都忘不了，而且可以明目张胆地放在显眼的地方而不被别人知道真正的密码。
他是这么变换的，大家都知道手机上的字母： 1--1， abc--2, def--3, ghi--4, jkl--5, mno--6, pqrs--7, tuv--8 wxyz--9, 0--0,就这么简单，渊子把密码中出现的小写字母都变成对应的数字，数字和其他的符号都不做变换，
声明：密码中没有空格，而密码中出现的大写字母则变成小写之后往后移一位，如：X，先变成小写，再往后移一位，不就是y了嘛，简单吧。记住，z往后移是a哦。
输入描述:
输入包括多个测试数据。输入是一个明文，密码长度不超过100个字符，输入直到文件结尾
输出描述:
输出渊子真正的密文
思路：
就是普通的替换，注意转换的时候输出
#include<stdio.h>
#include<string.h>
int main()
{
char str[100];
int len;
int num;
while(scanf("%s",str)!=EOF)
{
len=strlen(str);
for(int i=0;i<len;i++)
{
if(str[i]>='a'&&str[i]<='z')//小写字母转数字
{
if(str[i]>='a'&&str[i]<='c')
{
num=2;
}
else if(str[i]>='d'&&str[i]<='f')
{
num=3;
}
else if(str[i]>='g'&&str[i]<='i')
{
num=4;
}
else if(str[i]>='j'&&str[i]<='l')
{
num=5;
}
else if(str[i]>='m'&&str[i]<='o')
{
num=6;
}
else if(str[i]>='p'&&str[i]<='s')
{
num=7;
}
else if(str[i]>='t'&&str[i]<='v')
{
num=8;
}
else if(str[i]>='w'&&str[i]<='z')
{
num=9;
}
printf("%d",num);
}
else if(str[i]>='A'&&str[i]<='Z')//大写字母
{
if(str[i]=='Z')
{
str[i]='a';
}
else
{
str[i]=str[i]+32+1;
}
printf("%c",str[i]);
}
else//是数字，数字不改变
{
printf("%c",str[i]);
}
}
printf("\n");
}
}HJ23.实现删除字符串中出现次数最少的字符，若多个字符出现次数一样，则都删除。输出删除这些单词后的字符串，字符串中其它字符保持原来的顺序。
注意每个输入文件有多组输入，即多个字符串用回车隔开
输入描述:
字符串只包含小写英文字母, 不考虑非法输入，输入的字符串长度小于等于20个字节。
输出描述:
删除字符串中出现次数最少的字符后的字符串。
思路：考虑到统计重复值时，要构建一个标记数组，这里将字母‘a’到‘z’映射到数组下标0-25，需要强制转换，将字符‘a’映射到下标0,最后在判断时，判断标记数组中个数，即可找到重复值最小的几组数据，进行删除，（这里删除用输出进行控制，对出现字符最少的数不输出即可）
#include<stdio.h>
#include<string.h>
int main()
{
char str[20];
int len;
int n;
while(scanf("%s",str)!=EOF)
{
len=strlen(str);
int min;
int arr[26]={0};
for(int i=0;i<len;i++)
{
n=str[i]-'a';
arr[n]++;//将'a'到'z'赋值到0-25
}
min=1;//最小值开始值赋值1
for(int j=1;j<len;j++)
{
if(min>arr[j]&&arr[j]>1)
{
min=arr[j];//统计最小值
}
}
for(int k=0;k<len;k++)
{
n=str[k]-'a';
if(arr[n]!=min)//将重复值大与min的值输出
{
printf("%c",str[k]);
}
}
printf("\n");
}
}HJ26.字符串排序
编写一个程序，将输入字符串中的字符按如下规则排序。
规则 1 ：英文字母从 A 到 Z 排列，不区分大小写。
如，输入： Type 输出： epTy
规则 2 ：同一个英文字母的大小写同时存在时，按照输入顺序排列。
如，输入： BabA 输出： aABb
规则 3 ：非英文字母的其它字符保持原来的位置。
如，输入： By?e 输出： Be?y
思路：一开始想的是用冒泡排序，但是存在不是字母的元素就需要判断很多个条件，看了网友的做法，提出了一种新的思路：构建一个temp数组，用来存放aaAAbBbb...等，将字母顺序排在前面的元素依次存放在temp数组中，在对原数组中的字母元素进行依次替换；非字母元素保留不动。
注意的是：读入的是一行字符串，对其进行排序，如果用scanf("%s,str)进行读入，其遇到空格就停止了。因此这里用的是gets()函数，其能读入一行字符串（包括空格），在遇到换行或EOF时停止。
#include <stdio.h>
#include <string.h>
int main()
{
char str[1000];
while(gets(str))//gets()函数每次读入一行，换行或遇到EOF结束，且换行从缓存区丢弃
{
int i,j,k=0;
char temp[1000];
for(i=0;i<26;i++)//0-25表示26个字母
{
for(j=0;j<strlen(str);j++)
{
if(str[j] == 'a'+i || str[j] == 'A'+i)//从a和A开始找
temp[k++] = str[j];//依次存入temp数组中
}
}//temp数组仅存放字母，对于非字母未存放
k=0;
for(i=0;i<strlen(str);i++)//替换原数组的字母
{
if((str[i]>='a'&&str[i]<='z')||(str[i]>='A'&&str[i]<='Z'))//将字母出现的位置替换为排序后的元素
str[i] = temp[k++];
}
printf("%s\n",str);
}
return 0;
}
上一篇： Ubuntu下两个gcc版本切换