LeetCode 476. 數字的補數
本篇文章特點：利用 熟悉題目的解法 對 陌生問題進行解決，所以很容易理解
先看題目，方便講解，題目如下：
對整數的二進制表示取反（0 變 1 ，1 變 0）后，再轉換為十進制表示，可以得到這個整數的補數，
例如，整數 5 的二進制表示是 "101" ，取反后得到 "010" ，再轉回十進制表示得到補數 2 ，
給你一個整數 num ，輸出它的補數，
示例 1：
輸入：num = 5
輸出：2
解釋：5 的二進制表示為 101（沒有前導零位），其補數為 010，所以你需要輸出 2 ，
示例 2：
輸入：num = 1
輸出：0
解釋：1 的二進制表示為 1（沒有前導零位），其補數為 0，所以你需要輸出 0 ，
提示：
1 <= num < 231
拋磚
能想到的就是位運算了，對于我這種不熟悉 ( 按位或 | ) (按位與 &) (按位異或 ^ ) 的人來說，就需要拿 5(二進制補碼:101)這個數慢慢試了，可以發現 如果是 1111 和 101 采用 異或^ 就可以得到 目標值 2(010);
嘗試寫了一下，發現 對于 5來說 除了 101 前面還有許多 0 ，按位異或一定會改變前面的 0 ，所以不可行，
雞肋的總結
也做了幾個LeetCode題，總結出一個雞肋的結論—很容易想出來的方法一般不會成功，
接下來就要想那種需要耗費一定的時間和空間的方法了，激進的方法（一步到位）已經不能成功了，就采用保守的方法了 — 遍歷各位二進制，并且進行修改，
引玉
遍歷二進制 是一個很基礎很基礎的方法，本人將其收集在一個常用的模板中，所以用這種方式肯定十拿九穩，這就是我所說的 利用 熟悉題目的解法 對 陌生問題進行解決，（稍微擴展下，不僅遍歷二進制，甚至可以遍歷所有進制，常見的就是 十進制 如：123 分解為 1 2 3）
既然已經知道大體方向(遍歷二進制).接下來就是詳細講解細節了，
1.遍歷的方式有兩種(一直取余%) ，或者一直和 (1<<i) 按位與& ，這里大可以在無效0出現之前 就結束遍歷，
所以采用第一種，選擇 do while 是因為 第一個二進制位 需要直接考慮，否則一些特殊情況進入不了while
2. 當我們能一個一個遍歷二進制位，就可以針對每一位進行修改了，
2.1 因為不能修改原數字，所以就要創建一個新的數字，這里設定為 res = 0 .因為對于 每一位 0 變成 1更
容易，
2.2 遍歷到那一位，想要把0變成1，常見的方式是 1 和 0 按位或 | ，但是這個1需要一直在遍歷的位置，所以
設定另一個變數x=1.跟隨遍歷的程序，所以遍歷的每一次中都操作 1 << 1(可以采用 x*2來代替) 就能跟隨遍歷
的那一位了，
2.3 在遍歷的框架中 加入 2.1 2.2 的對應操作就可以了，
class Solution {
public int findComplement(int num) {
/*1.創建一個 x = 1 ，res = 0；
2.從左向右遍歷 二進制補碼，每遍歷一次，將x 二進制左移一位
2.1遍歷程序中，遇到num該位置是0，就將res 和 x進行按位或
*/
int x = 1, res = 0;
do {
int temp = num % 2;
if (temp == 0) {
res = res | x;
}
x *= 2;
num /= 2;
} while (num / 2 != 0);
return res;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/325646.html
標籤：其他