LeetCode.1009-十進制數的補碼(Complement of Base 10 Integer)

這是小川的第377次更新，第404篇原創

01 看題和準備

今天介紹的是LeetCode算法題中Easy級别的第238題（順位題号是1009）。每個非負整數N都具有二進制表示。例如，5可以二進制表示為

"101"

，11可以二進制表示為

"1011"

，依此類推。

請注意，除

N = 0

外，任何二進制表示中都沒有前導零。

二進制表示的補碼是将1改為0和将0改為1時得到的二進制數。例如，二進制中

"101"

的補碼是二進制的

"010"

。

對于給定的十進制數

N

，将其二進制表示的補碼作為十進制的整數傳回。

例如：

輸入：5

輸出：2

說明：5是二進制

"101"

，二進制補碼

"010"

，轉為十進制是2。

輸入：7

輸出：0

說明：7是二進制

"111"

"000"

，轉為十進制是0。

輸入：10

輸出：5

說明：10是二進制

"1010"

"0101"

，轉為十進制是5。

注意：

• 0 <= N < 10^9

02 第一種解法

題目的意思是将N轉為二進制，再求其二進制的補碼（0和1互換），再将轉換後的二進制補碼轉為十進制整數。

思路：利用異或位運算，例如5^7=2，那麼我們要找到7，而7的二進制為

111

，長度和5的二進制

101

相等，但是全為1，是以先将5轉為二進制字元串，使用一個32位長度的由1組成的字元串，截取對應長度的子串，再将截取出來的子串轉為十進制數，利用得到的十進制數和

N

做異或運算就可得到結果。

public int bitwiseComplement(int N) {
    String str = Integer.toBinaryString(N);
    String newStr = "11111111111111111111111111111111";
    newStr = newStr.substring(0, str.length());
    int num = Integer.valueOf(newStr, 2);
    return N^num;
}
           

03 第二種解法

思路：将

N

轉為二進制字元串，利用循環，将其中的0轉為1，1轉為0，變成新的二進制字元串，再将其轉為十進制整數。

public int bitwiseComplement2(int N) {
    String str = Integer.toBinaryString(N);
    StringBuilder sb = new StringBuilder();
    for (int i=0; i<str.length(); i++) {
        sb.append(str.charAt(i) == '0' ? '1' : '0');
    }
    return Integer.valueOf(sb.toString(), 2);
}
           

04 第三種解法

思路和第一種解法類似，隻是換了另外的方式來得到全是1的二進制數，全是1的二進制數可以通過1開頭後面跟0的二進制數減1得到，例如8的二進制數

1000

，8減去1得到7，7的二進制數是

111

，而8可以通過

1

左移位運算

3

得到（也可以累乘2三次得到）。

public int bitwiseComplement3(int N) {
    if (N < 2) {
        return N == 0 ? 1 : 0;
    }
    int num = 1;
    while (num <= N) {
        // 換成 num *= 2; 效果一樣
        num <<= 1;
    }
    return N^(num-1);
}
           

05 小結

算法專題目前已連續日更超過七個月，算法題文章244+篇，公衆号對話框回複【資料結構與算法】、【算法】、【資料結構】中的任一關鍵詞，擷取系列文章合集。

以上就是全部内容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，好看、留言、轉發就是對我最大的回報和支援！