c++ - 就地压缩位串（C++）

Question

我正在尝试制作一个压缩 0 和 1 字符串的函数。也就是说，“00010111100101”变为“30104100101”。这应该是一个非常复杂的过程吗？我的代码看起来很乱。

原型应如下所示：

static void compress_bitstring(std::string& str) { 
   // compression algorithm
} 

Answer 1

这是我的方法

更新意识到我的答案可能会更短，更全面（感谢 Nik Bougalis）

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

static void compress_bitstring(std::string& str) { 
  std::stringstream ss;
  std::string cur_num;
  int count = 1;
  for (int i = 0; i < str.size()-1; ++i){
    if (str[i] == str[i+1]){
      ++count;
      cur_num = str[i];
      if (i == str.size()-2){
        ss << count << cur_num;
      } else{
        if (count == 9){
          ss << count << cur_num;
          count = 0;
        }
      }
    } else if (count > 2){
        ss << count << cur_num;
        count = 1;
        if (i == str.size()-2){
          ss << str[i+1];
        }
    } else if (i != str.size()-2){
        for (int j = 0; j < count; ++j){
          ss << str[i];
        }
        count = 1;
    } else{
      ss << str[i] << str[i];
    }
  }
  str = ss.str();
}

static void decode_bitstring(std::string& str){
  int i = 0;
  int count;
  std::stringstream ss;
  while (i < str.size()){
    std::stringstream to_int;
    to_int << str[i];
    to_int >> count;
    if (count > 1){
      for (int j = 0; j < count; ++j){
        ss << str[i+1];
      }
      i = i + 2;
    } else{
      ss << str[i];
      ++i;
    }
  }
  str = ss.str();
}

int main(){
  std::string binary_num =  "0001011110010100000000000000000000000001";
  std::cout << binary_num << '\n';
  compress_bitstring(binary_num);
  std::cout << binary_num << '\n';
  decode_bitstring(binary_num);
  std::cout << binary_num << '\n';
  return 0;
}

编辑 2我还提供了一个解码器选项。

输出：

nero@ubuntu:~/learn$ ./lc
0001011110010100000000000000000000000001
301041001019090701
0001011110010100000000000000000000000001

Answer 2

好的，这是我的最终答案，压缩运行长度 > 9 并重构重复代码。

template<typename T>
std::string to_string(T t)
{
    std::ostringstream str;
    str << t;
    return str.str();
}

static void compress_bitstring(std::string& str)
{
    std::string result;
    int count = 0;
    char last = 0;

    auto add_to_result = [&]{
        if (count > 2)
            result += to_string(count) + last;
        else for (auto loop=0; loop<count; ++loop)
            result += last;
    };

    for (char ch : str)
    {
        if ((last == 0  ||  ch == last)  &&  count < 9)
            ++count;
        else {
            add_to_result();
            count = 1;
        }
        last = ch;
    }

    add_to_result();
    swap(result, str);
}

int main()
{
    std::string str("00010111100101");
    compress_bitstring(str);
    assert(str == "30104100101");

    str = "0001011110010100000000000000000000000001";
    compress_bitstring(str);
    assert(str == "301041001019090701");

    return 0;
}

Answer 3

template<typename T>
std::string to_string(T t)
{
    std::ostringstream str;
    str << t;
    return str.str();
}

static void compress_bitstring(std::string& str)
{
    std::string result;
    int count = 0;
    char last = 0;
    for (char ch : str)
    {
        if (last == 0  ||  ch == last)
            ++count;
        else {
            if (count > 2)
                result += to_string(count) + last;
            else for (auto loop=0; loop<count; ++loop)
                result += last;
            count = 1;
        }
        last = ch;
    }

    if (count > 2)
        result += to_string(count) + last;
    else for (auto loop=0; loop<count; ++loop)
            result += last;

    swap(result, str);
}

int main()
{
    std::string str("00010111100101");
    compress_bitstring(str);
    assert(str == "30104100101");

    return 0;
}

Answer 4

std::string compress1(std::string &s) {
    char c = s[0];
    int counter = 1;
    std::stringstream ss;
    for (size_t i = 1; i < s.length(); i++) {
        if (c != s[i]) {
            if (counter > 2) ss << counter;
            if (counter == 2) ss << c;
            ss << c;
            counter = 0;
        }
        c = s[i];
        counter++;
    }
    if (counter > 2) ss << counter;
    if (counter == 2) ss << c;
    ss << c;
    return ss.str();
}

输出：

compress1("00010111100101"): 30104100101
compress1("000101111001011"): 301041001011

Answer 5

在这里，我发布我的逻辑可能对您有所帮助。

 #include<string.h>

int main(){
   char* str ="00010111100101";
   char* result = malloc(strlen(str)+1);
   int i = 0;
   char *q;
   char * p = str;
   result[i++] = str[0];

   do{
      q = strchr(str,str[0]=='0'?'1':'0'); //Searching for the opposite char.
     result[i++] = (q == '\0'? str+strlen(str) : q ) - p + '0'; // Storing the difference in result 
     str = p = q;   //updating str and p
   }while(q != '\0');
   result[i] = '\0';
   printf("Compressed Result = %s",result);
   return 0;
}

http://codepad.org/Qn8NEuB7