LeetCode热题100中 35. 46. 70. 73. 118.

35.搜索插入位置

题目描述：

实现思路：

        这里主要就是二分查找，二分查找要注意对边界值的处理，l 是 数组的第一位，r是数组的最后一位，l <= r 我们就返回 l ,因为我们的判断是nums[mid] < target  取的是mid的左区间已经不包含mid 了,所以是 l = mid + 1 。

代码：

var searchInsert = function(nums, target) {
    let l = 0
    let r = nums.length - 1
    while(l <= r){
        let mid = Math.trunc((l + r) / 2)
        if(nums[mid] < target){
            l = mid + 1
        }else{
            r = mid - 1
        }
    }
    return l
};

46. 全排列

题目描述：

实现思路：

我们通过 user 来存储使用过的值，res 来存储 path 的数组，每次 path.lenght 的值等于nums.length 的时候我们就将 path 的数组加到 res 中去。

代码：

var permute = function(nums) {
    const res = [], path = [];
    backtracking(nums, nums.length, []);
    return res;

    function backtracking(nums,k,used){
        if(path.length === k) {
            res.push(Array.from(path));
            return;
        }
        for (let i = 0; i < k; i++ ) {
            if(used[i] != true){
            path.push(nums[i]);
            used[i] = true; // 同支
            backtracking(nums, k, used);
            path.pop();
            used[i] = false;
            }
        }
    }
};

70. 爬楼梯

题目描述：

实现思路：

规律：
n = 1 ，有1 种方法： 一阶 。
n = 2，有2种方法：一阶＋一阶，二阶。
n = 3，有3种方法：一阶＋一阶 + 一阶，一阶 +二阶 ，二阶 + 一阶。
n = 4，有5种方法：一阶＋一阶 + 一阶+ 一阶，一阶 +二阶 + 一阶，二阶 + 二阶 ，一阶＋一阶+二阶， 二阶＋一阶 + 一阶 
。。。。
在这里，我们不关心具体用的是什么方法，我们只关心的是方法有几种，这里用的就是动态规划了，dp[ i ] ：指的就是达到第 i 阶 有dp[ i ] 种方法，那么dp[ i ] 就是由 dp[ i - 1 ] ＋ dp[ i - 2 ]

代码：

var climbStairs = function(n) {
    const dp = [];
    dp[1] = 1
    dp[2] = 2
    for(let i = 3; i <= n ;i++){
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
};

73. 矩阵置零

题目描述：

理解：

        就是在原数组中如果有 0 ，就要将其所在的行和列的元素变为 0。
        原地算法 指的是除了输入数据本身所占用的存储空间之外，不依赖于额外的数据结构或大量辅助数组来存储中间结果。

实现思路：

        通过第一列和第一行来记录哪一列哪一行需要置为 0，第一列和第一行有交叉的元素，也就是 [0][0]，所以我们用zerozero 来记录第一列的第一个元素。
        遍历数组时候，如果遇到某一个值为0，将该行第一个元素和该列第一个元素置为 0，因为该行的第一个元素和该列第一个元素都已经遍历过了，所以不会影响到接下来的遍历。
        最后再遍历一次数组，将需要置 0 的行和列置 0 。需要注意的是要先遍历除了第一行和第一列以外的元素，最后遍历第一行和第一列的元素，如果按顺序遍历元素，有可能会改变第一行和第一列存储的 0，从而导致结果错误。

代码：

var setZeroes = function(matrix) {
    const rows = matrix.length
    const cols = matrix[0].length
    let zerozero = 1
    for(let row = 0;row < rows; row++){
        for(let col = 0;col < cols; col++){
            if(matrix[row][col] == 0){
                matrix[0][col] = 0
                if(row > 0){
                    matrix[row][0] = 0
                }else{
                    zerozero = 0
                }
            }
        }
    }

    for(let row = 1;row < rows;row++){
        for(let col = 1;col < cols; col++){
            if(matrix[0][col] == 0 || matrix[row][0] == 0){
                matrix[row][col] = 0
            }
        }
    }

    for(let row = 0;row < rows;row++){
        if(matrix[0][0] == 0){
            matrix[row][0] = 0
        }
    }

    for(let col = 0;col < cols;col++){
        if(zerozero == 0){
            matrix[0][col] = 0
        }
    }

    return matrix;
};

118. 杨辉三角

题目描述：

实现思路：

        我们观察可以发现杨辉三角的第一位，也就是最上面的数一直等于 1 ，并且每行的第一位和最后一位都等于 1 ，除了上面所说的剩下的数，举个例子，第四行的第二位数 = 第三行的第一位 ＋ 第三行的第二位，第四行的第三位数 = 第三行的第二位 ＋ 第三行的第一位。我们设除上述的特殊位以外的数 arr[ i ][ j ]，那么由此规律可以推出它的每一位就等于：                                                arr[ i ][ j ] = arr[ i - 1 ][ j - 1] + arr[ i - 1 ][ j ]  。

代码：

var generate = function(numRows) {
   if(numRows === 0) return [];
   //  numRows 不是 0 ,第一位必为 1
   let arr = [[1]];
   for(let i = 1;i < numRows;i++) {
    //每行第一位
    arr[i] = [1]
    for(let j = 1;j < i;j++){
        arr[i][j] = arr[i-1][j-1] + arr[i-1][j]
    }
    arr[i][i] = 1
   }
   return arr
};