关于leetcode的测试用例

来源:7-5 最大矩阵-代码实操(2)

Nick_arron

2019-07-31

应该是leetcode更新了很多测试用例,导致目前无法通过了。
对于问题的理解:目前对于只有一个1或者一行1或者一列1,leetcode都认为是矩形,根据老师的代码改了一些边界条件,暂时可以通过所有用例,但是性能很差。
提供如下,欢迎指正。

function maximalRectangle (matrix) {
  if (!matrix.length) return 0
  let result = []
  let reg = /1+/g
  matrix = matrix.map(item => {
    let str = item.join('')
    let r = reg.exec(str)
    let rs = []
    while (r) {
      rs.push([r.index, r.index + r[0].length - 1])
      r = reg.exec(str)
    }
    return rs
  })
  if (matrix.length < 2) {
    matrix[0].map(posArr => {
      result.push(posArr[1] - posArr[0] + 1)
    })
  }
  
  let calc = (arr, n = 1) => {
    let top = arr.pop()
    let next = arr.pop()
    let tt
    let nn
    let start
    let end
    let width = 1
    let minWidth = 0
    let temp = []
    let max = result.length > 0 ? Math.max(...result) : 0
    n++

    for (let i = 0, lt = top.length; i < lt; i++) {
      tt = top[i]
      if (tt && tt[1] - tt[0] + 1 > max) {
        result.push(tt[1] - tt[0] + 1)
      }

      for (let j = 0, ln = next.length; j < ln; j++) {
        nn = next[j]
        if (nn && nn[1] - nn[0] + 1 > max) {
          result.push(nn[1] - nn[0] + 1)
        }
        width = Math.min(tt[1], nn[1]) - Math.max(tt[0], nn[0])
        if (width >= minWidth) {
          start = Math.max(tt[0], nn[0])
          end = Math.min(tt[1], nn[1])
          temp.push([start, end])
        }
      }
    }

    if (start === undefined || end === undefined) {
      if (n < 3) {
        return false
      } else {
        width = top[0][1] - top[0][0] + 1
        if (width > 1) {
          result.push(width * (n - 1))
        }
      }
    } else {
      if (arr.length > 0) {
        // 这里应该是有问题的
        let maxWidth = 0
        temp.map((posArr) => {
          if (posArr[1] - posArr[0] > maxWidth) {
            maxWidth = posArr[1] - posArr[0]
          }
        })
        result.push(n * (maxWidth + 1))
        arr.push(temp)
        calc(arr, n++)
      } else {
        // 到最后一行
        let maxWidth = 0
        temp.map((posArr) => {
          if (posArr[1] - posArr[0] > maxWidth) {
            maxWidth = posArr[1] - posArr[0]
          }
        })
        result.push(n * (maxWidth + 1))
      }
    }
  }
  while (matrix.length > 1) {
    calc([].concat(matrix))
    matrix.pop()
  }
  return result.length > 0 ? Math.max(...result) : 0
}

写回答

1回答

快乐动起来呀

2019-08-01

嗯,leetcode的测试用例在不断更新,目前这道题的算法确实不是最优解,等我更新的,也欢迎把你的算法贡献到 git.imooc.com 的 issue 区哈,分享更多同学学习

0
0

JavaScript版 数据结构与算法

填补前端同学的算法短板,掌握面试中最常见的算法与数据结构

2467 学习 · 395 问题

查看课程