LeetCode演算法題-Number Complement(Java實現-五種解法)
這是悅樂書的第240 次更新,第253 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第107題(順位題號是476)。給定正整數,輸出其補碼數。補充策略是翻轉其二進位制表示的位。例如:
輸入:5
輸出:2
說明:5的二進位制表示為101(無前導零位),其補碼為010,因此需要輸出2。
輸入:1
輸出:0
說明:1的二進位制表示形式為1(無前導零位),其補碼為0,因此需要輸出0。
注意:
-
保證給定的整數適合32位有符號整數的範圍。
-
您可以假設整數的二進位制表示中沒有前導零位。
本次解題使用的開發工具是eclipse,jdk使用的版本是1.8,環境是win7 64位系統,使用Java語言編寫和測試。
02 第一種解法
先將正整數轉為二進位制字串,然後變成字元陣列,將其中的0變成1,1變成0,再將字元陣列變為字串,最後將字串轉為二進位制數。
public int findComplement(int num) { String str = Integer.toBinaryString(num); char[] arr = str.toCharArray(); for (int i=0; i<arr.length; i++) { if (arr[i] == '0') { arr[i] = '1'; } else { arr[i] = '0'; } } return Integer.parseInt(String.valueOf(arr), 2); }
03 第二種解法
我們可以仔細觀察題目所給的示例:
5表示的二進位制數為101,最後的結果是2,所表示的二進位制數為10,如果我們將其前導0補齊,就會發現101通過計算後要得到010,那麼需要藉助怎樣的計算呢?
藉助位運算,101^111 = 010,我們使用二進位制數111和101做異或運算就可以得到最後的結果。
因此,我們需要獲取num表示的二進位制數長度,來組成一個由1組成新二進位制數(長度和num表示的二進位制數一致),再將兩數做異或運算即可。
異或運算的規則是兩邊的對應位不同時,取1,否則取0。
public int findComplement2(int num) { String str = Integer.toBinaryString(num); String str2 = ""; for (int i=0; i<str.length(); i++) { str2 += "1"; } int res = Integer.parseInt(str2, 2); return num^res; }
04 第三種解法
還是第二種解法的思路,只不過將字串操作換為了位運算操作,我們先將num右移,計算其二進位制數有多少位,記為i,然後再對1進行左移i位,移完後得到的二進位制數是1個1加上i個0,而不是i個1,所以我們需要減去1使其變成i個1,最後和num做異或運算並返回其結果。
public int findComplement3(int num) { if (num == 0) { return 1; } int i = 0; while ((num>>i) != 0) { i++; } int res = (1<<i)-1; return num^res; }
05 第四種解法
還是第二種解法的思路,與第三種解法的位運算不同,藉助包裝類和位運算來一起完成計算,Integer類的highestOneBit方法,取的是其二進位制數左側的最高位1,因為本題的輸入引數為正數,可以不用考慮負數、反碼、補碼的問題。獲得最高位所表示的整數後,再左移一位,然後再減1,最後還是和num進行異或運算,並返回結果。
public int findComplement4(int num) { if (num == 0) { return 1; } int res = (Integer.highestOneBit(num)<<1) - 1; return num^res; }
06 第五種解法
還有一種做法,也藉助位運算,使用與(&)運算,在進行與運算之前,我們先要把與運算兩邊的數準備好。左邊的數是對num進行非運算,右邊的數還是需要藉助Integer類的highestOneBit方法,獲取最高位1所表示的整數再減去1,然後兩個新的數進行與運算,並返回結果。以題目中的5為例:
左邊:對5進行非運算,得到-6
右邊:5的二進位制數最高位1表示為整數4,減去1為3
3
00000000000000000000000000000011
-6
10000000000000000000000000001010
當相同的位上均為1時結果為1,否則結果為0
00000000000000000000000000000010
也就是整數2。
public int findComplement5(int num) { return ~num & (Integer.highestOneBit(num) - 1); }
07小結
演算法專題目前已日更超過三個月,演算法題文章107 +篇,公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞,獲取系列文章合集。
以上就是全部內容,如果大家有什麼好的解法思路、建議或者其他問題,可以下方留言交流,點贊、留言、轉發就是對我最大的回報和支援!