DropBox OA Grid Illumination

给一个数N, 是正方形grid的边长。给一组灯的二维坐标，

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

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

空间复杂度n平方的话有的test case过不了，还要照顾时间复杂度

按照lz的方法，int[]row, int[]col, hashmap<int, int> diagonleft(就是x+y那条对角线key范围0 ~2n-2), hashmap<int, int>diagonright(x-y那条对角线，范围－（n-1）~n-1)，还弄了个hashset存灯的位置（放的是interger, x*n+y），遍历灯序列的时候，这四个都＋1，然后query的时候，query (i, j)周围四个点只要不出界的就去hashset里找是不是灯，如果是的话加入到一个list里，然后遍历这个list，对应row,col, diagonleft, diagonright都减少1，然后判断row, col, diagonleft, diagonright里row(i), col(j), diagonleft(i+j), diagonright(i-j)的count是否大于0,如果大于就是light,, 请问这个思路对吗，为什么就是只pass了3个case,好伤心，梦碎了

翻滚吧豆子 发表于 2016-10-23 17:53
1  把行  列   两条斜线编号(每方向斜线编2N-1)个号    2  将每个灯hash到对应的线的编号

请问hash是具体怎么做呢？比如（3，4）这个点，是row[3]++, col[4]++, diagon1[3+4]++, diagon2[3-4]++吗？像index是负数该如何弄呢？谢谢啦，虽然挂了，还是想死个明白～

请问lz网投等了多久发oa啊

yrfzh 发表于 2016-9-10 11:50
请问lz网投等了多久发oa啊

一两周吧

火火火bit 发表于 2016-9-10 12:23
一两周吧

明白了多谢lz啊

这样行吗，对每个灯，假设位置是(i, j)，把i，j，还有i - j，i + j分别存到4和multimap里面，记录该行，该列，以及两个斜线被多少个灯照亮。施工时候去掉周围八个再查map，施工完再加上。或者用multiset也行。

daniel_hl 发表于 2016-9-10 12:59
这样行吗，对每个灯，假设位置是(i, j)，把i，j，还有i - j，i + j分别存到4和multimap里面，记录该行，该 ...

如果你只存这样的四个map，怎么检查周围八个呢

火火火bit 发表于 2016-9-10 13:31
如果你只存这样的四个map，怎么检查周围八个呢

哦，总以为给出了一个matrix，那就再加一个保存点的set？

daniel_hl 发表于 2016-9-10 13:39
哦，总以为给出了一个matrix，那就再加一个保存点的set？

可以可以～

哇塞 宁神太厉害了

eros 发表于 2016-9-10 13:46
哇塞 宁神太厉害了

别逗了。。。