算法简单题,吾辈重拳出击 - 前 n 个数字二进制中 1 的个数

简介: 最近做的题,明眼人一看都能知道大都和动态规划 DP 有关,因为就是从动态规划分类下抽取的简单题,有的题在剑指 offer 系列中是简单题,但是在力扣主列表里确实中等难度的题目。简单与难,也并非是绝对的,每个人的感受都会不同。更重要的是,通过这些题构建基础的算法思路,建立信心。

image.png

最近做的题,明眼人一看都能知道大都和动态规划 DP 有关,因为就是从动态规划分类下抽取的简单题,有的题在剑指 offer 系列中是简单题,但是在力扣主列表里确实中等难度的题目。


简单与难,也并非是绝对的,每个人的感受都会不同。更重要的是,通过这些题构建基础的算法思路,建立信心。


动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题,它们的结果都逐渐被计算并被保存,从简单的问题直到整个问题都被解决。因此,动态规划保存递归时的结果,因而不会在解决同样的问题时花费时间。


动态规划 => 子问题 => 复用计算结果(通常伴随比较得值) => 递归(通常一遍循环即可)

image.png


OK,简单温故思路,再开始本篇题目:前 n 个数字二进制中 1 的个数

给定一个非负整数 n ,请计算 0n 之间的每个数字的二进制表示中 1 的个数,并输出一个数组。


示例 1:

输入: n = 2
输出: [0,1,1]
解释: 
0 --> 0
1 --> 1
2 --> 10


示例 2:

输入: n = 5
输出: [0,1,1,2,1,2]
解释:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101


第一反应



n=2,就要写出 0、1、2 的二进制,分别是 0 、1、10,分别有1的个数:0、1、1

n=3,就要写出 0、1、2、3 的二进制,分别是0、1、10、11,分别有1的个数:0、1、1、2

同理 n=4  => [0,1,1,2,1]

n=5 => [0,1,1,2,1,2]

......

设结果数组 res = []

暴力解法,算出每一个数字的二进制有几个1,然后 push 进数组;


第二反应



怎么算出二进制有几个 1 ?

部分编程语言有相应的内置函数用于计算给定的整数的二进制表示中的 11 的数目,例如 Java 的 Integer.bitCount、C++ 的 _ _builtin_popcount、Go 的 bits.OnesCount 等;


在 javascript 没有这个方法,所以需要我们自己写一个。

这里需要用到与操作 —— “&”


x = x & (x-1) 用于去除整数 x 二进制最右边的 1,递进移除,进行计数。

每次移除最右侧的 1 ,计数加一,直到全部做与操作,归为为0,输出统计次数;

举个例子,比如 x = 5 :


let x = 5; 
x = 5 & 4; 
// 5:     00000000000000000000000000000101
// 4:     00000000000000000000000000000100
第1次与结果 x:
// 00000000000000000000000000000100
x = x & 3 
// x:       00000000000000000000000000000100
// 3:       00000000000000000000000000000011
第2次与结果 x:
// 00000000000000000000000000000000
结果 = 0,结束,共计 2 次与操作,即 5 的二进制有 2 个 1;


算法表示为:


var countOnes = function(x){
    let count = 0;
    while(x > 0){
        x &= x - 1;
        // 统计次数
        count++;
    }
    return count;
}


第三反应



有了上一步的判断,拿到结果输入,轻而易举。


var countBits = function(n) {
    let res = []
    let countOnes = function(x){
        let count = 0;
        while(x > 0){
            x &= x - 1;
            // 统计次数
            count++;
        }
        return count;
    }
    for(let i = 0;i<=n;i++){
        res.push(countOnes(i))
    }
    return res
};

image.png


第四反应



上述算法需要对每个数都做 countOnes 操作,countOnes 操作里面又有一个循环,整个时间复杂度肯定是大于 O(n) 的;


还能不能再优化优化?动态规划 DP 来帮忙!

DP 就是将大问题抽象为一个小的具体问题,用公式表达。 通常由后向前导,遍历一次,时间复杂度更小。


看看官方解答思路:

此题中,对于正整数 x,如果可以知道最大的正整数 y,y≤x 且 y 是 2 的整数次幂,y 的二进制表示中只有最高位是 1,其余都是 0,此时称 y 为 x 「最高有效位」

则:bits[x] = bits [x - y] + 1


怎么理解?(OS: 不好理解。。。就先记住这个规则吧,欢迎大神解释QAQ)


