leetcode-剑指offer【15】-二进制中1的个数

[博客链接]

一个菜🐔的学习之路

掘金首页

[题目描述]

[题目链接]

leetcode题目链接

[github地址]

代码链接

[思路介绍]

思路一：暴力法+位运算

  • 通过判断 n & 1 == 1 判断末位是否为1
  • 然后无符号右移即可
  • 这个的测试用例真的挺奇怪的居然偶尔会TLE
  1. public int hammingWeight(int n) {
  2.     int res = 0;
  3.     while (n != 0) {
  4.         if ((n & 1) == 1) {
  5.             res += 1;
  6.         }
  7.         n >>>= 1;
  8.     }
  9.     return res;
  10. }

时间复杂度O(k)k最大32

思路二：java.Integer库的调用

  1. public int hammingWeight(int n) {
  2.            return Integer.bitCount(n);
  3.         }

时间复杂度O(logk)k最大32

思路三：位运算的奇思妙想

  • n &= (n-1) 会将最后位1变成0
  • n-1表示把最后一位的1右边全变成1，当前位变为1，然后与n与运算则表示当前位右侧以及当前位都变成0
  • 计算次数则为1的个数

leetcode-剑指offer【15】-二进制中1的个数 - 图1

  1. public int hammingWeight(int n) {
  2.             int res = 0;
  3.             while (n != 0) {
  4.                 n &= n - 1;
  5.                 res += 1;
  6.             }
  7.             return res;
  8.         }

时间复杂度O(k)-主要优化的是删除了中间为0的运算

思路四：思路一的多种写法

  • 虽然我也没看出来啥优化
  1. public int hammingWeight(int n) {
  2.             int ret = 0;
  3.             for (int i = 0; i < 32; i++) {
  4.                 if ((n & (1 << i)) != 0) {
  5.                     ret += 1;
  6.                 }
  7.             }
  8.             return ret;
  9.         }

时间复杂度O(k),可能是leetcode更信任常量？

思路五：思路一的多种写法

  1. public int hammingWeight(int n) {
  2.             int res = 0;
  3.             while (n != 0) {
  4.                 res += (n & 1);
  5.                 n >>>= 1;
  6.             }
  7.             return res;
  8.         }

时间复杂度O(k)

思路六-logk写法

  • 这个是java库的写法
  • 手写了一次运算过程

leetcode-剑指offer【15】-二进制中1的个数 - 图2

简化后运算过程

leetcode-剑指offer【15】-二进制中1的个数 - 图3

  1. public int hammingWeight(int i) {
  2.     // HD, Figure 5-2
  3.     i = i - ((i >>> 1) & 0x55555555);
  4.     i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
  5.     i = (i + (i >>> 4)) & 0x0f0f0f0f;
  6.     i = i + (i >>> 8);
  7.     i = i + (i >>> 16);
  8.     return i & 0x3f;
  9. }

这种做法没有宫水三叶 题解中的具有通用性

  1. public int hammingWeight(int n) {
  2.         n = (n & 0x55555555) + ((n >>> 1)  & 0x55555555);
  3.         n = (n & 0x33333333) + ((n >>> 2)  & 0x33333333);
  4.         n = (n & 0x0f0f0f0f) + ((n >>> 4)  & 0x0f0f0f0f);
  5.         n = (n & 0x00ff00ff) + ((n >>> 8)  & 0x00ff00ff);
  6.         n = (n & 0x0000ffff) + ((n >>> 16) & 0x0000ffff);
  7.         return n;
  8.     }

时间复杂度O(logk)k最大32

这做法我印象里做过，但是具体忘记了哪道题了后续会补