反应式扩展:获取二进制数的“孔径”

本文关键字：孔径 二进制数 扩展 获取 反应式 | 更新日期: 2023-09-27 18:32:04

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

这就是问题所在：

正整数 N 内的孔径是 二进制表示中的连续零，周围由 两端的。

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

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

为了简化起见，我尝试将其应用于"1000010001"之类的字符串，而不是二进制表示形式。

无论如何，我不介意复杂性部分，只是我想知道一种"优雅"的方式来做到这一点。

反应式扩展:获取二进制数的“孔径”

显然，在 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<T>版本！

我不知道如何在这里使用 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

我同意为此使用 Rx 是愚蠢的。使用 LINQ 解决问题同样愚蠢，但既然是 Rx 的大哥，你不妨。

与James World的回答一样，这只是为了娱乐目的。 

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
}

现在我觉得很脏。

相关文章：