// 比如正整数 5 ,小于等于 5 的最大正整数,且它是 2  的整数次幂,且只有最高位是 1,其余都为 0 的是数字 4;
bits[5] = bits [5 - 4] + 1 = bits[1] + 1 = 2
// 比如正整数 8,小于等于  7 的最大正整数,且它是 2  的整数次幂,且只有最高位是 1,其余都为 0 的是数字 4
bits[7] = bits [7 - 4] + 1 = bits[3] + 1 = 3
// 比如正整数 8,小于等于  8 的最大正整数,且它是 2  的整数次幂,且只有最高位是 1,其余都为 0 的是数字 8
bits[8] = bits [8 - 8] + 1 = bits[0] + 1 = 1


对照下面整个表可以试试,bits[x] = bits [x - y] + 1 这条抽象规则是对的。

image.png


那怎样知道这个 y 等于几?

y 的二进制表示中只有最高位是 1,其余都是 0,因此 y & (y−1)=0

for 循环一层 x,当 x & (x−1)=0 的时候,更新 y 值,循环完毕,y 值肯定是最大的那个。

最终实现:

var countBits = function(n) {
    let bits = new Array(n + 1).fill(0) // 结果数组要多一位
    let y = 0
    for(let i = 1; i <= n; i++) {
            if ((i & (i - 1)) == 0) {
                y = i;
            }
            bits[i] = bits[i - y] + 1;
    }
    return bits
}


第五反应



动态规划的另外一种解释!通透!!!❤


根据 i & (i-1) 计算i的二进制形式中1的个数

i & (i-1) 能将整数i的二进制形式最右边的1变为0

那么 整数i的二进制中1的个数比整数i&(i-1)的二进制中1的个数多1


var countBits = function (n) {
  let res = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    res[i] = res[i & (i - 1)] + 1;
  }
  return res;
};


第六反应



小结:


本题说简单,其实也并不简单~

与 & 操作得二进制 1 的个数在实际工作中并不多见,本瓜觉得这里更重要的是再次过一遍动态规划的简单题基础思维:


动态规划 => 子问题 => 复用计算结果(通常伴随比较得值、更新值) => 递归(通常一遍循环即可)


相关文章
|
6月前
|
算法 Java C++
试题 算法训练 6-2递归求二进制表示位数
试题 算法训练 6-2递归求二进制表示位数
45 0
|
6月前
|
算法 Java
算法编程(十四):颠倒二进制位
算法编程(十四):颠倒二进制位
53 0
|
监控 算法 安全
二进制转十进制算法简介及其在监控软件中的应用
在上网行为管理软件中,匈牙利算法主要应用于解决资源分配的问题。上网行为管理软件可能存在多个用户同时访问同一文件或打印机的情况,为了确保资源的公平共享,需要对资源进行分配
224 2
|
4月前
|
机器学习/深度学习 算法 计算机视觉
通过MATLAB分别对比二进制编码遗传优化算法和实数编码遗传优化算法
摘要: 使用MATLAB2022a对比了二进制编码与实数编码的遗传优化算法,关注最优适应度、平均适应度及运算效率。二进制编码适用于离散问题,解表示为二进制串;实数编码适用于连续问题,直接搜索连续空间。两种编码在初始化、适应度评估、选择、交叉和变异步骤类似,但实数编码可能需更复杂策略避免局部最优。选择编码方式取决于问题特性。
|
4月前
|
算法
Ngnix02 --- Ngnix的功能特性及常见功能,Ngnix常用的功能模块,有不同算法,根据不同算法进行转发,ip_hash、url_hash、fair,核心组成 ngnix二进制可执行文件
Ngnix02 --- Ngnix的功能特性及常见功能,Ngnix常用的功能模块,有不同算法,根据不同算法进行转发,ip_hash、url_hash、fair,核心组成 ngnix二进制可执行文件
|
5月前
|
算法 Java Go
【经典算法】LeetCode 67. 二进制求和(Java/C/Python3/Golang实现含注释说明,Easy)
【经典算法】LeetCode 67. 二进制求和(Java/C/Python3/Golang实现含注释说明,Easy)
65 2
|
5月前
|
算法
【经典LeetCode算法题目专栏分类】【第4期】BFS广度优先算法:单词接龙、最小基因变化、二进制矩阵中的最短路径
【经典LeetCode算法题目专栏分类】【第4期】BFS广度优先算法:单词接龙、最小基因变化、二进制矩阵中的最短路径
|
6月前
|
算法
【免费】面向多微网网络结构设计的大规模二进制矩阵优化算法
【免费】面向多微网网络结构设计的大规模二进制矩阵优化算法
|
监控 算法 安全
转:二进制转十进制算法在文档管理软件中的运用
二进制转十进制算法在文档管理软件中有多种应用。
79 0
|
6月前
|
算法
算法题 — 整数转二进制,查找其中1的数量
算法题 — 整数转二进制,查找其中1的数量
46 0