最近我在接受采访时被要求将字符串"aabbbccccddddd"转换为"a2b3c4d5".目标是用一次出现和重复计数替换每个重复的字符.这里'a'在输入中重复两次,因此我们必须在输出中将其写为'a2'.另外,我需要编写一个函数来将格式反转回原始格式(例如从字符串"a2b3c4d5"到"aabbbccccddddd").我可以自由使用C或C++.我写了下面的代码,但面试官似乎对此不太满意.他让我尝试一种比这更聪明的方法.
在下面的代码中,我曾经formatstring()通过添加重复计数来消除重复的字符,并用于reverseformatstring()转换回原始字符串.
void formatstring(char* target, const char* source) {
int charRepeatCount = 1;
bool isFirstChar = true;
while (*source != '\0') {
if (isFirstChar) {
// Always add the first character to the target
isFirstChar = false;
*target = *source;
source++; target++;
} else {
// Compare the current char with previous one,
// increment repeat count
if (*source == *(source-1)) {
charRepeatCount++;
source++;
} else {
if (charRepeatCount > 1) {
// Convert repeat count to string, append to the target
char repeatStr[10];
_snprintf(repeatStr, 10, "%i", charRepeatCount);
int repeatCount = strlen(repeatStr);
for (int i = 0; i < repeatCount; i++) {
*target = repeatStr[i];
target++;
}
charRepeatCount = 1; // Reset repeat count
}
*target = *source;
source++; target++;
}
}
}
if (charRepeatCount > 1) {
// Convert repeat count to string, append it to the target
char repeatStr[10];
_snprintf(repeatStr, 10, "%i", charRepeatCount);
int repeatCount = strlen(repeatStr);
for (int i = 0; i < repeatCount; i++) {
*target = repeatStr[i];
target++;
}
}
*target = '\0';
}
void reverseformatstring(char* target, const char* source) {
int charRepeatCount = 0;
bool isFirstChar = true;
while (*source != '\0') {
if (isFirstChar) {
// Always add the first character to the target
isFirstChar = false;
*target = *source;
source++; target++;
} else {
// If current char is alpha, add it to the target
if (isalpha(*source)) {
*target = *source;
target++; source++;
} else {
// Get repeat count of previous character
while (isdigit(*source)) {
int currentDigit = (*source) - '0';
charRepeatCount = (charRepeatCount == 0) ?
currentDigit : (charRepeatCount * 10 + currentDigit);
source++;
}
// Decrement repeat count as we have already written
// the first unique char to the target
charRepeatCount--;
// Repeat the last char for this count
while (charRepeatCount > 0) {
*target = *(target - 1);
target++;
charRepeatCount--;
}
}
}
}
*target = '\0';
}
我没有发现上述代码有任何问题.还有其他更好的方法吗？
小智 7
方法/算法很好,也许你可以稍微改进和缩小代码(通过做一些更简单的事情,没有必要以过于复杂的方式解决这个问题).并选择一种实际上有意义的缩进风格.
AC解决方案:
void print_transform(const char *input)
{
for (const char *s = input; *s;) {
char current = *s;
size_t count = 1;
while (*++s == current) {
count++;
}
if (count > 1) {
printf("%c%zu", current, count);
} else {
putc(current, stdout);
}
}
putc('\n', stdout);
}
(这可以很容易地修改,以便它返回转换后的字符串,或者将其写入足够长的缓冲区.)
一个C++解决方案:
std::string transform(const std::string &input)
{
std::stringstream ss;
std::string::const_iterator it = input.begin();
while (it != input.end()) {
char current = *it;
std::size_t count = 1;
while (++it != input.end() && *it == current) {
count++;
}
if (count > 1) {
ss << current << count;
} else {
ss << current;
}
}
return ss.str();
}
由于其他几个人提出了非常合理的选择,我想就我认为你的基本问题提出一些看法:"他让我尝试一种比这更聪明的方式....还有其他更好的办法吗？ ？"
当我采访开发人员时,我正在寻找告诉我她如何解决问题的信号:
最重要的是,正如H 2 CO 3所指出的那样,是正确的:代码是否有效？如果算法合理,我通常很乐意忽略小的语法错误(遗忘的分号,不匹配的parens或括号等).
正确使用该语言,特别是如果候选人声称具有专业知识或具有丰富的经验.他是否理解并恰当地使用习语来编写简单明了的代码？
在她提出解决方案时,她可以解释一下她的思路吗？它是合乎逻辑且连贯的,还是一种霰弹枪方法？她能干并且愿意沟通吗？
他是否考虑了边缘情况？如果是这样,内在算法是否处理它们,或者一切都是特例？虽然我最开心的是如果初始算法"适用于所有情况",我认为从一个涵盖所有情况的冗长方法开始(或者只是添加"TODO"注释,并指出需要做更多工作)是完全可以接受的.完成),然后稍后简化,当它可能更容易注意到模式或重复的代码.
她是否考虑过错误处理？通常情况下,如果候选人首先询问她是否可以认为输入有效,或者评论如"如果这是生产代码,我会检查x,y和z问题",我会问她是什么会这样做,然后建议她现在专注于一个工作算法,然后(也许)稍后回过头来.但如果候选人没有提及它,我会很失望.
测试,测试,测试!候选人如何验证他的代码是否有效？他是否介绍了代码并建议测试用例,还是需要提醒他？测试用例是否合理？他们会覆盖边缘案件吗？
优化:作为最后一步,在一切正常并经过验证后,我有时会询问候选人是否可以改进她的代码.如果她在没有我的刺激的情况下提出建议,奖励积分; 如果她在代码工作之前花了很多精力担心它,那就是负面因素.
将这些想法应用到您编写的代码中,我会做出以下观察:
正确使用const是一个优点,因为它表明熟悉语言.在一次采访中,我可能会问一两个关于为何/何时使用它的问题.
在char整个代码中正确使用指针是一个好兆头.我倾向于在比较中明确表达数据类型,特别是在访谈期间,所以我很高兴看到,例如,
while (*source != '\0')而不是(普通的,正确的,但IMO不那么小心)while(*source).
isFirstChar根据我的"边缘情况"点,有点红旗.当您声明一个布尔值来跟踪代码的状态时,通常会有一种方法来重新构建问题以便本质地处理该条件.在这种情况下,您可以使用它charRepeatCount来确定这是否是可能系列中的第一个字符,因此您不需要显式测试字符串中的第一个字符.
出于同样的原因,重复的代码也可以是可以简化算法的标志.一个改进是将转换转换为charRepeatCount单独的函数.请参阅下面的更好解决方案.
这很有趣,但我发现候选人很少在采访中为他们的代码添加评论.感谢有用的人,对于那些在没有信息的情况下增加详细程度的"增加计数器"的负面观点.人们普遍认为,除非你做了一些奇怪的事情(在这种情况下你应该重新考虑你所写的内容),你应该假设读代码的人熟悉编程语言.所以评论应该解释你的思考过程,而不是将代码翻译成英文.
过多的嵌套条件或循环也可能是一个警告.您可以通过将每个字符与下一个字符(而不是前一个字符)进行比较来消除一级嵌套.这甚至适用于字符串中的最后一个字符,因为它将与终止空字符进行比较,该字符不匹配,可以像任何其他字符一样对待.
有一种更简单的方法可以charRepeatCount从int一个字符串转换为字符串.例如,_snprintf()返回它"打印"到字符串的字节数,因此您可以使用
target += _snprintf(target, 10, "%i", charRepeatCount);
在反转功能中,您已经完全使用了三元运算符......但是没有必要特殊情况下零值:无论数值如何,数学都是相同的.同样,还有标准的实用程序函数atoi(),它会将字符串的前导数字转换为整数.
经验丰富的开发人员通常会将增量或减量操作包含在循环中作为条件的一部分,而不是作为底部的单独语句:while(charRepeatCount-- > 0).如果你用幻灯片操作符写的话,我会挑起眉毛但是给你一点点幽默和个性:while (charRepeatCount --> 0).但只有你承诺不在生产中使用它.
祝你的面试好运!
我认为你的代码太复杂了.这是我的方法(使用C):
#include <ctype.h>
#include <stdio.h>
void format_str(char *target, char *source) {
int count;
char last;
while (*source != '\0') {
*target = *source;
last = *target;
target++;
source++;
for (count = 1; *source == last; source++, count++)
; /* Intentionally left blank */
if (count > 1)
target += sprintf(target, "%d", count);
}
*target = '\0';
}
void convert_back(char *target, char *source) {
char last;
int val;
while (*source != '\0') {
if (!isdigit((unsigned char) *source)) {
last = *source;
*target = last;
target++;
source++;
}
else {
for (val = 0; isdigit((unsigned char) *source); val = val*10 + *source - '0', source++)
; /* Intentionally left blank */
while (--val) {
*target = last;
target++;
}
}
}
*target = '\0';
}
format_str压缩字符串,然后convert_back解压缩它.
您的代码“有效”，但它不遵循 C++ 中使用的一些常见模式。你应该有：
std::string而不是普通char* array的const reference避免修改，因为您将结果写入其他地方；我认为面试官的目的是测试你处理 C++11 标准的能力，因为算法本身相当简单。