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

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
?微信公众号：为敢（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 = 1
Output: 4
Explanation:
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 = 2
Output: 6
Explanation:
[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

 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 = 0
13         for i in 0..<maxOnes
14         {
15             ans += res[i]
16         }
17         return ans
18     }
19 }