5

最近我在一次采访中被要求将字符串“aabbbccccdddd”转换为“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';
}

我没有发现上面的代码有任何问题。还有其他更好的方法吗？

4

8 回答 8

7

由于其他几个人提出了非常合理的替代方案，我想就我认为您的潜在问题提供一些意见：“他让我尝试比这更聪明的方法......还有其他更好的方法吗？ ？”

当我采访一名开发人员时，我正在寻找能告诉我她如何解决问题的信号：

  1. 正如 H 2 CO 3所指出的，最重要的是正确性：代码可以工作吗？如果算法合理，我通常很乐意忽略小的语法错误（忘记分号、不匹配的括号或大括号等）。

  2. 正确使用语言，尤其是在候选人声称拥有专业知识或拥有丰富经验的情况下。他是否理解并适当地使用习语来编写简单明了的代码？

  3. 她能解释一下她在制定解决方案时的思路吗？它是合乎逻辑和连贯的，还是一种霰弹枪方法？她是否能够并且愿意进行良好的沟通？

  4. 他会考虑边缘情况吗？如果是这样，内在算法是否处理它们，或者一切都是特殊情况？尽管如果初始算法对所有情况都“有效”，我最高兴，但我认为从涵盖所有情况的详细方法开始是完全可以接受的（或者只是添加“TODO”注释，并指出需要做更多的工作完成），然后在以后简化，因为可能更容易注意到模式或重复的代码。

  5. 她会考虑错误处理吗？通常，如果候选人首先询问她是否可以假设输入是有效的，或者带有诸如“如果这是生产代码，我会检查x、y和z问题”之类的评论，我会问她什么会做，然后建议她现在专注于一个有效的算法，（也许）稍后再回来。但如果候选人没有提及，我会感到失望。

  6. 测试，测试，测试！候选人将如何验证他的代码是否有效？他是遍历代码并建议测试用例，还是我需要提醒他？测试用例是否合理？他们会覆盖边缘情况吗？

  7. 优化：作为最后一步，在一切正常并经过验证之后，我有时会问候选人是否可以改进她的代码。如果她在没有我催促的情况下提出建议，则可以加分；如果她在代码运行之前花费大量精力担心它，就会产生负面影响。

将这些想法应用到您编写的代码中，我会做出以下观察：

适当地使用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)。但前提是您承诺不在生产中使用它。

祝你面试顺利！

于 2013-10-26T14:56:43.353 回答
7

方法/算法很好，也许您可​​以稍微改进和缩小代码（通过做一些更简单的事情，没有必要以过于复杂的方式解决这个问题）。并选择一种真正有意义的缩进样式。

交流解决方案：

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();
}
于 2013-10-26T13:20:54.147 回答
5

我认为您的代码对于这项任务来说太复杂了。这是我的方法（使用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解压缩。

于 2013-10-26T13:37:53.653 回答
0

我天真的方法：

void pack( char const * SrcStr, char * DstBuf ) {

    char const * Src_Ptr = SrcStr;
    char * Dst_Ptr = DstBuf;

    char c = 0;
    int RepeatCount = 1;

    while( '\0' != *Src_Ptr ) {

        c = *Dst_Ptr = *Src_Ptr;
        ++Src_Ptr; ++Dst_Ptr;

        for( RepeatCount = 1; *Src_Ptr == c; ++RepeatCount ) {
            ++Src_Ptr;
        }

        if( RepeatCount > 1 ) {
            Dst_Ptr += sprintf( Dst_Ptr, "%i", RepeatCount );
            RepeatCount = 1;
        }
    }

    *Dst_Ptr = '\0';
};

void unpack( char const * SrcStr, char * DstBuf ) {

    char const * Src_Ptr = SrcStr;
    char * Dst_Ptr = DstBuf;

    char c = 0;

    while( '\0' != *Src_Ptr ) {

        if( !isdigit( *Src_Ptr ) ) {
            c = *Dst_Ptr = *Src_Ptr;
            ++Src_Ptr; ++Dst_Ptr;

        } else {
            int repeat_count = strtol( Src_Ptr, (char**)&Src_Ptr, 10 );
            memset( Dst_Ptr, c, repeat_count - 1 );
            Dst_Ptr += repeat_count - 1;
        }
    }

    *Dst_Ptr = '\0';
};

但是，如果面试官要求错误处理，那么解决方案就会变得更加复杂（并且丑陋）。我的便携式方法：

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>

// for MSVC
#ifdef _WIN32
    #define snprintf sprintf_s
#endif

