狗家实习电面面经，感觉差不多跪了，来攒人品……

第一题我就是brute force做的，四个点四个点一扫，然后看是不是一个方形，是的话计算一下面积……实在是想不出别的了我……

求问楼主，长方形那个题，可不可能是斜着的情况，也就是长方形的四条边和x、y轴不是水平的情况？

第一题，如果是用点1点2点3点4组成矩形左上右下俩个（d1, d2）(d3,d4)，那么最简单就是从数组0开始到倒数第四个点，依次算pow(d1-d3, 2)+pow(d4-d2,2);然后我能想到的优化就是扫一遍数组，建立diff[i][i+2]= pow(d[i+2])-d[i], 2),然后就diff[i]+diff[i+1]到diff[i+1]+diff[i+2].....取最小值

打错了。。。建立diff[i]= pow(d[i+2])-d[i], 2),然后就diff[i]+diff[i+1]取最小。。。

lalasparrow 发表于 2017-11-26 07:32
求问楼主，长方形那个题，可不可能是斜着的情况，也就是长方形的四条边和x、y轴不是水平的情况？

不会的，就是垂直的。

shu16 发表于 2017-11-26 10:26
不会的，就是垂直的。

好的，谢谢楼主..！

征夷大将军 发表于 2017-11-26 08:55
第一题，如果是用点1点2点3点4组成矩形左上右下俩个（d1, d2）(d3,d4)，那么最简单就是从数组0开始到倒数第 ...

并不是按顺序出现的啊……

shu16 发表于 2017-11-26 10:26
不会的，就是垂直的。

第一题是不是https://leetcode.com/problems/maximal-rectangle/description/ 啊？

续命神哈 发表于 2017-11-26 11:05
第一题是不是https://leetcode.com/problems/maximal-rectangle/description/ 啊？

不是，这是个二维数组，那个一维数组，里面存的是点，四个点就可以围城一个方形

个人感觉第一题3 for loops就可以做了吧
先把所有点都放进set里，然后根据三个点可以算出能组成长方形的第四个点，查找第四个点是不是在set里
是的话，求global min就行