剑指 Offer（专项突击版）第3|4题

前言

• 现在前端要求变高了,找工作的时可能会碰上算法题,每天刷几道算法题做足预备,今天是《剑指 Offer（专项突击版）》第3|4题。

剑指 Offer II 003. 前 n 个数字二进制中 1 的个数

给定一个非负整数 n ，请核算 0 到 n 之间的每个数字的二进制表明中 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 
阐明 :
● 0 <= n <= 105

知识点： 位运算 动态规划

办法一：位运算

剖析：

直观解法，运用一个for循环来核算从0到n的每个整数i的二进制方式中1的个数。

每次用“i&（i-1）”将整数i的最右边的1变成0。整数i减去1，那么它最右边的1变成0。假如它的右边还有0，则右边一切的0都变成1，而其左面一切位都坚持不变。

/**
 * @param {number} n
 * @return {number[]}
 */
var countBits = function(n) {
    let result = new Array(n + 1).fill(0);;
    for (let i = 0; i<=n; i++) {
        let j = i;
        while(j !== 0) {
            result[i]++;
            j = j & (j -1);
        }
    }
    return result;
};

复杂度剖析

• 时刻复杂度：O(nlog⁡n)。需要对从 0 到 n 的每个整数运用核算「一比特数」，关于每个整数核算「一比特数」的时刻都不会超过 O(log⁡n)。

• 空间复杂度：O(1)。除了返回的数组以外，空间复杂度为常数。

办法二：动态规划

剖析：

根据前面的剖析可知，“i&（i-1）”将i的二进制方式中最右边的1变成0，也就是说，整数i的二进制方式中1的个数比“i&（i-1）”的二进制方式中1的个数多1。

/**
 * @param {number} n
 * @return {number[]}
 */
var countBits = function(n) {
    let res = [];
    res[0] = 0
    for(let i = 1;i <=n;i++) {
        //整数 i 的二进制方式中1的个数比 i &(i - 1)的二进制方式中1的个数多1
        res[i] = res[i & (i - 1)] + 1;
    }
    return res
};

复杂度剖析

• 时刻复杂度：O(n)。关于每个整数，只需要 O(1) 的时刻核算「一比特数」。

• 空间复杂度：O(1)。除了返回的数组以外，空间复杂度为常数。

剑指 Offer II 004. 只呈现一次的数字

给你一个整数数组 nums ，除某个元素仅呈现 一次 外，其他每个元素都恰呈现 三次 。 请你找出并返回那个只呈现了一次的元素。

难度：中等

示例 1：
输入：nums = [2,2,3,2] 输出：3 
示例 2：
输入：nums = [0,1,0,1,0,1,100] 输出：100 
提示：
● 1 <= nums.length <= 3 * 104
● -231 <= nums[i] <= 231 - 1
● nums 中，除某个元素仅呈现 一次 外，其他每个元素都恰呈现 三次

知识点： 位运算 数组

办法一：位运算

剖析：

关于计算数字呈现次数，能够想到Hash表，可是这样没有运用每个元素都恰呈现 三次 特性。或者运用排序再进行计算的时刻复杂度可能会高于O(n)。但若面试时没有思路，能够先答出让面试官引导持续回答。

这个标题有一个简化版的类似的标题“输入数组中除一个数字只呈现一次之外其他数字都呈现两次，请找出只呈现一次的数字”。任何一个数字异或它自己的成果都是0。假如将数组中一切数字进行异或运算，那么最终的成果就是那个只呈现一次的数字。

考虑数字的二进制方式。将数组中一切数字的同一方位的数位相加。

假如将呈现3次的数字独自拿出来，那么这些呈现了3次的数字的恣意第i个数位之和都能被3整除。因此，假如数组中一切数字的第i个数位相加之和能被3整除，那么只呈现一次的数字的第i个数位一定是0；假如数组中一切数字的第i个数位相加之和被3除余1，那么只呈现一次的数字的第i个数位一定是1。

计算一切数字的各二进制位中 1 的呈现次数，并对 3 求余，成果则为只呈现一次的数字。

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    // 创建一个长度为32的数组，默认值为0
    let arr = new Array(32).fill(0);
    for (let i = 0; i<nums.length; i++) {
        for (let j = 0; j<32; j++) {
            // 整数i先被右移31-i位，原来从左起第i个数位右移之后位于最右边
            // 与1做位与运算   也就是说只要1与1做位与运算才为1否则为0
            arr[j] += (nums[i] >> (31 - j)) & 1;
        }
    }
    // arr中每一位保存着nums中对应位中1的个数和
    let res = 0;
    for (let i = 0; i<32; i++) {
        res = (res << 1) + (arr[i] %3);
    }
    return res;
};

复杂度剖析

• 时刻复杂度：O(n)
• 空间复杂度：O(1)

so

• 结束依旧：长风破浪会有时，直挂云帆济沧海！
• 在线整理的的确很好，对的文章进行了一个汇总整理，在线刷题攻略，拿走不谢，要学会站在他人的肩膀上提升自己点击这儿–> 前端进阶攻略

传送门

• 简历包装 || 简历造假 vs 背景调查
• 卷王的2021总结
• 我为什么喜爱手抄代码
• 前端三年：小白变成老油条
• 今年面试了100+的前端同学我的总结
• 我为什么坚持六点起床
• 我读技能书很焦虑，读不下去书怎么办？
• 勤奋努力 === “卷” ？
• vite + react + ts 手摸手做项目系列一 （项目装备篇）
• vite + react + ts 手摸手做项目系列二 （实战篇）