# 初级算法 其他
# 汉明重量
汉明重量是一串符号中非零符号的个数。 因此它等同于同样长度的全零符号串的汉明距离。
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
};