[数据结构与算法]【近日力扣】矩阵中的路径+二进制中1的个数+比较版本号+旋转数组的最小数字

矩阵中的路径（中等）

• DFS 深度优先搜索

var exist = function(board, word) {
	// dfs 深度优先搜索矩阵
    let dfs = (board, word, i, j, k) => {
    	// 如果 i j 超出或不在矩阵里，或二维数组元素不等于word中的字母，则返回 false
        if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] !== word[k]) return false
        // 
        if (k === word.length - 1) return true
        // 在这一轮中将搜索过的路径标记为空
        board[i][j] = ''
        // 短路语法，只要有一条路径传回true则成功，不需要找到所有路径
        let res = dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i, j - 1, k +1)
                  || dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1)
        // 复原标记过的元素，不干扰下一轮搜索（因为dfs中每个单元格会被访问多次）
        // 注意，数组作为参数传入函数是传地址
        board[i][j] = word[k]
        return res
    }
    
    // 双循环，将每一个元素都作起点进行一次深度优先搜索
    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            if (dfs(board, word, i, j, 0)) return true
        }
    }
    return false
};

二进制中1的个数（简单）

• 传入的是二进制数，第一种，循环用位逻辑与比较 n 的最后一位，且比较后去除末位；第二种，利用n &= n - 1的性质加速循环进程，这个式子会使得 n 低位的 1 被置换为零，统计置换的次数即为1的个数，举例：110 & 110 - 1 = 100，其第二位的 1 被置换为零

var hammingWeight = function(n) {
    let sum = 0
    // 第一种
    // for (let i = 0; i < 32; i++) {
    //     if (n & (1 << i)) sum++
    // }
    // 第二种
    while (n) {
    	// 小知识插入：加减法优先级高于逻辑运算（这里没用到）
        n &= n - 1
        sum++
    }
    return sum
};

比较版本号（中等）

• 感觉理解了比较的点在哪里，且知道一些常见API就差不多了

var compareVersion = function(version1, version2) {
    let a1 = version1.split(".")
    let a2 = version2.split(".")
    let max = Math.max(a1.length, a2.length)
    for (let i = 0; i < max; i++) {
    	// 给短的数组后续补零
        let x = (a1[i] === undefined) ? 0 : parseInt(a1[i])
        let y = (a2[i] === undefined) ? 0 : parseInt(a2[i])
        if (x > y) return 1
        if (x < y) return -1
    }
    return 0
    
};

旋转数组的最小数字（简单）

• 二分法，第一次遇到，感觉很新颖

var minArray = function(numbers) {
	// 设定左右边界
    let left = 0
    let right = numbers.length - 1
    // 只要右边界大于左边界就继续循环
    while (left < right) {
        let center = Math.floor((left + right) / 2) // 取中点
        // 若左边界大于中点，则最小值为中点或者其左边，缩小右边界
        if (numbers[left] > numbers[center]) {
            right = center
        // 若右边界大于中点，则最小值为中点或者其右边，缩小左边界
        } else if (numbers[right] < numbers[center]) {
            left = center + 1
        } else {
        	// 中点等于左/右边界，缩小任意边界便可，此处缩小右边界
            right--
        }
    }
    return numbers[left]
};