5

最近、あるインタビューで、文字列 "aabbbccccddddd" を "a2b3c4d5" に変換するように依頼されました。目標は、繰り返される各文字を 1 回の出現と繰り返し回数に置き換えることです。ここで 'a' は入力で 2 回繰り返されるため、出力では 'a2' と記述する必要があります。また、フォーマットを元のフォーマットに戻す関数を作成する必要があります (たとえば、文字列 "a2b3c4d5" から "aabbbccccdddddd" へ)。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

アプローチ/アルゴリズムは問題ありません。おそらく、コードを少し洗練して縮小することができます（より単純なことを行うことで、過度に複雑な方法でこれを解決する必要はありません）。そして、実際に意味のあるインデント スタイルを選択します。

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();
}
于 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

これを試して

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++ で使用される一般的なパターンに準拠していません。あなたが持っている必要があります：

  • std::stringプレーンchar* arrayの代わりに使用
  • const reference結果を別の場所に書き込むため、変更を避けるためにその文字列を渡します。
  • 範囲ベースの for ループやラムダなどの C++11 機能も使用します。

インタビュアーの目的は、C++11 標準を処理する能力をテストすることだったと思います。アルゴリズム自体は非常に簡単だったからです。

于 2013-10-26T13:18:51.063 に答える
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 に答える