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

[Swift]LeetCode554.砖墙|BrickWall

原作者: [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:

  1. The width sum of bricks in different rows are the same and won't exceed INT_MAX.
  2. 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

解释: 

 

提示:

  1. 每一行砖块的宽度之和应该相等,并且不能超过 INT_MAX。
  2. 每一行砖块的数量在 [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 }

 

 


鲜花

握手

雷人

路过

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

请发表评论

全部评论

专题导读
上一篇:
[Swift实际操作]七、常见概念-(2)点CGPoint和变形CGAffineTransform的使用 ...发布时间:2022-07-13
下一篇:
swiftSDWebImage使用发布时间: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