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中的答案是最好的，但我真正在寻找的是伪代码，甚至是关于如何去做的想法。

提前致谢。

4

3 回答 3

5

这称为运行长度编码 (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;
}
于 2009-01-18T16:41:20.690 回答
2

就像一个想法：你为什么要打扰右边的数字？它总是在 1 和 0 之间交替，不是这样，所以假设它以 1 开头，如果实际序列以 0 开头，则编码一个初始 0。换句话说，你最终会得到：

1 2 3 1 1 3 5 2 1 1 1 1

但基本上你需要跟踪“我目前在看什么？” 和“我见过多少”？如果它发生变化，写下你一直在看的内容和计数，然后将“我正在看的内容”更新为新值并将计数更新为 1，然后继续。不要忘记在数据末尾写出最后一个值。

（我没有给出伪代码或 Java，因为我认为你会通过接受小提示而不是提供工作代码来了解更多信息。如果你需要进一步的提示，尽管说。）

于 2009-01-18T16:40:59.117 回答
0

我真正在寻找的只是伪代码，甚至是关于如何去做的想法。

以下是一些想法：

  • 如何测试字节中的一位是一还是零：使用“按位与”运算来屏蔽其他位
  • 如何测试字节中的不同位是一还是零：
    • 要么，使用不同的位掩码
    • 或者，在屏蔽之前移动或旋转字节中的位

使用上述方法，对第一个字节中的 8 位进行处理。然后重复此操作以处理下一个字节中的下一个 8 位。

一些伪代码可能类似于以下内容：

main()
{
  Encoder encoder = new Encoder;
  foreach (byte b in inputStream)
  {
    encoder.input(b);
  }
  //tell the encoder that the stream is finished
  //that there will be no subsequent bytes
  ///and that the final bits should be flushed now
  encoder.finished();
}

class Encoder
{
  //member data
  bool m_b; //value of the most-recently-processed bit
  int m_n; //number of the most-recently-processed bits

  //public methods
  void finished()
  {
    //TODO format and write the {m_n}:{m_b} value to output
    //and reset m_n to zero
  }

  void input(byte b)
  {
    for int (i = 0; i < 8; ++i)
    {
      //get the bit value
      bool bit = getbit(b, i);
      //see whether we can append it
      bool canAppend =
        (bit == m_b) || //new bit is same as previous bit
        (0 == m_n); //no previous bit
      //flush previous bits if can't append
      if (!canAppend)
        finished();
      //append current bit
      m_b = bit;
      ++m_n;
    }
  }

  //private helper method
  bool getbit(byte b, int i)
  {
    //TODO return the bit value using a mask
  }
}

当您编写代码时，不要忘记使用各种输入数据对其进行测试，包括特殊情况（包括例如一个字节中具有相同值的所有位）。

于 2009-01-18T17:14:46.817 回答