大廠算法面試之leetcode精講9.位運(yùn)算
視頻教程（高效學(xué)習(xí)）:點(diǎn)擊學(xué)習(xí)
目錄：
位運(yùn)算基礎(chǔ)：
程序中所有的數(shù)載計(jì)算機(jī)內(nèi)存中都是以二進(jìn)制存儲(chǔ)的，位運(yùn)算就是直接對(duì)整數(shù)在內(nèi)存中的二進(jìn)制進(jìn)行操作，由于直接在內(nèi)存中進(jìn)行操作，不需要轉(zhuǎn)成十進(jìn)制，因此處理速度非?？?/p>
常見位運(yùn)算
x & 1 === 0 //判斷奇偶x & (x - 1) //清除最右邊的1x & -x //得到最右邊的1191. 位1的個(gè)數(shù) （easy）
方法1：循環(huán)每個(gè)二進(jìn)制位
- 思路：直接循環(huán)二進(jìn)制中的每一位，判斷是否為1，統(tǒng)計(jì)1的個(gè)數(shù)
- 復(fù)雜度分析：時(shí)間復(fù)雜度
O(k)，k=32?？臻g復(fù)雜度為O(1)
Js:
var hammingWeight = function(n) { let ret = 0; for (let i = 0; i < 32; i++) { if ((n & (1 << i)) !== 0) {//讓1不斷左移 判斷該位是否為1 ret++; } } return ret;};Java:
public class Solution { public int hammingWeight(int n) { int ret = 0; for (int i = 0; i < 32; i++) { if ((n & (1 << i)) != 0) { ret++; } } return ret; }}方法2：優(yōu)化循環(huán)的過(guò)程
- 思路：巧用二進(jìn)制公式
x&(x-1)表示去掉二進(jìn)制中最右邊的第一個(gè)1，加速循環(huán)過(guò)程 - 復(fù)雜度分析：時(shí)間復(fù)雜度為
O(k)，k為二進(jìn)制中1的個(gè)數(shù)，最壞的情況下所有位都是1?？臻g復(fù)雜度是O(1)
js:
var hammingWeight = function(n) { let ret = 0; while (n) { n &= n - 1;//不斷消掉最右邊的1 ret++; } return ret;};java:
public class Solution { public int hammingWeight(int n) { int ret = 0; while (n != 0) { n &= n - 1; ret++; } return ret; }}231. 2 的冪（easy）
方法1.二進(jìn)制
- 思路：一個(gè)數(shù)是2的冪需要滿足這個(gè)數(shù)的二進(jìn)制中只有一個(gè)1，也就是需要滿足這個(gè)數(shù)>0，同時(shí)消除唯一的一個(gè)1之后就是0
- 復(fù)雜度：時(shí)間復(fù)雜度
O(1)。空間復(fù)雜度O(1)
Js:
var isPowerOfTwo = function(n) { return n > 0 && (n & (n - 1)) === 0;};Java:
class Solution { public boolean isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }}方法2.是否為最大 2的冪的約數(shù)
- 思路：最大的2的冪為
2^30 = 1073741824， 判斷 n 是否是2^30的約數(shù)即可。 - 復(fù)雜度:時(shí)間復(fù)雜度
O(1)。空間復(fù)雜度O(1)
js:
var isPowerOfTwo = function(n) { const MAX = 1 << 30; return n > 0 && MAX % n === 0;};Java:
class Solution { static final int MAX = 1 << 30; public boolean isPowerOfTwo(int n) { return n > 0 && MAX % n == 0; }}338. 比特位計(jì)數(shù) (easy)
方法1.循環(huán)
- 思路：循環(huán)
0-n，計(jì)算每個(gè)數(shù)二進(jìn)制中1的個(gè)數(shù)。 - 復(fù)雜度：時(shí)間復(fù)雜度
O(nk)，k一個(gè)整數(shù)統(tǒng)計(jì)二進(jìn)制1的復(fù)雜度，最壞的情況下是k=32?？臻g復(fù)雜度是O(1)
js:
var countBits = function(n) { const bits = new Array(n + 1).fill(0); for (let i = 0; i <= n; i++) { bits[i] = countOnes(i); } return bits};const countOnes = (x) => { let ones = 0; while (x > 0) { x &= (x - 1); ones++; } return ones;}Java:
class Solution { public int[] countBits(int n) { int[] bits = new int[n + 1]; for (int i = 0; i <= n; i++) { bits[i] = countOnes(i); } return bits; } public int countOnes(int x) { int ones = 0; while (x > 0) { x &= (x - 1); ones++; } return ones; }}方法2.動(dòng)態(tài)規(guī)劃
- 思路：
bits[i]表示i的二進(jìn)制中1的個(gè)數(shù)，那么bits[i-1]就是bits[i]拿掉一個(gè)1之后的值，i & (i - 1)就是去掉最低位的一個(gè)1.
所以狀態(tài)轉(zhuǎn)移方程就是bits[i] = bits[i & (i - 1)] + 1，不斷循環(huán)計(jì)算出從1-n中每個(gè)數(shù)二進(jìn)制中1的個(gè)數(shù)即可
- 復(fù)雜度：時(shí)間復(fù)雜度
O(n)?？臻g復(fù)雜度是O(1)
Js:
var countBits = function(n) { const bits = new Array(n + 1).fill(0); for (let i = 1; i <= n; i++) { bits[i] = bits[i & (i - 1)] + 1; } return bits;};Java:
class Solution { public int[] countBits(int n) { int[] bits = new int[n + 1]; for (int i = 1; i <= n; i++) { bits[i] = bits[i & (i - 1)] + 1; } return bits; }}389. 找不同（ easy）
方法1.計(jì)數(shù)
- 思路：循環(huán)字符串s 統(tǒng)計(jì)每個(gè)字符的個(gè)數(shù)，循環(huán)字符串t 每出現(xiàn)一次s中的字符 就讓相應(yīng)字符的數(shù)量減少1，如果字符減少到了小于0 則這個(gè)字符就是答案
- 復(fù)雜度：時(shí)間復(fù)雜度
O(n)，n是字符串的長(zhǎng)度?？臻g復(fù)雜度O(k)，k是字符集的大小
js：
var findTheDifference = function(s, t) { const cnt = new Array(26).fill(0); for (const ch of s) {//循環(huán)字符串s 統(tǒng)計(jì)每個(gè)字符的個(gè)數(shù) cnt[ch.charCodeAt() - a.charCodeAt()]++; } for (const ch of t) {//循環(huán)字符串t 每出現(xiàn)一次s中的字符 就讓相應(yīng)字符的數(shù)量減少1 cnt[ch.charCodeAt() - a.charCodeAt()]--; if (cnt[ch.charCodeAt() - a.charCodeAt()] < 0) {//如果字符減少到了小于0 則這個(gè)字符就是答案 return ch; } } return ;};java：
class Solution { public char findTheDifference(String s, String t) { int[] cnt = new int[26]; for (int i = 0; i < s.length(); ++i) { char ch = s.charAt(i); cnt[ch - a]++; } for (int i = 0; i < t.length(); ++i) { char ch = t.charAt(i); cnt[ch - a]--; if (cnt[ch - a] < 0) { return ch; } } return ; }}方法2.求和
- 思路：統(tǒng)計(jì)字符串s和t中字符Unicode的總和，兩個(gè)和的差 就是不同的字符
- 復(fù)雜度：時(shí)間復(fù)雜度
O(n)。空間復(fù)雜度O(1)
js：
var findTheDifference = function(s, t) { let as = 0, at = 0; for (let i = 0; i < s.length; i++) {//統(tǒng)計(jì)字符串s中字符Unicode值的總和 as += s[i].charCodeAt(); } for (let i = 0; i < t.length; i++) {//統(tǒng)計(jì)字符串t中字符Unicode值的總和 at += t[i].charCodeAt(); } return String.fromCharCode(at - as);//兩個(gè)和的差 就是不同的字符};java：
class Solution { public char findTheDifference(String s, String t) { int as = 0, at = 0; for (int i = 0; i < s.length(); ++i) { as += s.charAt(i); } for (int i = 0; i < t.length(); ++i) { at += t.charAt(i); } return (char) (at - as); }}方3.位運(yùn)算
- 思路：循環(huán)s和t 不斷異或 相同元素異或等于0 所以唯一不同的字符最后會(huì)留下來(lái)
- 復(fù)雜度：時(shí)間復(fù)雜度
O(n)?？臻g復(fù)雜度O(1)
js：
//s = "abcd", t = "abcde"var findTheDifference = function(s, t) { let ret = 0;//循環(huán)s和t 不斷異或 相同元素異或等于0 所以唯一不同的字符最后會(huì)留下來(lái) for (const ch of s) { ret ^= ch.charCodeAt(); } for (const ch of t) { ret ^= ch.charCodeAt(); } return String.fromCharCode(ret);};java：
class Solution { public char findTheDifference(String s, String t) { int ret = 0; for (int i = 0; i < s.length(); ++i) { ret ^= s.charAt(i); } for (int i = 0; i < t.length(); ++i) { ret ^= t.charAt(i); } return (char) ret; }}268. 丟失的數(shù)字 （easy）
方法1.排序：在循環(huán)數(shù)組，看后一個(gè)數(shù)是不是比前一個(gè)大1
方法2.哈希表：將數(shù)組中的元素插入哈希表，然后循環(huán)0～nums.length-1中的數(shù)是不是都在哈希表中
方法3.求和：0～nums.length-1求和減去nums中的和
方法4:位運(yùn)算
- 思路：相同的數(shù)異或?yàn)?
- 復(fù)雜度：時(shí)間復(fù)雜度
O(n)，空間復(fù)雜度O(1)
js:
//nums = [3,0,1]//index = 0,1,2var missingNumber = function (nums) { let missing = nums.length for (let i = 0; i < nums.length; i++) {//相同的數(shù)異或?yàn)? missing = missing ^ nums[i] ^ (i) } return missing}java
class Solution { public int missingNumber(int[] nums) { int missing = nums.length; for (int i = 0; i < nums.length; i++) { missing ^= i ^ nums[i]; } return missing; }}
