前言

  • 现在前端要求变高了,找工作的时可能会碰上算法题,每天刷几道算法题做足预备,今天是《剑指 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 求余,成果则为只呈现一次的数字。

剑指 Offer(专项突击版)第3|4题

/**
 * @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

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

剑指 Offer(专项突击版)第3|4题

传送门

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