java - 编程问题 - 传真压缩

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;
}