黑白像素方阵

给定一个方阵,每个单元pixel either black or white. 找出四条边都是black pixels的最大sub-matrix 

Naive: O(N^4)

先找N by N, 如果判断成功结束。失败的话,1尝试第二大的 N-1 * N-1。iterate所有这个size的。。逐渐尝试

Better: O(N^3)

上面的解法之所以慢是因为每检查一个可能符合要求的方阵,要O(N)的工作量。 所以可以预先做一下处理。把isSquare的复杂度降为O(1)

这题的技巧就是Pre-Processing。


变形题:


这题是一个搜索类题目。


这个解法好有趣

DFS

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 14,354评论 0 33
  • 一、实验目的 学习使用 weka 中的常用分类器,完成数据分类任务。 二、实验内容 了解 weka 中 explo...
    yigoh阅读 12,769评论 5 4
  • 一年级语文上册生字表 生字表一(共400字) 啊(ā)爱(ài)安(ān)岸(àn)爸(bà)八(bā)巴(bā)...
    meychang阅读 8,117评论 0 6
  • 今天是一周的开始,更是崭新的一周,是奋斗的起点,是憧憬的绽放,是精彩的孕育,是梦想的再次启航,星期一我们迎来...
    2020级1班阅读 4,576评论 41 10
  • 隐青砖黛瓦红墙,苍劲柏,映初阳。 入佛寺拜礼烟香,与愿赤心藏。 禅坐定、悟道是平常。 ——重阳_张 中华新韵 与愿...
    重阳_张阅读 3,362评论 6 6

友情链接更多精彩内容