• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode221.最大正方形|MaximalSquare

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:https://www.cnblogs.com/strengthen/p/10203015.html 
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example:

Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。

示例:

输入: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

输出: 4

404ms
 1 class Solution {
 2     func maximalSquare(_ matrix: [[Character]]) -> Int {
 3 
 4         guard matrix.count > 0, matrix[0].count > 0 else { return 0 }
 5         var m = matrix.count, n = matrix[0].count
 6         var dp = Array(repeating: Array(repeating: 0, count: n+1), count: m+1)
 7         var res = 0
 8         for i in 1...m {
 9             for j in 1...n {
10                 if matrix[i-1][j-1] == "0" { continue }
11                dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1
12                 res = max(res, dp[i][j])
13             }
14         }
15         return res * res
16     }
17 }

408ms

 1 class Solution {
 2     func maximalSquare(_ matrix: [[Character]]) -> Int {
 3 
 4         guard matrix.count > 0, matrix[0].count > 0 else { return 0 }
 5         var m = matrix.count, n = matrix[0].count
 6         var dp =  Array(repeating: 0, count: n+1)
 7         var res = 0
 8         var pre = 0
 9         for i in 0..<m {
10             for j in 1...n {
11                 var t = dp[j]
12                 if matrix[i][j-1] == "0" { dp[j] = 0 }
13                 else {
14                     dp[j] = min(min(dp[j], dp[j-1]), pre) + 1
15                      res = max(res, dp[j])
16                 }
17                 pre = t
18             }
19         }
20         return res * res
21     }
22 }

416ms

 1 class Solution {
 2     func maximalSquare(_ matrix: [[Character]]) -> Int {
 3         guard !matrix.isEmpty else { return 0 }
 4         
 5         var maxLength = 0
 6         var areaArray = Array(repeating: Array(repeating: 0, count: matrix[0].count), count: matrix.count)
 7         
 8         for i in 0..<matrix.count {
 9             for j in 0..<matrix[0].count {
10                 if i == 0 || j == 0{
11                     areaArray[i][j] = matrix[i][j] == "0" ? 0 : 1
12                 }else {
13                     if matrix[i - 1][j] == "0" && matrix[i][j - 1] == "0" && matrix[i - 1][j - 1] == "0" {
14                         areaArray[i][j] = matrix[i][j] == "0" ? 0 : 1
15                     }else if matrix[i][j] == "1" {
16                         areaArray[i][j] = min(min(areaArray[i - 1][j], areaArray[i][j - 1]), areaArray[i - 1][j - 1]) + 1
17                     }
18                 }
19                 maxLength = max(maxLength, areaArray[i][j])
20             } 
21         }
22         
23         return maxLength * maxLength
24     }
25 }

420ms

 1 class Solution {
 2     func maximalSquare(_ matrix: [[Character]]) -> Int {
 3       if matrix.count == 0 {
 4         return 0
 5       }
 6 
 7       let rows = matrix.count, cols = matrix[0].count
 8       var maxsqlen = 0
 9 
10       // make a copy of matrix
11       var dp = [[Int]](repeating: ([Int](repeating: 0, count: cols + 1)), count: rows + 1)
12 
13       for i in 1...rows {
14         for j in 1...cols {
15           // if previous i and previous j is 1
16           if matrix[i - 1][j - 1] == "1" {
17             // find the minimum of [i - 1][j], [i - 1][j - 1], [i][j - 1] and add 1
18             dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]) + 1
19             maxsqlen = max(maxsqlen, dp[i][j])
20           }
21         }
22       }
23 
24       return maxsqlen * maxsqlen
25     }
26 }

436ms

 1 class Solution {
 2     func maximalSquare(_ matrix: [[Character]]) -> Int {
 3         var maxCount = 0
 4         for row in 0..<matrix.count {
 5             for col in 0..<matrix[0].count {
 6                 guard matrix[row][col] == "1" else { continue }
 7                 var currentCount = 1
 8                 var base = 1
 9                 let startRow = row
10                 let startCol = col
11                 var newRow = row + 1
12                 var newCol = col + 1
13                 boundaryCheck: while newRow < matrix.count && newCol < matrix[0].count {
14                     for nextRow in startRow...newRow {
15                         if matrix[nextRow][newCol] != "1" {
16                             break boundaryCheck
17                         }
18                     }
19 
20                     for nextCol in startCol...newCol {
21                         if matrix[newRow][nextCol] != "1" {
22                             break boundaryCheck
23                         }
24                     }
25                     base += 1
26                     currentCount = base * base
27                     newRow += 1
28                     newCol += 1
29                 }
30                 maxCount = max(maxCount, currentCount)
31             }
32         }
33         return maxCount
34     }    
35 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Swift_String的操作发布时间:2022-07-13
下一篇:
[Swift]LeetCode1080.根到叶路径上的不足节点|InsufficientNodesinRoottoLeafPaths ...发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap