二维数组及滚动数组

118. 杨辉三角

思路

找出规律：res[i][j] = res[i-1][j-1] + res[i-1][j]

代码

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function(numRows) {
  if (!numRows) return [];
  const res = [[1]];
  for(let i = 1; i < numRows; i ++) {
    let path = []
    for(let j = 0; j <= i; j ++) {
      path[j] = (res[i-1][j-1] || 0) + (res[i-1][j] || 0)
    }
    res.push(path)
  }
  return res;
};

复杂度分析

时间复杂度 #card=math&code=O%28N%5E2%29)
空间复杂度

119. 杨辉三角 II

思路

使用滚动数组，从右 → 左遍历更新值，从 左→右的话值已经更新了，会重复累加

代码

/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function(rowIndex) {
  const res = Array(rowIndex+1).fill(1);
  for(let i = 1; i < rowIndex; i ++) {
    for(let j = i; j >= 0; j --) {
      res[j] += res[j-1] || 0;
    }
  }
  return res;
};

复杂度分析

时间复杂度 #card=math&code=O%28N%5E2%29)
空间复杂度 #card=math&code=O%28N%29)

661. 图片平滑器

思路

确定好边界和当前能计算在内的个数求得均值。

代码

/**
 * @param {number[][]} M
 * @return {number[][]}
 */
var imageSmoother = function(M) {
  const res = [], rowLen = M.length, colLen = M[0].length;
  for(let row = 0; row < rowLen; row ++) {
    let path = [];
    for(let col = 0; col < colLen; col ++) {
      path.push(getArvage(M, row, col))
    }
    res.push(path)
  }
  return res;
};

function getArvage(M, rowIndex, colIndex) {
  let sum = 0, count = 0, rowLen = M.length, colLen = M[0].length;
  for(let row = Math.max(rowIndex-1, 0); row <= Math.min(rowIndex+1, rowLen-1); row ++) {
    for(let col = Math.max(colIndex-1, 0); col <= Math.min(colIndex+1, colLen-1); col ++) {
      sum+= M[row][col] || 0
      count += 1;
    }
  }
  return Math.floor(sum / count)
}

复杂度分析

时间复杂度 #card=math&code=O%28N%5E2%29)
空间复杂度 #card=math&code=O%28N%5E2%29)

598. 范围求和 II

思路

最大整数永远在左上角，找到ops中行和列最小值与矩阵的行列相比得到面积即可

代码

/**
 * @param {number} m
 * @param {number} n
 * @param {number[][]} ops
 * @return {number}
 */
var maxCount = function(m, n, ops) {
  let minA = Number.MAX_SAFE_INTEGER, minB = Number.MAX_SAFE_INTEGER;
  for(let i = 0; i < ops.length; i ++) {
    let [a, b] = ops[i];
    minA = Math.min(minA, a)
    minB = Math.min(minB, b)
  }
  return Math.min(m, minA) * Math.min(n, minB)
};

复杂度分析

时间复杂度 #card=math&code=O%28k%29) ops的操作次数
空间复杂度 #card=math&code=O%281%29)

419. 甲板上的战舰

思路

1、题目中指出，战舰要么是横着连续，要么是竖着连续
2、遍历数组，当遇到’X’就说明有一艘战舰，我们判断是横着还是竖着，循环把战舰的’X’全部设为”.”
3、继续循环，下次遇到’X’说明是新的战舰，我们再记一次数，重复操作2
4、当遍历完数组，甲板就全变成了”.”，所有的战舰也被统计出来了

代码

/**
 * @param {character[][]} board
 * @return {number}
 */
/**
 * @param {character[][]} board
 * @return {number}
 */
function countBattleships(board) {
  let count = 0;
  for (let i = 0; i < board.length; i++) {
    let row = board[i];
    for (let j = 0; j < row.length; j++) {
      if (row[j] === 'X') {
        if (board[i + 1] && board[i + 1][j] === 'X') {
          let r = i;
          while (board[r] && board[r][j] === 'X') {
            board[r++][j] = '.';
          }
        } else {
          let c = j;
          while (row[c] === 'X') {
            row[c++] = '.';
          }
        }
        count++;
      }
    }
  }
  return count;
}

复杂度分析

时间复杂度 #card=math&code=O%28N%5E2%29)
空间复杂度 #card=math&code=O%28N%29)