被动扩展：获取二进制数的“光圈”

Question

一个朋友提出了这个挑战。只是为了训练，我试图使用反应式扩展来解决它，但我没有运气。这并不奇怪，因为我还是Rx的新手。

这就是问题所在：

正整数N内的孔径是其二进制表示中的任意连续零的最大序列，其两端被1包围。

例如，数字9具有二进制表示1001，并且包含长度为2的光圈。数字529具有二进制表示100001001，包含两个光圈：一个是长度4，一个是长度3。数字20具有二进制表示10100，包含一个长度为1的光圈。数字15有二进制表示1111，没有光圈。编写一个函数：类Aperture{public int Aperture（int N）；}给定正整数N，返回其最长光圈的长度。如果N不包含光圈，则函数应返回0。　 假设：N是[1..2147483647]复杂度范围内的整数：算法时间复杂度为O（log（N））；

算法空间复杂度为O（1）（最坏情况——不计算输入参数）

为了简化，我尝试将其应用于“100001001”之类的字符串，而不是二进制表示。

不管怎样，我不介意复杂的部分，只是我想知道一种“优雅”的方法来做这件事。

Answer 1

我同意用Rx来做这件事是愚蠢的。使用LINQ解决这个问题同样愚蠢，但既然它是Rx的老大哥，你也可以这么做。

正如詹姆斯·沃尔德的回答一样，这只是出于娱乐目的。

public int Aperture(int input)
{
    var binaryString = Convert.ToString(input, 2);

    // The accumulator is an integer array maintaining
    // the count of '0's since the last seen '1'.
    // Whenever a '1' is encountered, a new count
    // of zero is added at the end of the array.
    // Whenever a '0' is encountered, the last
    // count is incremented by one.
    var segments = binaryString.Aggregate(
        new [] { 0 },
        (acc, c) =>
            c == '0'
            ? acc
                .Take(acc.Length - 1)
                .Concat(new [] { acc[acc.Length - 1] + 1 })
                .ToArray()
            : acc
                .Concat(new [] { 0 })
                .ToArray()
    );

    return segments
        // If last segment count is non-zero, it was not
        // closed with a '1' and we want to exclude it.
        .Take(segments.Length - 1)
        .Max();
}

[TestMethod]
public void ApertureTest()
{
    Assert.AreEqual(2, Aperture(9));   // 1001,       Segments: 0, 2, 0
    Assert.AreEqual(4, Aperture(529)); // 1000010001, Segments: 0, 4, 3, 0
    Assert.AreEqual(1, Aperture(20));  // 10100,      Segments: 0, 1, 2
    Assert.AreEqual(0, Aperture(15));  // 1111,       Segments: 0, 0, 0, 0
}

现在我觉得脏兮兮的。

Answer 2

我不知道怎么用Rx。我的解决方案展示了一种经典方法：

private static int Aperture(int n)
{
    int max = 0;
    int index = 0;
    int lastIndex = int.MaxValue;
    while (n != 0)
    {
        int bit;
        n = Math.DivRem(n, 2, out bit);
        if (bit != 0)
        {
            int length = index - lastIndex - 1;
            if (length > max)
                max = length;
            lastIndex = index;
        }
        index++;
    }
    return max;
}

测试结果：

Aperture(9)   = 2
Aperture(529) = 4
Aperture(20)  = 1
Aperture(15)  = 0

Answer 3

显然，在RX中解决这个问题没有太多意义，因为答案只能通过检查整个数字来推断——而且由于其他许多原因，它的效率非常低。。。

...但是为了你的娱乐：），这里有一个非常愚蠢的RX方式（不要在家里这样做！）：

public int Aperture(int input)
{
    var cs = Convert.ToString(input,2).ToCharArray().ToObservable();     

    return cs.Publish(ps => ps.Buffer(() => ps.Where(c => c == '1')))
    .Where(x => x.LastOrDefault() == '1')
    .Select(x => x.Count - 1).StartWith(0)
    .Max().Wait();
}

Aperture(9)   = 2
Aperture(529) = 4
Aperture(20)  = 1
Aperture(15)  = 0

我不知道我为什么要这样做：）但这里有另一种方式，有点朋克。我基本上是用一个2元组作为累加器。我在一边存储0的运行计数。如果我看到一个1，我会将计数复制到结果槽，如果它高于那里的值，然后重置计数。结果槽包含末端的光圈。

public int Aperture(int input)
{    
    var cs = Convert.ToString(input,2).ToCharArray().ToObservable();

    return cs.Aggregate(
        Tuple.Create(0,0), (acc, c) => c == '0'
            ? Tuple.Create(acc.Item1 + 1, acc.Item2)
            : Tuple.Create(0, Math.Max(acc.Item1, acc.Item2)
        )).Wait().Item2;
}

另外，只需删除ToCharArray（）。ToObservable（）和上面的Wait（），您就有了一个IEnumerable