初级算法 其他

汉明重量

汉明重量是一串符号中非零符号的个数。 因此它等同于同样长度的全零符号串的汉明距离。

var hammingWeight = function(n) {
    let count = 0
    while(n){
        n = n & (n - 1)   
        count += 1
    }
    return count
};

汉明距离

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

运用异或

var hammingDistance = function(x, y) {
    let n  = x ^ y
    let count = 0
    while(n){
        n = n & (n - 1)   
        count += 1
    }
    return count
};

颠倒二进制位

输入一个整数，给出其二进制位表示，返回翻转其二进制表示后所表示的值

var reverseBits = function(n) {
    let arr = new Array(32).fill("0")
    let bits = n.toString(2).split("")
    for(let i = 0; i < bits.length; i++){
        arr[32 - i - 1] = bits[bits.length - i - 1]
    }
    let bin = arr.reverse().join("")
    return parseInt(bin,2)
};

杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行

var generate = function(numRows) {
    let result = []
    for(let i = 0 ; i < numRows; i++){
        let row = []
        for(let j = 0 ; j < numRows; j++){
            if(i == 0){
                row.push(1)
                break
            }else {
                if(j == 0 || j == i){
                    row.push(1)
                } else if(j < i) {
                    let num = result[i-1][j-1] + result[i-1][j]
                    row.push(num)
                }
            }
        }
        result.push(row)
    }
    return result;
};

有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['， ']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。

这种类似运算表达式的匹配一般都使用栈来解决

var isValid = function(s) {
    let length = s.length 
    if(length % 2 != 0) return false
    let map = {
        "(":")",
        "[":"]",
        "{":"}"
    }
    let stack  = [s[0]]
    for(let i = 1; i < length; i++ ){
        if(map[stack[stack.length - 1]] == s[i] ){
            stack.pop()
        }else {
            stack.push(s[i])
        }
    }
    return stack.length == 0 
};

缺失数字

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

等差数列求和

var missingNumber = function(nums) {
    let sum1 = nums.reduce((a,b)=>a+b)
    let n = nums.length 
    let sum2 = (1 + n) * n / 2
    return sum2 - sum1
};