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


theme: fancy

前言

  • 现在前端要求变高了,找工作的时可能会碰上算法题,每天刷几道算法题做足准备,今天是《剑指 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

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

image.png

传送门

© 版权声明
THE END
喜欢就支持一下吧
点赞10 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片

    暂无评论内容