矩阵

顺时针打印矩阵 (opens new window)

顺时针输入一个矩阵，按照从外向里以顺时针的顺序依次打印每一个数字。

function spiralOrder(matrix: number[][]): number[] {
  const yLength = matrix.length
  if (!yLength) {
  	return []
  }
  
  const xLength = matrix[0].length
  if (xLength === 1 || yLength === 1) {
  	return matrix.reduce((pre, cur) => pre.concat(cur), [])
  }
    
  const round = Math.ceil((xLength < yLength ? xLength : yLength) / 2)
    
  let result: number[] = []
    
  for (let i = 0; i < round; i++) {
		result.push(getCircle(xLength, yLength, i, matrix))
  }
  result = result.reduce((pre, cur) => pre.concat(cur), [])
  result.length = xLength * yLength
  return result
}


function getCircle(xLength: number, yLength: number, index: number, matrix: number[][]): number[] {
		let x = index, y = index
    xLength = xLength - index
    yLength = yLength - index
    const list: number[] = []
    while (y < xLength) {
    	list.push(matrix[x][y])
      y++
    }
    y--
    x++
    while (x < yLength) {
      list.push(matrix[x][y])
      x++
    }
    x--
    y--
    while (y >= index) {
      list.push(matrix[x][y])
      y--
    }
    y++
    x--
    while (x >= index) {
      list.push(matrix[x][y])
      x--
    }
    x++
    y++ 
		if(list.length > 1){
    	list.pop()       
		}
    return list
}

旋转图像 (opens new window)

给定一个 n × n 的二维矩阵表示一个图像。

将图像顺时针旋转 90 度。

function rotate(matrix: number[][]): void {
  if(!matrix.length) return 
  let left = 0
  let right = matrix.length - 1
  
  while(left < right) {
    [matrix[left], matrix[right]] = [matrix[right], matrix[left]]
    left++
    right--
  }
  
  for(let i = 0; i < matrix.length; i++) {
    for(let j = i + 1; j < matrix[i].length; j++) {
      [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]]
    }
  }
}

螺旋矩阵II (opens new window)

给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

function generateMatrix(n: number): number[][] {
  if(n === 1) return [[1]] // 特殊情况
  
  const res: number[][] = []
  
  for(let i = 0; i < n; i++) {
    res[i] = []
  }
  
  // 旋转圈数
  let circleNum = n - 1
  let num = 1
  // 记录循环次数，用于定义每次起点位置
  let count = 0
  
  while(circleNum) {
    let x = count
    let y = count
    
    const rect = n - count * 2
    if(rect === 1) res[y][x] = num++
    
    // 上
    for(let i = 0; i < rect - 1; i++) {
      res[y][x++] = num++
    }
    // 右
    for(let i = 0; i < rect - 1; i++) {
      res[y++][x] = num++
    }
    // 下
    for(let i = 0; i < rect - 1; i++) {
      res[y][x--] = num++
    }
    // 左
    for(let i = 0; i < rect - 1; i++) {
      res[y--][x] = num++
    }
    
    circleNum--
    count++
  }
  
  
  return res
}

矩阵置零 (opens new window)

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。

// 巧用 0 === -0 且 Object.is(0, -1) === false
function setZeros(matrix: number[][]): void {
  for(let i = 0; i < matrix.length; i++) {
    for(let j = 0; j < matrix[i].length; j++) {
      if(Object.is(matrix[i][j], 0)) {
        
        for(let k = 0; k < matrix.length; k++) {
          if(k !== i && Object.is(matrix[k][j], 0)) continue
          else matrix[k][j] = -0
        }
        
        for(let k = 0; k < matrix[i].length; k++) {
          if(k !== j && Object.is(matrix[i][k], 0)) continue
          else matrix[i][k] = -0
        }
      }
    }
  }
}

标记法

function setZeros(matrix: number[][]): void {
  const rows: {[key: number]: boolean} = {}
  const cols: {[key: number]: boolean} = {}
  
  for(let i = 0; i < matrix.length; i++) {
    for(let j = 0; j < matrix[i].length; j++) {
      if(matrix[i][j] === 0) {
        rows[i] = true
        cols[j] = true
      }
    }
  }
  
  for(let i = 0; i < matrix.length; i++) {
    for(let j = 0; j < matrix[i].length; j++) {
      if(rows[i] || cols[j]) {
        matrix[i][j] = 0
      }
    }
  }
}

杨辉三角 (opens new window)

给定一个非负整数 *numRows，*生成杨辉三角的前 numRows 行。

在杨辉三角中，每个数是它左上方和右上方的数的和。

function generate(numRows: number): number[][] {
  if(numRows <= 0) return []
  
  const res: number[][] = []
  
  for(let i = 0; i < numRows; i++) {
    const subArr: number[] = []
    for(let j = 0; j <= i; j++) {
      if(j > 0 && j < i) {
        subArr.push(res[i - 1][j - 1] + res[i - 1][j])
      } else {
        subArr.push(1)
      }
    }
    res.push(subArr)
  }
  return res
}