2014 年华为校园招聘机试题

时间：2022-01-17 18:52:51

试题

一、字符串过滤（60分）：

通过键盘输入一串小写字母(a~z)组成的字符串。请编写一个字符串过滤程序，若字符串中出现多个相同的字符，将非首次出现的字符过滤掉。 比如字符串“abacacde”过滤结果为“abcde”。
要求实现函数：
void stringFilter(const char *pInputStr, long lInputLen, char *pOutputStr);
【输入】 pInputStr： 输入字符串; lInputLen： 输入字符串长度
【输出】 pOutputStr： 输出字符串，空间已经开辟好，与输入字符串等长；
【注意】只需要完成该函数功能算法，中间不需要有任何IO的输入输出 示例
输入：“deefd” 输出：“def”
输入：“afafafaf” 输出：“af”
输入：“pppppppp” 输出：“p”
main函数已经隐藏，这里保留给用户的测试入口，在这里测试你的实现函数，可以调用printf打印输出
当前你可以使用其他方法测试，只要保证最终程序能正确执行即可，该函数实现可以任意修改，但是不要改变函数原型。一定要保证编译运行不受影响。

二、字符串压缩（40分）：

通过键盘输入一串小写字母(a~z)组成的字符串。请编写一个字符串压缩程序，将字符串中连续出席的重复字母进行压缩，并输出压缩后的字符串。 压缩规则：
1. 仅压缩连续重复出现的字符。比如字符串”abcbc”由于无连续重复字符，压缩后的字符串还是”abcbc”。
2. 压缩字段的格式为”字符重复的次数+字符”。例如：字符串”xxxyyyyyyz”压缩后就成为”3x6yz”。 要求实现函数：
void stringZip(const char *pInputStr, long lInputLen, char *pOutputStr);
【输入】 pInputStr： 输入字符串 lInputLen： 输入字符串长度
【输出】 pOutputStr： 输出字符串，空间已经开辟好，与输入字符串等长；
【注意】只需要完成该函数功能算法，中间不需要有任何IO的输入输出 示例
输入：“cccddecc” 输出：“3c2de2c”
输入：“adef” 输出：“adef”
输入：“pppppppp” 输出：“8p”

三、字符串计算器（50分）：

通过键盘输入100以内正整数的加、减运算式，请编写一个程序输出运算结果字符串。 输入字符串的格式为：“操作数1 运算符 操作数2”，“操作数”与“运算符”之间以一个空格隔开。 补充说明：
1、操作数为正整数，不需要考虑计算结果溢出的情况。 2、若输入算式格式错误，输出结果为“0”。 要求实现函数：
void arithmetic(const char *pInputStr, long lInputLen, char *pOutputStr);
【输入】 pInputStr： 输入字符串 lInputLen： 输入字符串长度
【输出】 pOutputStr： 输出字符串，空间已经开辟好，与输入字符串等长；
【注意】只需要完成该函数功能算法，中间不需要有任何IO的输入输出 示例
输入：“4 + 7” 输出：“11”
输入：“4 - 7” 输出：“-3”
输入：“9 ++ 7” 输出：“0” 注：格式错误

解析

  • stringFilter 给出两种时间复杂度的算法实现。
    • O(n^2) 的实现，是逐个在输出字符串是否存在该字符，如果不存在，写入到输出
    • O(n) 的实现，是用一个数组标记，是否已经出现过该字符。
  • stringZip 应注意 单个字符 重复的次数可能超过9，即多位
  • arithmetic 分别提取出左右操作数和运算符，转换成整型计算
#include <iostream>
#include <string.h>
#include <stdlib.h>
using namespace std;
// 算法复杂度 O(n^2)
void stringFilter(const char *pInputStr, long lInputLen, char *pOutputStr) {
    if (lInputLen == 0)
        return;
    int count = 0; // 统计当前输出字符串的长度
    while (*pInputStr != '\0') {
        int i = 0;
        // 查找是否存在相同的字符
        while (i < count) {
            if (*(pOutputStr+i) == *pInputStr)
                break;
            i++;
        }
        if (i == count) {
            // 没有找到
            *(pOutputStr+count) = *pInputStr;
            count++;
        }
        pInputStr++;    
    }
    *(pOutputStr+count) = *pInputStr; // 补 '\0'
}
// 算法复杂度 O(n)
void stringFilter2(const char *pInputStr, long lInputLen, char *pOutputStr) {
    bool flag[26] = {0};
    for(int i = 0; i < lInputLen; i++) {
        int num = *(pInputStr+i) - 'a';
        if (flag[num] == false) {
            *(pOutputStr++) = *(pInputStr+i);
            flag[num] = true;
        }
    }
    *pOutputStr = '\0';
}
// 时间复杂度 O(n) 空间复杂度 O(1)
void stringZip(const char *pInputStr, long lInputLen, char *pOutputStr) {
    int k = 0;
    for (int i = 0; i < lInputLen-1; ) {
        int count = 1;
        for (int j = i+1; j < lInputLen; j++) {
            if (pInputStr[i] == pInputStr[j]) {
                count++;
                continue;
            } else {
                break;
            }
        }
        if (count == 1) {
            pOutputStr[k++] = pInputStr[i];
        } else {
            char count_buff[20];
            memset(count_buff, 0, 20);
            _itoa(count, count_buff, 10);
            strcpy(pOutputStr+k, count_buff);
            k += strlen(count_buff);
            pOutputStr[k++] = pInputStr[i];
        }
        i += count;
    }
    pOutputStr[k] = '\0';
}
// 算法时间复杂度O(n)，空间复杂度 O(n)
void arithmetic(const char *pInputStr, long lInputLen, char *pOutputStr) {
    // 初始化结果为0
    pOutputStr[0] = '0';
    pOutputStr[1] = '\0';
    char* left = new char [lInputLen];
    char* right = new char [lInputLen];
    char sign;
    int i = 0; // 输入
    int j = 0; // 算子索引
    // 提取左操作数
    while (i < lInputLen) {
        if (pInputStr[i] == ' ')
            break;
        if (pInputStr[i] < '0' || pInputStr[i] > '9')
            return;
        left[j++] = pInputStr[i++];
    }
    left[j] = '\0';
    // 提取运算符
    i++;
    sign = pInputStr[i++];
    i++;
    // 提取右操作数
    j = 0;
    while (i < lInputLen) {
        if (pInputStr[i] < '0' || pInputStr[i] > '9')
            return;
        right[j++] = pInputStr[i++];
    }
    right[j] = '\0';
    // 计算结果
    int result;
    if (sign == '+')
        result = atoi(left) + atoi(right);
    else if (sign == '-')
        result = atoi(left) - atoi(right);
    else
        return;
    _itoa(result, pOutputStr, 10);
    delete left;
    delete right;
}

int main()
{
    char s[] = "pppmnmppssppp";
    int len = strlen(s);
    char* fliter_res = new char[len];
    stringFilter2(s, len, fliter_res);
    cout << "stringFilter: 操作字符串为：" << s << endl;
    cout << "输出："   << fliter_res << endl;

    char* zip_res = new char[len];
    stringZip(s, len, zip_res);
    cout << "stringZip: 操作字符串为：" << s << endl;
    cout  << "输出："  << zip_res << endl;

    char s2[] = "23 + 34";
    int len2 = strlen(s2);
    char* res2 = new char[len2];
    arithmetic(s2, strlen(s2), res2);
    cout << "arithmetic: 操作字符串为：" << s2 << endl;
    cout  << "输出："  << res2 << endl;

    getchar();
    return 0;
}
标签：

相关文章