問題

這是我在競爭性程式設計中面臨的問題之一。

問題)您有一個輸入字串,它以二進位制格式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
上一個問題:
下一個問題: