[Swift]LeetCode1183. 矩阵中 1 的最大数量 ｜ Maximum Number of Ones

概述★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ ?微信公众号：为敢（WeiGanTechnologies） ?博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/） ?GitHub地址：https://github.com/strengthen/LeetCode ?原文地址：https://www.cnblogs.com/s

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

ConsIDer a matrix M with dimensions wIDth * height,such that every cell has value 0 or 1,and any square sub-matrix of M of size sIDeLength * sIDeLength has at most maxOnes ones.

Return the maximum possible number of ones that the matrix M can have.

 

Example 1:

input: wIDth = 3,height = 3,sIDeLength = 2,maxOnes = 1Output: 4Explanation:In a 3*3 matrix,no 2*2 sub-matrix can have more than 1 one.The best solution that has 4 ones is:[1,1][0,0][1,1]

Example 2:

input: wIDth = 3,maxOnes = 2Output: 6Explanation:[1,1][1,1]

 

Constraints:

1 <= wIDth,height <= 100 1 <= sIDeLength <= wIDth,height 0 <= maxOnes <= sIDeLength * sIDeLength

 

现在有一个尺寸为 wIDth * height 的矩阵 M，矩阵中的每个单元格的值不是 0 就是 1。

而且矩阵 M 中每个大小为 sIDeLength * sIDeLength 的 正方形 子阵中，1 的数量不得超过 maxOnes。

请你设计一个算法，计算矩阵中最多可以有多少个 1。

 

示例 1：

输入：wIDth = 3,maxOnes = 1输出：4解释：题目要求：在一个 3*3 的矩阵中，每一个 2*2 的子阵中的 1 的数目不超过 1 个。最好的解决方案中，矩阵 M 里最多可以有 4 个 1，如下所示：[1,1]

示例 2：

输入：wIDth = 3,maxOnes = 2输出：6解释：[1,1]

 

提示：

1 <= wIDth,height 0 <= maxOnes <= sIDeLength * sIDeLength Runtime: 32 ms Memory Usage: 21 MB

 1 class Solution { 2     func maximumNumberOfOnes(_ wIDth: Int,_ height: Int,_ sIDeLength: Int,_ maxOnes: Int) -> Int { 3         var res:[Int] = [Int]() 4         for i in 0..<sIDeLength 5         { 6             for j in 0..<sIDeLength 7             { 8                 res.append(((wIDth-i-1)/sIDeLength+1)*((height-j-1)/sIDeLength+1)) 9             }10         }11         res = res.sorted(by:>)12         var ans:Int = 013         for i in 0..<maxOnes14         {15             ans += res[i]16         }17         return ans18     }19 }

总结

以上是内存溢出为你收集整理的[Swift]LeetCode1183. 矩阵中 1 的最大数量 ｜ Maximum Number of Ones全部内容，希望文章能够帮你解决[Swift]LeetCode1183. 矩阵中 1 的最大数量 ｜ Maximum Number of Ones所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。