华为机试时，自己由于对一些库函数不熟，写的代码像一坨shit，还未调试通过。回来后恶补一次，再写一遍以下三道试题。试题的难度不大，关键是在一小时内能写出清晰的代码，没有bug，对我有点难度。
/*
题目一： 字符串的过滤功能
1、输入'a'~'z'之间的字符串，去掉重复的字符，如：aaazzz --> az
2、pOutputStr在外部已经申请好空间
*/
void StringFilter(const char* pInputStr, long lInputLen, const char* pOutputStr);
思路：
1、由于输入字符串全为小写字母，可以建立一个hash表，索引每个字母出现的次数。
2、从前往后遍历输入字符串，当字母在hash表中的值等于0时，将其写入输出字符串。
3、后面再读到此字母时，hash表中的值大于0，也就不会再次写入输出字符串，从而达到过滤重复字符串的目的。
缺点：
1、需要申请额外的空间。
优点：
1、小写字母可以拓展成任意的字符
复杂度：O(n)
#include<string.h>
void StringFilter(const char* pInputStr, long lInputLen, char* pOutputStr)
{
// 检查输入
if (pInputStr == NULL || *pInputStr == '\0' || lInputLen <= 0)
return ;
const int size = 256;
int hashTable[size];
memset(hashTable, 0, size * sizeof(int)); // 给hashTable赋初始值
unsigned int c;
int j = 0;
// 检查每个字母出现的次数
for (int i = 0; i < lInputLen; ++ i)
{
c = (unsigned int) pInputStr[i];
if (hashTable[c] == 0) // 只写入第一次出现的字母
pOutputStr[j++] = (char)c;
++ hashTable[c];
}
pOutputStr[j] = '\0';
}
/*
题目二：字符串的压缩
1、输入字符串全为'a'~'z'，输出字符串空间申请好，长度和输入相同
2、对相邻的重复出现的字符进行压缩，存储出现次数和字符。如：aaabbca --> 3a2bca
*/
void StringZip(const char* pInputStr, long lInputLen, const char* pOutputStr);
思路：
1、因为压缩的都是相邻的字符串，可以定义前后两个指针“ahead、behind”，
依次比较ahead是否和behind相等，记录该字符出现的次数
2、当ahead != behind时，将该字母出现的次数和字母本身写入输出字符串
复杂度：O(n)
void StringZip(const char* pInputStr, long lInputLen, char* pOutputStr)
{
// 检查输入
if (pInputStr == NULL || *pInputStr == '\0' || lInputLen <= 0)
return ;
const char *ahead, *behind;
unsigned int count; // 统计每个字符在相邻位置出现次数
char numStr[8] = {0};
char c[2] = {0};
strcpy(pOutputStr, "");
ahead = behind = pInputStr;
while (*behind != '\0')
{
++ behind;
if (*ahead != *behind)
{
count = behind - ahead;
c[0] = *ahead;
if (count == 1)
strcat(pOutputStr, c);
else
{
sprintf(numStr, "%d", count); // 将数字转换成字符串
strcat(pOutputStr, numStr); // 追加字符出现次数
strcat(pOutputStr, c); // 追加字符
}
ahead = behind;
}
}
}
/*
题目三：求字符串表达式的加减运算
1、输入字符串的格式为：数字 +[-] 数字，输出字符串运算的结果
2、输入字符串格式检查，如："12 ++ 2"，输入报错
3、运算数位两位以内的整数，不考虑大数溢出等情况
*/
void Arithmetic(const char* pInputStr, long lInputLen, const char* pOutputStr);
思路：
1、不考虑溢出，直接将字符串中的数字提取出来，进行运算
2、判断+、-字符是否输入有误
3、将运算后的结果转换成字符串，赋值给输出字符串
代码：
#include<stdio.h>
#include<string.h>
void Arithmetic(const char* pInputStr, long lInputLen, char* pOutputStr)
{
// 检查输入
if (pInputStr == NULL || *pInputStr == '\0' || lInputLen <= 0)
return ;
int num1, num2, result;
char token[5];
sscanf(pInputStr, "%d %s %d",& num1, token,& num2);
if (strcmp(token, "+") == 0)
result = num1 + num2;
else if (strcmp(token, "-") == 0)
result = num1 - num2;
else
return;
sprintf(pOutputStr, "%d", result);
}