每日算法

2021-10-18

448. 找到所有数组中消失的数字

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

示例 1：

1 2	输入：nums = [4,3,2,7,8,2,3,1] 输出：[5,6]

示例 2：

1 2	输入：nums = [1,1] 输出：[2]

思路:

新建一个map
记录数组中出现过的值
for从1到 length + 1 查看map中是否又对应的值,如果没有 push进结果里

代码:

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDisappearedNumbers = function(nums) {
    var map = new Map()
    let res = []
    for(var i = 0; i < nums.length; i++) {
        if(map.has(nums[i])) {
            map.set(nums[i],map.get(nums[i])+1)
        }else {
            map.set(nums[i],1)
        }
    }
    for(var j = 1; j < nums.length + 1; j++) {
        if(!map.get(j)) {
            res.push(j)
        }
    }
    return res
};

338. 比特位计数

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

示例 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

思路:

先把利用toString(2/8/16)将十进制转为二进制
每一次遍历一个二进制并记录其中1的数量

代码:

/**
 * @param {number} n
 * @return {number[]}
 */
var countBits = function(n) {
    const result = []
    for(var i = 0; i <= n; i++) {
       let _i =  i.toString(2)
       let res = 0
       for(var j = 0; j <= _i.length; j++) {
           if(_i[j] == 1) {
               res++
           }
       }
       result.push(res)
    }
    return result
};

呜呜呜….,感觉我写的算法时间复杂的,空间复杂的好高…….

加油!!!!!