编程问题 - 传真压缩

Question

我准备通过完成过去比赛的问题参加计算机科学竞赛.他们中的大多数都很容易,但是这个让我感到烦恼......看起来很简单,但我只是无法做到.

如果你有一串1和0:

100111010001111100101010

什么是将其作为输入然后输出的代码:

1:1 2:0 3:1 1:0 1:1 3:0 5:1 2:0 1:1 1:0 1:1 1:0

每个冒号左边的数字是冒号出现后数字的次数.

所以,另一个例子......输入:

1100011

输出:

2:1 3:0 2:1

根据该问题,这类似于用于压缩传真传输的算法.

java中的答案是最好的,但我真正想要的只是伪代码甚至是如何做到的想法.

提前致谢.

Answer 1

这称为运行长度编码(RLE),用于许多事情(例如Windows位图文件格式)以提供非常基本的压缩(特别是如果原始包含大量重复值(如位图或传真) )包含相同颜色的长期运行).

int[] array = { ........ }; // your values...
for ( int i=0; i < array.Length; i++ )
{
   int count = 1;
   int value = array[i];

   // Consume until different..
   while ( i+1 < array.Length && array[i] == array[i+1] )
   { 
       count++; 
       i++ 
   }

   Console.WriteLine("{0}:{1}", count, value);
}

// OR, as suggested by @jon  [done in my head, so could probably be improved a lot...]
int count = 0;
int oldValue = -1;
for ( int i=0; i<array.Length; i++ )
{
   int newValue = array[i];
   count = ( newValue != oldValue ) ? 1 : count+1;

   if ( i+1 >= array.Length || array[i+1] != newValue)
   {
      Console.WriteLine("{0}:{1}", count, newValue);
   }

   oldValue = newValue;
}