tusimple SDE general电面一轮挂经

SDE new grad General 岗位
发一道图森的电面题，没有做出来，第一次遇到这样的题，没有什么思路。
输入一个足够大的二维矩阵，矩阵元素只有0 和 1， 我们把这个矩

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

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

---- |-----
1 1 | 1 1
0 0 | 0 0
return true

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

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

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

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

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

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

感觉是用dfs + backtracking试遍所有分割的可能

AlchemistTan 发表于 2020-3-5 20:04
我觉得可以根据定义来做，先把整个matrix扫一遍，算出每行每列的1的个数。然后纵向每一刀要左边必须有m + 1 ...

请问有没有好的方法在已知怎么分割的情况下快速验证每个submatrix的和相等？

或许你可以换一种思路，就拿我第一次回答的例子来看把，切割位置分别都在正中间，我们记录下切割位置为 2 和 2，那么你就可以知道各个submatrix的 i j的范围，比如第一个submatrix 就是 0 < i < 2,  0 < j < 2,后面的submatrix也是同样到理，这样的话就剩去了你说的二分查找位置，其实我一开始的想法就是这样做遍历，可能没说清楚。

能不能分别求 axis sum 然后尝试分割？ 如果能同时做到 equal cut on axis 0 with p lines 和 equal cut on axis 1 with q lines 那么就有解？

思路大概是：
假设这个是可以被割开的，然后我们sum over axis 0 那么 axis 0 上的割线应该刚好能把 axis sum 分割，axis 1 也一样。

顶顶 发表于 2020-3-8 06:51
请问有没有好的方法在已知怎么分割的情况下快速验证每个submatrix的和相等？

可以参考刷题网304