[Swift]LeetCode1139.最大的以1为边界的正方形|Largest1-BorderedSquare

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

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

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

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given a 2D grid of 0s and 1s, return the number of elements in the largest square subgrid that has all 1s on its border, or 0 if one doesn't exist.

Example 1:

Input: grid = [[1,1,1],[1,0,1],[1,1,1]]
Output: 9

Example 2:

Input: grid = [[1,1,0,0]]
Output: 1

Constraints:

1 <= grid.length <= 100
1 <= grid[0].length <= 100
grid[i][j] is 0 or 1

给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大正方形子网格，并返回该子网格中的元素数量。如果不存在，则返回 0。

示例 1：

输入：grid = [[1,1,1],[1,0,1],[1,1,1]]
输出：9

示例 2：

输入：grid = [[1,1,0,0]]
输出：1

提示：

1 <= grid.length <= 100
1 <= grid[0].length <= 100
grid[i][j] 为 0 或 1

Runtime: 100 ms

Memory Usage: 21 MB

 1 class Solution {
 2     func largest1BorderedSquare(_ grid: [[Int]]) -> Int {
 3         var naxNum:Int = 0
 4         let m:Int = grid.count
 5         let n:Int = grid[0].count
 6         var hor:[[Int]] = [[Int]](repeating:[Int](repeating:0,count:n),count:m)
 7         var ver:[[Int]] = [[Int]](repeating:[Int](repeating:0,count:n),count:m)
 8         for i in 0..<m
 9         {
10             for j in 0..<n
11             {
12                 if grid[i][j] == 1
13                 {
14                     // auxillary horizontal array
15                     hor[i][j] = (j == 0) ? 1 : hor[i][j-1] + 1 
16                     // auxillary vertical array
17                     ver[i][j] = (i == 0) ? 1 : ver[i-1][j] + 1
18                 }
19             }            
20         }
21         for i in stride(from:m - 1,through:0,by:-1)
22         {
23             for j in stride(from:n - 1,through:0,by:-1)
24             {
25                 // choose smallest of horizontal and vertical value
26                 var small:Int = min(hor[i][j], ver[i][j])
27                 while (small > naxNum)
28                 {
29                     // check if square exists with 'small' length
30                     if ver[i][j-small+1] >= small &&  hor[i-small+1][j] >= small
31                     {
32                         naxNum = small
33                     }
34                     small -= 1
35                 }
36             }
37         }
38         return naxNum * naxNum
39     }
40 }

104ms

 1 class Solution {
 2     private func checkBottomRight(_ grid: [[Int]], row: Int, col: Int, length: Int) -> Bool {
 3         guard length > 1 else {
 4             return true
 5         }
 6         
 7         for i in 0..<length {
 8             if grid[row + i][col + length - 1] != 1 || grid[row + length - 1][col + i] != 1 {
 9                 return false
10             }
11         }
12         return true
13     }
14     
15     func largest1BorderedSquare(_ grid: [[Int]]) -> Int {
16         var maxLength = 0
17         for row in 0..<grid.count {
18             for col in 0..<grid[row].count {
19                 guard grid[row][col] == 1 else {
20                     continue
21                 }
22                 
23                 var i = 1
24                 while row + i < grid.count && grid[row + i][col] == 1 && col + i < grid[row].count && grid[row][col + i] == 1 {
25                     i += 1
26                 }
27                 while i > maxLength && !self.checkBottomRight(grid, row: row, col: col, length: i) {
28                     i -= 1
29                 }
30                 maxLength = Swift.max(maxLength, i)
31             }
32         }
33         return maxLength * maxLength
34     }
35 }

120ms

 1 class Solution {
 2     
 3     func largest1BorderedSquare(_ grid: [[Int]]) -> Int {
 4         var  ans = 0
 5         let rowSize = grid.count
 6         let colSize = grid[0].count
 7         
 8         func valid(x: Int,y: Int, edgeLength: Int) -> Bool {
 9             let lastY = y + edgeLength - 1
10             let lastX =  x + edgeLength - 1
11             for i in x...lastX {
12                 if grid[i][y] == 0 || grid[i][lastY] == 0{
13                     return false
14                 }
15             }
16             for j in y...lastY {
17                 if grid[x][j] == 0 || grid[lastX][j] == 0  {
18                     return false
19                 }
20             }
21             return true
22         }
23         for i in 0..<rowSize {
24             for j in 0..<colSize {
25                 if grid[i][j] == 1 {
26                     if ans == 0 {
27                         ans = 1
28                     }
29                     if i != rowSize - 1 && j != colSize - 1 {
30                         //---->right
31                         var m = j + 1
32                         while m < colSize && grid[i][m] == 1 {
33                             m += 1
34                         }
35                         var n = i + 1
36                         while n < rowSize &&  grid[n][j] == 1 {
37                             n += 1
38                         }
39                         var squreLength = min(n - i, m - j)
40                         while squreLength > ans {
41                             if valid(x: i, y: j, edgeLength: squreLength) {
42                                 ans = squreLength
43                             }
44                             squreLength -= 1
45                         }
46                     }
47                 }
48             }
49         }
50         return ans * ans
51     }
52 }

124 ms

 1 class Solution {
 2     func largest1BorderedSquare(_ grid: [[Int]]) -> Int {
 3         guard !grid.isEmpty, !grid[0].isEmpty else { return 0 }
 4         
 5         let m = grid.count
 6         let n = grid[0].count
 7         var horizontal = Array(repeating: Array(repeating: 0, count: n), count: m)
 8         var vertical = Array(repeating: Array(repeating: 0, count: n), count: m)
 9         
10         for i in 0..<m {
11             for j in 0..<n {
12                 if grid[i][j] > 0 {
13                     horizontal[i][j] = j == 0 ? 1 : horizontal[i][j-1] + 1
14                     vertical[i][j] = i == 0 ? 1 : vertical[i-1][j] + 1   
15                 }
16             }
17         }
18         
19         for l in (1...min(m,n)).reversed() {
20             for i in (0..<m-l+1) {
21                 for j in (0..<n-l+1) {
22                     if vertical[i+l-1][j] >= l, vertical[i+l-1][j+l-1] >= l,
23                        horizontal[i][j+l-1] >= l, horizontal[i+l-1][j+l-1] >= l {
24                            return l * l
25                     }
26                 }
27             }
28         }
29         
30         return 0
31     } 
32 }

244ms

 1 class Solution {
 2     func largest1BorderedSquare(_ grid: [[Int]]) -> Int {
 3         let M = grid.count
 4         let N = grid[0].count
 5         var left = [[Int]](repeating:[Int](repeating:0, count: N), count: M)
 6         var top = [[Int]](repeating:[Int](repeating:0, count: N), count: M)
 7         for i in grid.indices {
 8             for j in grid[0].indices {
 9                 if grid[i][j] == 1{
10                     left[i][j] = j > 0 ? left[i][j-1] + 1 : 1
11                     top[i][j] = i > 0 ? top[i-1][j] + 1 : 1
12                 }
13             }
14         }
15         for l in stride(from: min(M, N), to: 0, by: -1) {
16             for i in stride(from: 0, to: M - l + 1, by: 1) {
17                 for j in stride(from: 0, to: N - l + 1, by: 1) {
18                     if top[i + l - 1][j] >= l
19                     && top[i + l - 1][j + l - 1] >= l
20                     && left[i][j + l - 1] >= l
21                     && left[i + l - 1][j + l - 1] >= l {
22                         return l * l
23                     }
24                 }
25             }
26         }
27         return 0
28     }
29 }