新鲜出炉12/14 Google电面 被扣shi盆子

/
+ . + . + . + . +
.    .          .    .
+ . +        +   +
.    .          .    .
+ . + . + . + . +
.    .               .
+   + . + . + . +

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

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

最右下角有条边有缺失，所以不算）

然后问题是 给一个图 要你求这个图里一共有多少正方形。这个图怎么表示要自己去想。(没有input)


各位大神有什么思路吗？

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

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

已在之前的回复中补充 python实现 和test case。直接跑就行。

请问有知道这道题怎么表示点和边么 什么样的input能很好的表示点的存在和边的链接？

不会什么巧妙的方法。感觉最笨的方法就是从点开始然后，边的长度从1-n全部遍历一次，然后判断能不能形成正方形。。。

这个题的奥义在于都让你自定义数据结构了，那就怎么简单怎么来。 你可把所有交点定义为一张图的node，他们之间的连线定义成edge（在邻接表里带上长度和方向）。 然后非常naive的从每个点出发搜索往右边走找到candidate右上方的点，然后再查一下左下/右下是不是也在图中。
因为原题的坐标和长度可以是浮点数所以千万不要用二维数组。

很典型的matrix DP的题目，可以直接搜索下，有模版可以解答的。