LeetCode演算法題-Binary Number with Alternating Bits（Java實現）
這是悅樂書的第292 次更新，第310 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第160題（順位題號是693）。給定正整數，檢查它是否具有交替位：即它的二進位制數的任意兩個相鄰位總是具有不同的值。例如：
輸入：5
輸出：true
說明：5的二進位制表示是：101
輸入：7
輸出：false
說明：7的二進位制表示為：111。
輸入：11
輸出：false
說明：11的二進位制表示是：1011。
輸入：10
輸出：true
說明：10的二進位制表示是：1010。
本次解題使用的開發工具是eclipse，jdk使用的版本是1.8，環境是win7 64位系統，使用Java語言編寫和測試。
02 第一種解法
最直接解法，將正整數轉為二進位制字串，藉助包裝類Integer的toBinaryString方法實現，然後對字串的字元進行遍歷，如果相鄰的字元相等了，直接返回false。
public boolean hasAlternatingBits(int n) {
String str = Integer.toBinaryString(n);
for (int i=1; i<str.length(); i++) {
if (str.charAt(i) == str.charAt(i-1)) {
return false;
}
}
return true;
}
03 第二種解法
我們也可以觀察下為true的那些數，從1開始：
1，其二進位制數為：1
2，其二進位制數為：10
5，其二進位制數為：101
10，其二進位制數為：1010
通過觀察這些二進位制數，我們可以發現，它們可以看做是10和1的組合體。對於10，可以有零個，也可以有多個，而對於1，只可能是0個或者1個，多了就重複了。因此，我們也可以使用正則表示式來解。
匹配多字元10，使用圓括號；匹配0次或者多次，使用星號，或者{0,}。
匹配1，可以直接寫1，匹配0次或者1次，使用問號，或者{0,1}。
public boolean hasAlternatingBits(int n) {
String str = Integer.toBinaryString(n);
//(10){0,}1{0,1} 這樣寫也是可以的
return str.matches("(10)*1?");
}
04 第三種解法
我們也可以不將其轉為二進位制字串，直接使用位運算來判斷，藉助與(&)運算。與運算的規則是對應位都為1才為1，否則對應位為0。每次將n和1進行與運算，看它最後一位是0還是1，使用一個臨時變數，將其二進位制數的最後一位記錄下來，與當前的最後一位比較，如果相同了，就返回false。
public boolean hasAlternatingBits(int n) {
// 記錄每次操作的最後一位
int prev = -1;
while (n > 0) {
if ((n&1) == 1) {
if (prev == 1) {
return false;
}
prev = 1;
} else {
if (prev == 0) {
return false;
}
prev = 0;
}
// 每次將其右移一位
n >>= 1;
}
return true;
}
05 第四種解法
對於第三種解法，我們還可以再簡化下。上面我們每進行一次計算都會去判斷一下，是否等於上一次計算的最後一位，這裡我們將其移動到while迴圈的判斷條件中去，反過來處理，先得到下一次正確的最後一位，看其符不符合。依舊使用一個臨時變數，迴圈繼續的條件變成了當前最後一位是否等於預先設定好的那個數，在迴圈內部，我們對temp變數進行變動，取每次計算的相反值，如果計算為0，那麼temp就為1，表示下一次參與計算後的最後一位要為1，否則就去判斷n是否已經等於0了。
public boolean hasAlternatingBits(int n) {
int temp = n&1;
while ((n&1) == temp) {
temp = 1-temp;
n >>= 1;
}
return n == 0;
}
06 第五種解法
此解法利用了n的二進位制數0與1交替的特徵，與自身右移一位後的數進行錯位相加，變成了一個全部由1組成的二進位制數，然後再利用檢測是否全為1的方法，判斷是否符合題意。而檢測的方法就是，加1後和自身進行與運算，因為如果該二進位制數全為1，加1後就轉為了首位為1，其餘位都是0的二進位制數，再與原來的自己進行與運算，運算的結果就是0。比如5，5+5/2變成了7，二進位制數為111，加1後，其二進位制數變為了1000，兩者進行與運算後，得到的結果是0。除以2和右移一位的效果等同。
public boolean hasAlternatingBits(int n) {
// ((n + (n >> 1) + 1) & (n + (n >> 1))) == 0 這樣寫也行
return ((n+n/2+1) & (n+n/2)) == 0;
}
07 小結
演算法專題目前已日更超過四個月 ，演算法題文章160 +篇，公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞，獲取系列文章合集。
以上就是全部內容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！