关于leetcode个人解题总结:大厂算法面试之leetcode精讲9位运算

18次阅读

共计 4437 个字符，预计需要花费 12 分钟才能阅读完成。

大厂算法面试之 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) // 革除最左边的 1
x & -x // 失去最左边的 1

191. 位 1 的个数（easy）

办法 1：循环每个二进制位
  • 思路：间接循环二进制中的每一位，判断是否为 1，统计 1 的个数
  • 复杂度剖析：工夫复杂度O(k)，k=32。空间复杂度为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：优化循环的过程
  • 思路：巧用二进制公式 x&(x-1) 示意去掉二进制中最左边的第一个 1，减速循环过程
  • 复杂度剖析：工夫复杂度为O(k)，k 为二进制中 1 的个数，最坏的状况下所有位都是 1。空间复杂度是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. 二进制
  • 思路：一个数是 2 的幂须要满足这个数的二进制中只有一个 1，也就是须要满足这个数 >0，同时打消惟一的一个 1 之后就是 0
  • 复杂度：工夫复杂度O(1)。空间复杂度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 的幂的约数
  • 思路：最大的 2 的幂为 2^30 = 1073741824，判断 n 是否是 2^30 的约数即可。
  • 复杂度: 工夫复杂度O(1)。空间复杂度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. 比特位计数 (easy)

办法 1. 循环
  • 思路：循环0-n，计算每个数二进制中 1 的个数。
  • 复杂度：工夫复杂度O(nk)，k 一个整数统计二进制 1 的复杂度，最坏的状况下是 k =32。空间复杂度是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. 动静布局
  • 思路：bits[i]示意 i 的二进制中 1 的个数，那么 bits[i-1] 就是 bits[i] 拿掉一个 1 之后的值，i & (i - 1)就是去掉最低位的一个 1.

所以状态转移方程就是bits[i] = bits[i & (i - 1)] + 1，一直循环计算出从 1 - n 中每个数二进制中 1 的个数即可

  • 复杂度：工夫复杂度O(n)。空间复杂度是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. 计数
  • 思路：循环字符串 s 统计每个字符的个数，循环字符串 t 每呈现一次 s 中的字符 就让相应字符的数量缩小 1，如果字符缩小到了小于 0 则这个字符就是答案
  • 复杂度：工夫复杂度O(n)，n 是字符串的长度。空间复杂度O(k)，k 是字符集的大小

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. 求和
  • 思路：统计字符串 s 和 t 中字符 Unicode 的总和，两个和的差 就是不同的字符
  • 复杂度：工夫复杂度O(n)。空间复杂度O(1)

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. 位运算
  • 思路：循环 s 和 t 一直异或 雷同元素异或等于 0 所以惟一不同的字符最初会留下来
  • 复杂度：工夫复杂度O(n)。空间复杂度O(1)

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;
    }
}

268. 失落的数字（easy）

办法 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,2
var 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;
    }
}

正文完
Leetcode个人解题总结
2021-11-29
 0
关于leetcode个人解题总结:刷题11删除排序链表中的重复元素
关于leetcode个人解题总结:LeetCode-Hot100-510
关于leetcode个人解题总结:LeetCode-Hot1001115
关于leetcode个人解题总结:golangleetcode初级爬楼梯买卖股票的最佳时机