DropBox OA Grid Illumination

robotwish 发表于 2016-9-13 03:42
请问对角线是每个点(i + 1, j + 1) (i + 1, j - 1).... 四个点方向上的线还是只有在中间对角线上的点才存在 ...

每个点，不止最长的两条

有人全过了test case么？可以分享一下代码吗

火火火bit 发表于 2016-9-13 11:45
嗯，虽然大数据的test case没过，还是给电面了

嗯我只过了6个test case也给电面了

yhx189 发表于 2016-9-14 07:57
嗯我只过了6个test case也给电面了

你使用了什么方法的呢？n^2?

Bitdance 发表于 2016-9-14 08:16
你使用了什么方法的呢？n^2?

就是把每一行，每一列，每一个对角线的灯的位置都存到一个hashset里面。时间复杂度是操作的次数L, 空间复杂度是 M* N

lz能分享一下码吗？

yhx189 发表于 2016-9-14 08:37
就是把每一行，每一列，每一个对角线的灯的位置都存到一个hashset里面。时间复杂度是操作的次数L, 空间复 ...

能分享一下码嘛

Bitdance 发表于 2016-9-14 06:02
有人全过了test case么？可以分享一下代码吗

我全过了，算法跟你差不多

大概就是4个hashmap存横竖对角线的lamp count，1个hashset存位置
关灯的时候就遍历9个点，开灯的时候再加回来。这样时间复杂度是O（N）

wcyz666 发表于 2016-9-14 15:40
我全过了，算法跟你差不多

大概就是4个hashmap存横竖对角线的lamp count，1个hashset存位置

你好，我有点不太理解。能详细说下map的key,vaue 还有set都存的是什么吗？谢谢了

lz 是海投的吗？