在堆栈中查找最长的字符序列

Question

嗨,我正在解决一个问题:

给定一个基数为10的整数n,将其转换为二进制(base-2).然后查找并打印基数为10的整数,表示n的二进制表示中连续1的最大数.例如,对于n = 5,base-2 = 101,因此输出应为1,对于n = 439,base-2 = 110110111,因此输出应为3.

下面是我的代码解决方案:

class Solution {

    static int CalcBinary (int n) {
        Stack<int> binRep = new Stack<int>();
        while (n > 0) {
            int i = n%2;
            binRep.Push (i);
            n = n/2;
        }
        int oldCount = 0, newCount = 0;
        while (binRep.Count > 0){
            int val = binRep.Pop();
            if (val == 1) {
                newCount++;
            } else {
                if (newCount > oldCount) {
                    oldCount = newCount;
                }
                newCount = 0;
            }
        }
        return (newCount > oldCount) ? newCount : oldCount;
    }

    static void Main(String[] args) {
        int n = Convert.ToInt32(Console.ReadLine());
        Console.WriteLine (CalcBinary(n));
    }
}

代码运行正常并通过所有测试用例,例如n = 5,6,439等.只有问题是,如果有任何优化的解决方案来做同样的事情.其他人在此处发布了相同的问题,但对该问题的所有回复似乎与O(n)时间复杂度相同.另一件事是我可以使用数组而不是堆栈,但它会有任何区别吗？

Answer 1

public int CalcBinary(int n)
{
    int result = 0;
    int current = 0;
    for (int i = 0; i + result < 32 && (n >> i) != 0; i++)
    {
        if (((n >> i) & 1) == 1)
            current += 1;
        else
        {
            if (current > result) 
                result = current;
            current = 0;
        }
    }

    return result == 0 ? current : result;
}

我不太擅长大O算术,但我认为这个解决方案应该更快,因为我不使用任何其他类而是简单的位移.

如果不再有解决方案,我会提前停止(i + result < 32).

请注意,这仅适用于32位整数.对于64位调整上述条件.并且它仅适用于正值(例如,设置符号位可能会产生错误的结果111....111101).

更新:添加了(n >> i) != 0@ Scott-Chamberlain建议的条件(它检查是否还有1s).