狗店

回馈地里，口音听起来不是国人不是烙印

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

吟游诗人刘小翠 发表于 2018-11-29 11:00
是的，然后return的是四个顶点坐标
这题啥时候出的啊(;???Д??`)

上两次contest

有点类似 蠡口其五菱。只不过这里dp[j][q] 改为上次 j 列 和 q 列 同时为 1 时候的所在行 i 是多少。

1. int minRectangles(vector<vector<int>>& grid) {
   
2.         int row = grid.size(), col = grid[0].size();
   
3.         map<int, map<int,int>> g;
   
4.         unordered_map<int, unordered_map<int,int>> dp;
   
5.         for(int i = 0; i < row; ++i) {
   
6.             for(int j = 0; j < col; ++j) {
   
7.                 if(grid[i][j] == 1)
   
8.                     g[i][j] = 1;
   
9.             }
   
10.         }
    
11.         int res = INT_MAX;
    
12.         for(auto itr = g.begin(); itr != g.end(); ++itr) {
    
13.             int i = itr->first;
    
14.             for(auto jtr = g[i].begin(); jtr != g[i].end(); ++jtr) {
    
15.                 int j = jtr->first;
    
16.                 for(auto qtr = jtr; qtr != g[i].end(); ++qtr) {
    
17.                     int q = qtr->first;
    
18.                     int area = -1;
    
19.                     if(dp.find(j) != dp.end() && dp[j].find(q) != dp[j].end()) {
    
20.                         area = (q - j) * (i - dp[j][q]);
    
21.                     }
    
22.                     if(area > 0) {
    
23.                         res = min(res, area);
    
24.                     }
    
25.                     dp[j][q] = i;
    
26.                 }
    
27.             }
    
28.         }
    
29.         return res;
    
30.     }

复制代码

这里因为不知道点的边界是多少，所以不能使用一个固定的二维matrix去遍历，所以使用二维map。

楼主觉得这样做可以吗？

您好！
本帖隐藏的内容需要积分高于 250 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 250 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

感谢楼主分享，可以请问一下大致思路是什么样的吗？

按照x值排序，x相同就排序y，然后二分法找出两两x之间的最小y值差，更新最小值。时间复杂度，排序O(nlogn)。查找最小y值差，有多少组x为M，最大一组x里面的y的数量为K。O(M*K*logK)

請問是由4點做成長方形 還是兩點？

2018moment 发表于 2018/11/10 05:25:58
感谢楼主分享，可以请问一下大致思路是什么样的吗？

我大概是遍历所有的点然后找可以组成rect的其他点，然后找min。但是应该直接算xy差值就可以了。。。

huieewu 发表于 2018/11/10 06:06:21
請問是由4點做成長方形 還是兩點？

四点 zszszszs

foryousee 发表于 2018-11-9 17:33
按照x值排序，x相同就排序y，然后二分法找出两两x之间的最小y值差，更新最小值。时间复杂度，排序O(nlogn) ...

请问二分法在这里是怎么用的 可以详细说说吗

吟游诗人刘小翠 发表于 2018-11-10 06:07
我大概是遍历所有的点然后找可以组成rect的其他点，然后找min。但是应该直接算xy差值就可以了。。。

直接算xy差值的话怎么保证rect边和坐标轴平行呢。。。想不通求解释