问题

这是我在竞争性编程中面临的问题之一。

问题)您有一个输入字符串,它以二进制格式11100,您需要计算数字为零的步骤数.如果数字是odd -> subtract it by 1,如果even -> divide it by 2.

例如

28 - > 28/2

14 - > 14/2

7 - > 7-1

6 - > 6/2

3->3-1

2->2/2

1->1-1

0 – > STOP

步骤数=7

我提出了以下解决方案

 public int solution(String S) {
    // write your code in Java SE 8
    String parsableString = cleanString(S);
    int integer = Integer.parseInt(S, 2);
    return stepCounter(integer);
}

private static String cleanString(String S){
    int i = 0;
    while (i < S.length() && S.charAt(i) == '0')
        i++;
    StringBuffer sb = new StringBuffer(S);
    sb.replace(0,i,"");
    return sb.toString();
}

private static int stepCounter(int integer) {
    int counter = 0;
    while (integer > 0) {
        if (integer == 0)
            break;
        else {
            counter++;
            if (integer % 2 == 0)
                integer = integer / 2;
            else
                integer--;
        }
    }
    return counter;
}
 

这个问题的解决方案看起来非常简单和直接,但是这段代码的性能评估给了我一个大的ZERO.我的初步印象是将字符串转换为int是一个瓶颈,但没有找到更好的解决方案.任何人都可以向我指出这段代码的瓶颈,它在哪里可以大大改进?

  最佳答案

如果二进制数是奇数,最后一个(最不重要的)数字必须是1,所以减去1只是将最后一位数从1更改为0(重要的是,使数字甚至).

如果二进制数是偶数,最后一位数必须是0,除以零可以完全删除最后一个0.

所以步骤的数量是每1位数的两个步骤,每0位数的一个步骤 --1,因为当你得到最后0时,你不再除以2,你就停下来了。

这是一个简单的JavaScript(而不是Java)解决方案:

 let n = '11100';
n.length + n.replace(/0/g, '').length - 1;
 

只要再做一点工作,这也可以正确地处理前导零,如果需要的话。

  相同标签的其他问题

javastringalgorithmbinary
上一个问题:
下一个问题: