สมมติว่าเรามีเมทริกซ์ M ที่มีขนาด กว้าง x สูง ซึ่งทุกเซลล์มีค่า 0 หรือ 1 และเมทริกซ์ย่อยสี่เหลี่ยมใดๆ ของ M ที่มีขนาด l x l มีจำนวนสูงสุด maxOnes เราต้องหาจำนวนสูงสุดของเมทริกซ์ M ที่เป็นไปได้
ดังนั้น หากอินพุตเป็น w =3, h =3, l =2, maxOnes =1 ผลลัพธ์จะเป็น 4 เช่นเดียวกับในเมทริกซ์ 3*3 ไม่มีเมทริกซ์ย่อย 2*2 ตัวที่มีมากกว่า 1 ตัว . ทางออกที่ดีที่สุดที่มี 4 ข้อคือ −
| 1 | 0 | 1 |
| 0 | 0 | 0 |
| 1 | 0 | 1 |
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ยกเลิก :=0
-
สร้างตารางอาร์เรย์ 2 มิติหนึ่งขนาด n x n
-
สำหรับการเริ่มต้น i :=0 เมื่อฉัน <ความสูง อัปเดต (เพิ่ม i ขึ้น 1) ทำ -
-
สำหรับการเริ่มต้น j :=0 เมื่อ j
-
เพิ่ม sq[i mod n, j mod n] ขึ้น 1
-
-
-
กำหนดอาร์เรย์ v
-
สำหรับการเริ่มต้น i :=0 เมื่อ i
-
สำหรับการเริ่มต้น j :=0 เมื่อ j
-
ใส่ sq[i, j] ต่อท้าย v
-
-
-
เรียงลำดับอาร์เรย์ v ในลำดับย้อนกลับ
-
สำหรับการเริ่มต้น i :=0, j :=0 เมื่อ i <ขนาดของ v และ j
-
รีเทิร์น
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maximumNumberOfOnes(int width, int height, int n, int maxOnes) {
int ret = 0;
vector < vector <int> > sq(n, vector <int>(n));
for(int i = 0; i < height; i++){
for(int j = 0; j < width; j++){
sq[i % n][j % n]++;
}
}
vector <int> v;
for(int i = 0; i < n; i++){
for(int j = 0; j < n ; j++){
v.push_back(sq[i][j]);
}
}
sort(v.rbegin(), v.rend());
for(int i = 0, j = 0; i < v.size() && j < maxOnes; i++, j++){
ret += v[i];
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.maximumNumberOfOnes(3,3,2,1));
} อินพุต
3, 3, 2, 1
ผลลัพธ์
4
