【leetcode】1001. 网格照明 代码优化记录
【Kotlin】代码优化记录——从二维到一维再到set
我太菜啦，这里记录一下自己思考的过程——如何从超内存再到超时最后到卡线过！
像我这样的菜狗都可以模拟的出来，没有做不出的困难题，只有懒惰不愿思考的人！
可能大家都有解题中 “开灯” “关灯” 的想法，但是如何将这些想法化简成为最终答案还是需要不断思考滴！
1、第一想法（超内存）
第一个想法就是直接模拟，模拟了10分钟，debug了20分钟…
模拟方式如下:
class Solution {
// 开着的灯的坐标
val openedLamps: MutableSet<IntArray> = mutableSetOf()
// 亮着的坐标
val lightedList: MutableList<IntArray> = mutableListOf()
// 附近8个格子方向
val directions = arrayOf(
intArrayOf(0,0), // 虽然是附近8个格子，但是自己这个格子也要算进去
intArrayOf(-1,0), intArrayOf(-1,1), intArrayOf(0,1), intArrayOf(1,1),
intArrayOf(1,0), intArrayOf(1,-1), intArrayOf(0,-1), intArrayOf(-1,-1)
)
fun gridIllumination(n: Int, lamps: Array<IntArray>, queries: Array<IntArray>): IntArray {
// 整个网格
val grid: Array<IntArray> = Array(size = n, init = {IntArray(n)})
// 返回的结果
val res = mutableListOf<Int>()
// 第一次遍历整个网格，找出开着的灯，并点亮路
for (i in grid.indices) {
for (j in grid[0].indices) {
// 如果这个坐标的灯开了，添加这个坐标到开灯坐标里
for (lamp in lamps) {
if (lamp[0] == i && lamp[1] == j) {
openedLamps += intArrayOf(i,j)
// 同时，将路给点亮
handleWays(grid,i,j) {
lightedSet, xy ->
lightedSet += xy
}
}
}
}
}
// 进行queries操作
for (query in queries) {
// 当前query的坐标是被点亮就返回1，否则返回0
var flag = true
for (lighted in lightedList) {
if (query[0] == lighted[0] && query[1] == lighted[1]) {
res += 1
flag = false
break
}
}
if (flag) {
res += 0
}
// 无论是否被点亮，当前查询的附近8格的灯都需要关闭
closeLight(query,grid)
}
return res.toIntArray()
}
// 关闭附近8格的灯，并且让路变暗
fun closeLight(query: IntArray,grid: Array<IntArray>) {
// 遍历8个方向
for (direction in directions) {
val nextRow = query[0] + direction[0]
val nextCol = query[1] + direction[1]
// 如果下个位置没有超出边界，并且这个位置开着灯，关这个地方的灯
if (nextRow in grid.indices &&
nextCol in grid[0].indices ) {
for (openedLamp in openedLamps) {
if (openedLamp[0] == nextRow && openedLamp[1] == nextCol) {
// 关灯
handleWays(grid,nextRow,nextCol) {
lightedSet, xy ->
for (lighted in lightedSet) {
// 变暗
if (xy[0] == lighted[0] && xy[1] == lighted[1]) {
lightedSet -= lighted
break
}
}
}
// 循环中无法删除，就赋值到界外
openedLamp[0] = -1
openedLamp[1] = -1
}
}
}
}
}
// 点亮（变暗）路
fun handleWays(grid: Array<IntArray>, x: Int, y: Int, action: (lightedSet: MutableList<IntArray>, xy: IntArray) -> Unit) {
// 点亮每行每列的路
for (i in grid.indices) {
for (j in grid[0].indices) {
// 如果是同一行或者同一列就点亮
if (i == x || j == y) {
action(lightedList, intArrayOf(i,j))
}
}
}
// 点亮右下角的路
handleObliqueAngleWays(grid,x,y,1,1,action)
// 点亮左下角的路
handleObliqueAngleWays(grid,x,y,1,-1,action)
// 点亮右上角的路
handleObliqueAngleWays(grid,x,y,-1,1,action)
// 点亮左上角的路
handleObliqueAngleWays(grid,x,y,-1,-1,action)
}
// 点亮（变暗）斜角的路
fun handleObliqueAngleWays(grid: Array<IntArray>, x: Int, y: Int, d1: Int, d2: Int, action: (lightedSet: MutableList<IntArray>, xy: IntArray) -> Unit) {
var row = x + d1
var col = y + d2
while (row in grid.indices && col in grid[0].indices) {
action(lightedList, intArrayOf(row,col))
row += d1
col += d2
}
}
}
// 测试
fun main() {
val solution = Solution()
val gridIllumination = solution.gridIllumination(
6,
arrayOf(intArrayOf(2, 5), intArrayOf(4,2), intArrayOf(0,3), intArrayOf(0,5), intArrayOf(1,4), intArrayOf(4,2),
intArrayOf(3,3), intArrayOf(1,0)
),
arrayOf(intArrayOf(4, 3), intArrayOf(3, 1), intArrayOf(5,3), intArrayOf(0,5), intArrayOf(4,4), intArrayOf(3,3))
)
println("结果"+gridIllumination.joinToString())
for (list in solution.lightedList) {
print("[${list.joinToString()}],")
}
println()
for (openedLamp in solution.openedLamps) {
print("[${openedLamp.joinToString()}],")
}
}
最后直接内存溢出，发现原因是，我是用的是一个list来填装被照亮的路，而题目中n的数据范围是10的九次方，直接超内存了
2、第二想法（超时）
之后的想法是，我都用list来存放照亮的路了，为啥不用hashmap来存呢，仍然是模拟
优化就是，将一个二维数组转为一维数组，每一个一维数组的下标可以用i * n + j来表示
最后压缩成一个一维状态
然后我也懒得优化，每次关一个灯之后，照亮的路的hashmap直接clear，将存着开灯的list删去这个点，重新将hashmap赋值，给出亮着的路
class Solution {
// 开着的灯的坐标
val openedLamps: MutableSet<Long> = mutableSetOf()
// 附近8个格子方向+当前自己的格子
val directionsEight = arrayOf(
intArrayOf(0,0), // 虽然是附近8个格子，但是自己这个格子也要算进去
intArrayOf(-1,0), intArrayOf(-1,1), intArrayOf(0,1), intArrayOf(1,1),
intArrayOf(1,0), intArrayOf(1,-1), intArrayOf(0,-1), intArrayOf(-1,-1)
)
// 斜线的4个方向
val directionsFour = arrayOf(intArrayOf(1,1), intArrayOf(1,-1), intArrayOf(-1,1), intArrayOf(-1,-1))
// 哈希map
val allMap = mutableMapOf<Long,Boolean>()
fun gridIllumination(n: Int, lamps: Array<IntArray>, queries: Array<IntArray>): IntArray {
val res = mutableListOf<Int>()
val N = n.toLong()
// 遍历整个网格
for (i in 0 until n) {
for (j in 0 until n) {
// 找出灯的位置
for (lamp in lamps) {
if (lamp[0] == i && lamp[1] == j) {
val idx = i * N + j
openedLamps += (idx)
// 同时点亮路
lightWay(i,j,N)
}
}
}
}
// 执行queries操作
for (query in queries) {
res += if (allMap[query[0] * N + query[1]] == true) 1 else 0
// 查询点亮之后就去关灯
closeLight(query,N)
}
return res.toIntArray()
}
// 关灯
fun closeLight(query: IntArray,N: Long) {
for (direction in directionsEight) {
val nextRow = query[0] + direction[0]
val nextCol = query[1] + direction[1]
// 如果下个位置没有超出边界，并且这个位置开着灯，关这个地方的灯
if (nextRow in 0 until N &&
nextCol in 0 until N &&
nextRow*N+nextCol in openedLamps) {
openedLamps -= nextRow*N+nextCol
}
}
// 关灯之后，重新计算点亮的路
allMap.clear()
for (i in 0 until N) {
for (j in 0 until N) {
if (i*N+j in openedLamps) {
lightWay(i.toInt(),j.toInt(),N)
}
}
}
}
// 点亮路
fun lightWay(x: Int, y: Int, N: Long) {
// 如果是同一行或者同一列就点亮
for (i in 0 until N) {
for (j in 0 until N) {
if (i == x.toLong() || j == y.toLong()) {
allMap[i*N+j] = true
}
}
}
// 斜向点亮
for (direction in directionsFour) {
var row = x + direction[0]
var col = y + direction[1]
while (row in 0 until N && col in 0 until N) {
allMap[row*N+col] = true
row += direction[0]
col += direction[1]
}
}
}
}
当然结果不言而喻，内存没问题，但是超时了，同样是数据量的问题
3、最终想法
超时是因为我遍历了网格中的每一个点，判断每一个点是否开着灯
但是我们为什么不把问题简化，直接用开着灯的每一行来判断呢？
从每一个点到每一行\斜行，优化的时间非常之大
这次我们来维护4个list，每一个list对应——行、列、左斜行、右斜行
我们通过判断当前这个点所在的行、列、左斜行、右斜行是否被点亮，同时如果关灯，那么就是这个灯的位置的行、列、左斜行、右斜行从对应的list中删除
这个思想虽然又是一维，但是从一维长数组（n方），到了一维的4长度数组，我们只要维护这4个list就完事了
其实这一种思想，是将我的第一想法改为了，从维护一个亮着的坐标list–>到维护四个亮着的行、列、斜边
最后卡过了
最终代码如下：
class Solution {
// 附近8个格子方向+当前自己的格子
val directions = arrayOf(
intArrayOf(0,0), // 虽然是附近8个格子，但是自己这个格子也要算进去
intArrayOf(-1,0), intArrayOf(-1,1), intArrayOf(0,1), intArrayOf(1,1),
intArrayOf(1,0), intArrayOf(1,-1), intArrayOf(0,-1), intArrayOf(-1,-1)
)
fun gridIllumination(n: Int, lamps: Array<IntArray>, queries: Array<IntArray>): IntArray {
// 返回值
val res = mutableListOf<Int>()
// 路灯set
val openedLampsSet = mutableSetOf<Int>()
// 行、列、右斜线、左斜线的list
val rowList = mutableListOf<Int>()
val colList = mutableListOf<Int>()
val rightList = mutableListOf<Int>()
val leftList = mutableListOf<Int>()
// 遍历路灯
for (lamp in lamps) {
// 将路灯存入set中
if (lamp[0]*n+lamp[1] !in openedLampsSet) {
openedLampsSet += lamp[0]*n+lamp[1]
// 点亮道路
rowList += lamp[0]
colList += lamp[1]
leftList += (lamp[0] + lamp[1])
rightList += (n + lamp[1] - lamp[0] - 1)
}
}
// 关灯
for (query in queries) {
res += if (query[0] in rowList ||
query[1] in colList ||
query[0]+query[1] in leftList ||
n+query[1]-query[0]-1 in rightList) 1 else 0
// 遍历9个位置，关灯
for (direction in directions) {
val nextRow = query[0] + direction[0]
val nextCol = query[1] + direction[1]
// 如果位置上有灯，给它关了
if (nextRow * n + nextCol in openedLampsSet) {
openedLampsSet -= nextRow * n + nextCol
// 这一行、列、左斜边、右斜边都不亮了
rowList -= nextRow
colList -= nextCol
leftList -= (nextRow + nextCol)
rightList -= (n + nextCol - nextRow - 1)
}
}
}
return res.toIntArray()
}
}