算法相关的JavaScript实现

转载自奇舞周刊微信公众号，https://mp.weixin.qq.com/s/SLvmOmy5LpyV4YJ3rXLnEQ
看完觉得还不够，手动敲一敲加深记忆………

位运算相关

计算汉明重量

汉明重量即整数中比特1的个数，是LeetCode中的一道题。
汉明重量是一串符号中非零符号的个数。因此它等同于同样长度的全零符号串的汉明距离。在最为常见的数据位符号串中，它是1的个数。

function hammingWeight(n) {
    let num = 0
    while(n !== 0) {
        // &= 按位与赋值
        n &= (n-1)
        num++
    }
    return num
}

判断奇偶

function isOdd(n) {
    return n & 1 === 1
}

二分查找

非递归方法

function binarySearch(nums, target) {
    let low = 0
    let high = nums.length - 1

    while(low <= high) {
        let mid = parseInt((low+high)/2)
        if(nums[mid] == target) {
            return nums[mid]
        }
        if(nums[mid] > target) {
            high = mid - 1
        }
        if(nums[mid] < target) {
            low = mid + 1
        }
    }
    return -1
}

递归方法

function binarySearch(nums, target) {
    let low = 0
    let high = nums.length - 1

    const binaryWalker = (nums, low, high, target) => {
        if(low > high) return -1
        const mid = parseInt((low+high)/2)
        if(nums[mid] == target) return nums[mid]
        if(nums[mid] > target) return binaryWalker(nums, low, mid-1, target)
        if(nums[mid] < target) return binaryWalker(nums, mid+1, high, target)
    }
    return binaryWalker(nums, low, high, target)
}

常见排序

快速排序

function quickSort(arr) {
    if(arr.length <= 1) return arr

    let left = []
    let right = []

    let pivot = arr[0]

    for (let i = 1; i < arr.length; i++) {
        if(arr[i] > pivot) {
            right.push(arr[i])
        } else {
            left.push(arr[i])
        }
    }

    return [...quickSort(left), pivot, ...quickSort(right)]
}

冒泡排序

function bobbleSort(arr) {
    let i = arr.length - 1
    while(i >= 0) {
        for (var j = 0; j < i; j++) {
            if (arr[j] > arr[j+1]) {
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
            }
        }
        i--
    }
    return arr
}

二叉树遍历相关

这块内容似懂非懂，尤其是二叉树遍历非递归实现时的算法，有点懵圈
参考之前写的博客二叉树遍历 也是用的递归实现，不知道非递归的方法重不重要

前序遍历（中→左→右）

• 递归实现

function preOrderTraverse(root) {
    if (root) {
        console.log(root)
        preOrderTraverse(root.left)
        preOrderTraverse(root.right)
    }
}

• 非递归实现

function preOrderTraverse(root) {
    let stack = []

    if (root) {
        stack.push(root)
    }

    while(stack.length) {
        let temp = stack.pop()
        console.log(temp)

        if(temp.left) stack.push(temp.left)

        if(temp.right) stack.push(temp.right)
    }
}

中序遍历（左→中→右）

• 递归实现

function midOrderTraverse(root) {
    if (root) {
        midOrderTraverse(root.left)
        console.log(root)
        midOrderTraverse(root.right)
    }
}

• 非递归实现

function midOrderTraverse(root) {
    let stack = []
    while(true) {
        while(root) {
            stack.push(root)
            root = root.left
        }

        if(!stack.length) break

        let temp = stack.pop()
        console.log(temp)
        root = temp.right
    }
}

后序遍历（左→右→中）

• 递归实现

function postOrderTraverse(root) {
    if (root) {
        postOrderTraverse(root.left)
        postOrderTraverse(root.right)
        console.log(root)
    }
}

• 非递归实现

function postOrderTraverse(root) {
    let stack = [];
    let rest = [];
    if(root)stack.push(root);
    while(stack.length) {
      let temp = stack.pop();
      rest.push(temp);
      if(temp.left) stack.push(temp.left);
      if(temp.right) stack.push(temp.right);
    }
    return rest.reverse();
  }

层次遍历

function levelTraverse(root) {
    if(!root) return;
    let stack = [];
    stack.push(root);

    while(stack.length) {
      let temp = stack.shift();
      console.log(temp);
      if(temp.left) stack.push(temp.left);
      if(temp.right) stack.push(temp.right);
    }
  }