Two questions a day T25

Two questions a day T25

algorithm

LeetCode T542. 01 matrix [1]

description

Given a matrix of 0 and 1, find the distance of each element to the nearest 0.

The distance between two adjacent elements is 1.

Example 1:

enter
0 0 0
0 1 0
0 0 0

Output
0 0 0
0 1 0
0 0 0

Example 2:

enter
0 0 0
0 1 0
1 1 1

Output
0 0 0
0 1 0
1 2 1

note:

1. The number of elements in a given matrix does not exceed 10000. 2. At least one element in the given matrix is ​​0. 3. The elements in the matrix are only adjacent in four directions: up, down, left, and right.

analysis

Typical dynamic programming problem

Code

/**
 * @param {number[][]} matrix
 * @return {number[][]}
 */
var updateMatrix = function (matrix) {
 //dp optimise
  if (matrix.length == 0) {
    return [];
  }
  let m = matrix.length, n = matrix[0].length;
 //left-top to right-bottom
  for (let i = 0; i <m; i++) {
    for (let j = 0; j <n; j++) {
      if (matrix[i][j] != 0) {
        matrix[i][j] = m + n;
        if (i> 0) {
          matrix[i][j] = Math.min(matrix[i-1][j] + 1, matrix[i][j]);
        }
        if (j> 0) {
          matrix[i][j] = Math.min(matrix[i][j-1] + 1, matrix[i][j]);
        }
      }
    }
  }
 //right-bottom to left-top
  for (let i = m-1; i >= 0; i--) {
    for (let j = n-1; j >= 0; j--) {
     //distance
      if (matrix[i][j] != 0) {
        if (j <n-1) {
          matrix[i][j] = Math.min(matrix[i][j], matrix[i][j + 1] + 1);
        }
        if (i <matrix.length-1) {
          matrix[i][j] = Math.min(matrix[i][j], matrix[i + 1][j] + 1);
        }
      }
    }
  }
  return matrix;
};

JavaScript

Please write bind,apply

To realize bind, there are a few points to pay attention to

1. The prototype of the new function should be the prototype pointing to the current scope. 2. It is also necessary to ensure that the newly created function prototype and the private prototype of the function object are correct

Function.prototype.bind2 = function (context) {

    if (typeof this !== "function") {
      throw new Error("Function.prototype.bind-what is trying to be bound is not callable");
    }

    const self = this;
    const args = Array.prototype.slice.call(arguments, 1);
    const fNOP = function () {};

    const fbound = function () {
        self.apply(this instanceof self? this: context, args.concat(Array.prototype.slice.call(arguments)));
    }

    fNOP.prototype = this.prototype;
    fbound.prototype = new fNOP();

    return fbound;

}

Implement apply without the help of bind or call

Function.prototype.apply2 = function (context, arr) {
    var context = Object(context) || window;
    context.fn = this;

    var result;
    if (!arr) {
        result = context.fn();
    }
    else {
        var args = [];
        for (var i = 0, len = arr.length; i <len; i++) {
            args.push('arr[' + i +']');
        }
        result = eval('context.fn(' + args +')')
    }

    delete context.fn
    return result;
}

References

[1]542. 01 Matrix: https://leetcode-cn.com/problems/01-matrix/

Reference: https://cloud.tencent.com/developer/article/1664344 Two questions a day T25-Cloud + Community-Tencent Cloud