int pack( char const * SrcStr, char * DstBuf, size_t DstBuf_Size ) {

    int Err = 0;

    char const * Src_Ptr = SrcStr;
    char * Dst_Ptr = DstBuf;

    size_t SrcBuf_Size = strlen( SrcStr ) + 1;
    char const * SrcBuf_End = SrcStr + SrcBuf_Size;
    char const * DstBuf_End = DstBuf + DstBuf_Size;

    char c = 0;
    int RepeatCount = 1;

    // don't forget about buffers intercrossing
    if( !SrcStr || !DstBuf || 0 == DstBuf_Size \
        || (DstBuf < SrcBuf_End && DstBuf_End > SrcStr) ) {

        return 1;
    }

    // source string must contain no digits
    // check for destination buffer overflow
    while( '\0' != *Src_Ptr && Dst_Ptr < DstBuf_End - 1 \
        && !isdigit( *Src_Ptr ) && !Err ) {

        c = *Dst_Ptr = *Src_Ptr;
        ++Src_Ptr; ++Dst_Ptr;

        for( RepeatCount = 1; *Src_Ptr == c; ++RepeatCount ) {
            ++Src_Ptr;
        }

        if( RepeatCount > 1 ) {
            int res = snprintf( Dst_Ptr, DstBuf_End - Dst_Ptr - 1, "%i" \
                , RepeatCount );
            if( res < 0 ) {
                Err = 1;
            } else {
                Dst_Ptr += res;
                RepeatCount = 1;
            }
       }
    }

    *Dst_Ptr = '\0';

    return Err;
};

int unpack( char const * SrcStr, char * DstBuf, size_t DstBuf_Size ) {

    int Err = 0;

    char const * Src_Ptr = SrcStr;
    char * Dst_Ptr = DstBuf;

    size_t SrcBuf_Size = strlen( SrcStr ) + 1;
    char const * SrcBuf_End = SrcStr + SrcBuf_Size;
    char const * DstBuf_End = DstBuf + DstBuf_Size;

    char c = 0;

    // don't forget about buffers intercrossing
    // first character of source string must be non-digit
    if( !SrcStr || !DstBuf || 0 == DstBuf_Size \
        || (DstBuf < SrcBuf_End && DstBuf_End > SrcStr) || isdigit( SrcStr[0] ) ) {

        return 1;
    }

    // check for destination buffer overflow
    while( '\0' != *Src_Ptr && Dst_Ptr < DstBuf_End - 1 && !Err ) {

        if( !isdigit( *Src_Ptr ) ) {
            c = *Dst_Ptr = *Src_Ptr;
            ++Src_Ptr; ++Dst_Ptr;

        } else {
            int repeat_count = strtol( Src_Ptr, (char**)&Src_Ptr, 10 );
            if( !repeat_count || repeat_count - 1 > DstBuf_End - Dst_Ptr - 1 ) { 
                Err = 1;
            } else {
                memset( Dst_Ptr, c, repeat_count - 1 );
                Dst_Ptr += repeat_count - 1;
            }
        }
    }

    *Dst_Ptr = '\0';

    return Err;
};

int main() {

    char str[] = "aabbbccccddddd";
    char buf1[128] = {0};
    char buf2[128] = {0};

    pack( str, buf1, 128 );
    printf( "pack: %s -> %s\n", str, buf1 );

    unpack( buf1, buf2, 128 );
    printf( "unpack: %s -> %s\n", buf1, buf2 );

    return 0;
}

测试：http: //ideone.com/Y7FNE3。也适用于 MSVC。

于 2013-10-26T21:03:47.150 回答
0

尝试使用更少的样板：

#include <iostream>
#include <iterator>
#include <sstream>
using namespace std;

template<typename in_iter,class ostream>
void torle(in_iter i, ostream &&o)
{
        while (char c = *i++) {
                size_t n = 1;
                while ( *i == c )
                        ++n, ++i;
                o<<c<<n;
        }
}

template<class istream, typename out_iter>
void fromrle(istream &&i, out_iter o)
{
        char c; size_t n;
        while (i>>c>>n)
                while (n--) *o++=c;
}

int main()
{
    typedef ostream_iterator<char> to;
    string line; stringstream converted;
    while (getline(cin,line)) {
        torle(begin(line),converted);
        cout<<converted.str()<<'\n';
        fromrle(converted,ostream_iterator<char>(cout));
        cout<<'\n';
    }
}
于 2013-10-26T22:12:08.980 回答
0

您的代码“有效”，但它不符合 C++ 中使用的一些常见模式。你应该有：

  • 用于std::string代替普通char* array（s）
  • 传递该字符串const reference以避免修改，因为您将结果写入其他地方；
  • 使用 C++11 特性，例如基于范围的 for 循环和 lambda。

我认为面试官的目的是测试你处理 C++11 标准的能力，因为算法本身非常简单。

于 2013-10-26T13:18:51.063 回答
0

尝试这个

std::string str="aabbbccccddddd";

for(int i=0;i<255;i++)
{
    int c=0;
    for(int j=0;j<str.length();j++)
    {
        if(str[j] == i)
            c++;
    }
    if(c>0)
    printf("%c%d",i,c);
}
于 2013-10-26T14:05:30.950 回答
0

也许面试官想测试你对现有标准库工具的了解。以下是我在 C++ 中的看法：

#include <string>
#include <sstream>
#include <algorithm>
#include <iostream>

typedef std::string::const_iterator Iter;

std::string foo(Iter first, Iter last)
{
    Iter it = first;
    std::ostringstream result;
    while (it != last) {
        it = std::find_if(it, last, [=](char c){ return c != *it; });
        result << *first << (it - first);
        first = it;
    }
    return result.str();    
}

int main()
{
    std::string s = "aaabbbbbbccddde";
    std::cout << foo(s.begin(), s.end());
}

空输入需要额外检查。

于 2013-10-26T13:57:26.390 回答