題目: LeetCode - 835. Image Overlap
題目說明
給兩個只包含 0 和 1 的正方形陣列代表圖片,求兩者經過左右、上下平移後能造成 1 重疊的最多數量。
解題思路
先使用兩個陣列紀錄兩者圖片為 1 的所有座標,接著使用 HashMap 紀錄兩張圖片任意兩個 1 的偏移量相同的個數 ( 偏移量相同代表經過同樣的平移能使得兩者都重疊 ),最後找出最大值即可。
參考解法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| static auto __ = []() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0; }(); class Solution { public: int largestOverlap(vector<vector<int>>& A, vector<vector<int>>& B) { int n = A.size(), cnt = 0; vector<pair<int, int>> posA, posB; map<pair<int, int>, int> m; for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) { if(A[i][j]) posA.emplace_back(i, j); if(B[i][j]) posB.emplace_back(i, j); } for(auto& [xA, yA] : posA) for(auto& [xB, yB] : posB) ++m[{xB - xA, yB - yA}]; for(auto& [__, val] : m) cnt = max(cnt, val); return cnt; } };
|