大厂算法面试之 leetcode 精讲 9.位运算
视频教程（高效学习）:点击学习
目录：
1.开篇介绍
2.时间空间复杂度
3.动态规划
4.贪心
5.二分查找
6.深度优先&广度优先
7.双指针
8.滑动窗口
9.位运算
10.递归&分治
11剪枝&回溯
12.堆
13.单调栈
14.排序算法
15.链表
16.set&map
17.栈
18.队列
19.数组
20.字符串
21.树
22.字典树
23.并查集
24.其他类型题
位运算基础：
程序中所有的数载计算机内存中都是以二进制存储的，位运算就是直接对整数在内存中的二进制进行操作，由于直接在内存中进行操作，不需要转成十进制，因此处理速度非常快
常见位运算
x & 1 === 0 //判断奇偶x & (x - 1) //清除最右边的1x & -x //得到最右边的1
复制代码
方法 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：优化循环的过程
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; }}
复制代码
方法 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 的幂的约数
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; }}
复制代码
方法 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.动态规划
所以状态转移方程就是bits[i] = bits[i & (i - 1)] + 1，不断循环计算出从 1-n 中每个数二进制中 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; }}
复制代码
方法 1.计数
js：
var findTheDifference = function(s, t) { const cnt = new Array(26).fill(0); for (const ch of s) {//循环字符串s 统计每个字符的个数 cnt[ch.charCodeAt() - 'a'.charCodeAt()]++; } for (const ch of t) {//循环字符串t 每出现一次s中的字符 就让相应字符的数量减少1 cnt[ch.charCodeAt() - 'a'.charCodeAt()]--; if (cnt[ch.charCodeAt() - 'a'.charCodeAt()] < 0) {//如果字符减少到了小于0 则这个字符就是答案 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.求和
js：
var findTheDifference = function(s, t) { let as = 0, at = 0; for (let i = 0; i < s.length; i++) {//统计字符串s中字符Unicode值的总和 as += s[i].charCodeAt(); } for (let i = 0; i < t.length; i++) {//统计字符串t中字符Unicode值的总和 at += t[i].charCodeAt(); } return String.fromCharCode(at - as);//两个和的差 就是不同的字符};
复制代码
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.位运算
js：
//s = "abcd", t = "abcde"var findTheDifference = function(s, t) { let ret = 0;//循环s和t 不断异或 相同元素异或等于0 所以唯一不同的字符最后会留下来 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; }}
复制代码
方法 1.排序：在循环数组，看后一个数是不是比前一个大 1
方法 2.哈希表：将数组中的元素插入哈希表，然后循环 0～nums.length-1 中的数是不是都在哈希表中
方法 3.求和：0～nums.length-1 求和减去 nums 中的和
方法 4:位运算
思路：相同的数异或为 0
复杂度：时间复杂度O(n)，空间复杂度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++) {//相同的数异或为0 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; }}
复制代码
评论