[Swift]LeetCode554.砖墙|BrickWall

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

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

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

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

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

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

There is a brick wall in front of you. The wall is rectangular and has several rows of bricks. The bricks have the same height but different width. You want to draw a vertical line from the top to the bottom and cross the leastbricks.

The brick wall is represented by a list of rows. Each row is a list of integers representing the width of each brick in this row from left to right.

If your line go through the edge of a brick, then the brick is not considered as crossed. You need to find out how to draw the line to cross the least bricks and return the number of crossed bricks.

You cannot draw a line just along one of the two vertical edges of the wall, in which case the line will obviously cross no bricks.

Example:

Input: [[1,2,2,1],
        [3,1,2],
        [1,3,2],
        [2,4],
        [3,1,2],
        [1,3,1,1]]

Output: 2

Explanation:

Note:

The width sum of bricks in different rows are the same and won't exceed INT_MAX.
The number of bricks in each row is in range [1,10,000]. The height of wall is in range [1,10,000]. Total number of bricks of the wall won't exceed 20,000.

你的面前有一堵方形的、由多行砖块组成的砖墙。这些砖块高度相同但是宽度不同。你现在要画一条自顶向下的、穿过最少砖块的垂线。

砖墙由行的列表表示。每一行都是一个代表从左至右每块砖的宽度的整数列表。

如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。你需要找出怎样画才能使这条线穿过的砖块数量最少，并且返回穿过的砖块数量。

你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。

示例：

输入: [[1,2,2,1],
      [3,1,2],
      [1,3,2],
      [2,4],
      [3,1,2],
      [1,3,1,1]]

输出: 2

解释:

提示：

每一行砖块的宽度之和应该相等，并且不能超过 INT_MAX。
每一行砖块的数量在 [1,10,000] 范围内，墙的高度在 [1,10,000] 范围内，总的砖块数量不超过 20,000。

264ms

 1 class Solution {
 2     func leastBricks(_ wall: [[Int]]) -> Int {
 3         guard !wall.isEmpty else {
 4             return 0
 5         }
 6         
 7         var sumToCount: [Int:Int] = [:]
 8         var maxCount = 0
 9         
10         for row in 0..<wall.count {
11             
12             var sum = 0
13             
14             for column in 0..<wall[row].count-1 {
15                 sum += wall[row][column]
16                 
17                 let count = sumToCount[sum, default: 0] + 1
18                 sumToCount[sum] = count
19                 
20                 maxCount = max(maxCount, count)
21             }
22         }
23         
24         return wall.count - maxCount
25     }
26 }

Runtime: 268 ms

Memory Usage: 19.1 MB

 1 class Solution {
 2     func leastBricks(_ wall: [[Int]]) -> Int {
 3         var mx:Int = 0
 4         var m:[Int:Int] = [Int:Int]()
 5         for a in wall
 6         {
 7             var sum:Int = 0
 8             for i in 0..<a.count - 1
 9             {
10                 sum += a[i]
11                 if m[sum] == nil
12                 {
13                     m[sum] = 1
14                 }
15                 else
16                 {
17                     m[sum]! += 1
18                 }                
19                 mx = max(mx, m[sum]!)
20             }
21         }
22         return wall.count - mx
23     }
24 }

268ms

 1 class Solution {
 2     func leastBricks(_ wall: [[Int]]) -> Int {
 3         if wall.isEmpty || wall[0].isEmpty { return 0 }
 4         
 5         var results = [Int: Int]()
 6         for i in 0..<wall.count {
 7             var idx = 0
 8             for j in 0..<wall[i].count - 1 {
 9                 idx += wall[i][j]
10                 results[idx, default:0] += 1
11             }
12         }
13         
14         return wall.count - (results.values.max() ?? 0)
15     }
16 }

352ms

 1 class Solution {
 2     func leastBricks(_ wall: [[Int]]) -> Int {
 3         var map = [Int:Int]()
 4         var minCount = wall.count
 5         wall.forEach { (ele) in
 6             var sum = 0
 7            for i in 0..<ele.count-1 {
 8                 sum += ele[i]
 9                 map[sum] = (map[sum] ?? 0) + 1
10             }
11         }
12         map.forEach { (_, value) in
13             minCount = min(minCount, wall.count - value)
14         }
15         return minCount
16     }
17 }

388ms

 1 class Solution {
 2     func leastBricks(_ wall: [[Int]]) -> Int {
 3         var map: [Int: Int] = [:]
 4         for row in wall {
 5             var sum = 0
 6             for i in 0 ..< (row.count - 1) {
 7                 sum += row[i]
 8                 map[sum] = (map[sum] ?? 0) + 1
 9             }
10         }
11         var res = wall.count
12         for key in map.keys {
13             res = min(res, wall.count - map[key]!)
14         }
15         return res
16     }
17 }

512ms

 1 class Solution {
 2     func leastBricks(_ wall: [[Int]]) -> Int {
 3         var map: [Int:Int] = [:]
 4         for row in wall {
 5             var tmp = 0
 6             for i in 0..<(row.count - 1) {
 7                 tmp += row[i]
 8                 map[tmp] = (map[tmp] ?? 0) + 1
 9             }
10         }
11         var count = wall.count
12         for (key,val) in map {
13             count = min(wall.count - val, count)
14         }
15         return count 
16     }
17 }

640ms

 1 class Solution {
 2     func leastBricks(_ wall: [[Int]]) -> Int {
 3 guard wall.count > 0 else { return 0 }
 4     var offsetsWithHoles = Array(repeating: 0, count: 65536)
 5     for row in wall {
 6         var offset = 0
 7         for brick in row.dropLast() {
 8             offset += brick
 9             offsetsWithHoles[offset] += 1
10         }
11     }
12     return wall.count - offsetsWithHoles.max()!
13     }
14 }