0 前言

一道新势力 OEM 机试题（非本人），实则为牛客网上的一道华为校招机试题，这里记录下个人解法与牛客网上的最佳解法。

1 题目描述

将一个字符中所有的整数前后加上符号“*”，其他字符保持不变。连续的数字视为一个整数。注意：本题有多组样例输入。

输入描述:

输入一个字符串

输出描述:

1	字符中所有出现的数字前后加上符号“*”，其他字符保持不变

示例 1

输入

1 2	Jkdi234klowe90a3 5151

输出

1 2	Jkdi234klowe90a3 5151

2 求解

2.1 我的解法

函数声明

#ifndef _SOLUTION_HPP_
#define _SOLUTION_HPP_

#include <string>

std::string GenNewStr(std::string &string);

#endif

函数实现

#include "solution.hpp"

std::string GenNewStr(std::string &string)
{
    std::string result = "";
    bool flag_found_number = false;

    for (auto iter = string.begin(); iter != string.end(); ++iter)
    {
        // process the head of number
        if (!flag_found_number && ((*iter >= '0') && (*iter <= '9')))
        {
            result += "*";
            flag_found_number = true;
        }

        // process the trail of number
        if (flag_found_number && ((*iter < '0') || (*iter > '9')))
        {
            result += "*";
            flag_found_number = false;
        }
        result += *iter;
    }

    // process the end of input
    if (flag_found_number)
    {
        result += "*";
        flag_found_number = false;
    }

    return result;
}

主函数

#include <iostream>
#include <string>

#include "solution.hpp"

int main()
{
    std::string input;

    while (std::cin >> input)
        std::cout << GenNewStr(input) << std::endl;
    return 0;
}

测试结果

$ ./XP_Code.exe
asdad83kasd
asdad*83*kasd
1
*1*
902934
*902934*
sdfiw8
sdfiw*8*
123ksdf9384js823jd8
*123*ksdf*9384*js*823*jd*8*

提交到牛客上，运行时间 8ms，占用内存 612KB。

2.2 最佳解法

截止至 2021 年 4 月 20 日，牛客上排名第一的 C++ 实现，运行时间 1ms，占用内存 372KB。

#include <iostream>
#include <string>
using namespace std;
int main()
{
    string s;
    while (cin >> s)
    {
        for (int i = 0; i < s.length(); i++)
        {
            if (s[i] >= '0' && s[i] <= '9' && (i == 0 || s[i - 1] < '0' || s[i - 1] > '9'))
            {
                s = s.substr(0, i) + "*" + s.substr(i);
                i++;
            }
            if (s[i] >= '0' && s[i] <= '9' && (i + 1 == s.length() || s[i + 1] < '0' || s[i + 1] > '9'))
            {
                s = s.substr(0, i + 1) + "*" + s.substr(i + 1);
                i++;
            }
        }
        cout << s << endl;
    }
    return 0;
}

实现比较巧妙，通过 string 的 substr 方法进行字符串拼接，避免了 2.1 方法中遍历字符串的每个字符时都需要进行的“累加字符”操作，因此耗时更少。substr 中的参数是需要注意的点。

参考

表示数字
std::string::substr
【C++】C++中 substr 的用法
C++中 substr 函数的用法
C++ string 类型结尾会像 C 一样添加\0 吗？
C++ string 是否以‘\0’结尾讨论

输出倒逼思考

【OJ】表示数字

0 前言

1 题目描述

2 求解

2.1 我的解法

2.2 最佳解法

参考