★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10430537.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
On a N x N grid of cells, each cell (x, y) with 0 <= x < N and 0 <= y < N has a lamp.
Initially, some number of lamps are on. lamps[i] tells us the location of the i-th lamp that is on. Each lamp that is on illuminates every square on its x-axis, y-axis, and both diagonals (similar to a Queen in chess).
For the i-th query queries[i] = (x, y), the answer to the query is 1 if the cell (x, y) is illuminated, else 0.
After each query (x, y) [in the order given by queries], we turn off any lamps that are at cell (x, y) or are adjacent 8-directionally (ie., share a corner or edge with cell (x, y).)
Return an array of answers. Each value answer[i] should be equal to the answer of the i-th query queries[i].
Example 1:
Input: N = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
Output: [1,0]
Explanation:
Before performing the first query we have both lamps [0,0] and [4,4] on.
The grid representing which cells are lit looks like this, where [0,0] is the top left corner, and [4,4] is the bottom right corner:
1 1 1 1 1
1 1 0 0 1
1 0 1 0 1
1 0 0 1 1
1 1 1 1 1
Then the query at [1, 1] returns 1 because the cell is lit. After this query, the lamp at [0, 0] turns off, and the grid now looks like this:
1 0 0 0 1
0 1 0 0 1
0 0 1 0 1
0 0 0 1 1
1 1 1 1 1
Before performing the second query we have only the lamp [4,4] on. Now the query at [1,0] returns 0, because the cell is no longer lit.
Note:
1 <= N <= 10^90 <= lamps.length <= 200000 <= queries.length <= 20000lamps[i].length == queries[i].length == 2
在 N x N 的网格上，每个单元格 (x, y) 上都有一盏灯，其中 0 <= x < N 且 0 <= y < N 。
最初，一定数量的灯是亮着的。lamps[i] 告诉我们亮着的第 i 盏灯的位置。每盏灯都照亮其所在 x 轴、y 轴和两条对角线上的每个正方形（类似于国际象棋中的皇后）。
对于第 i 次查询 queries[i] = (x, y)，如果单元格 (x, y) 是被照亮的，则查询结果为 1，否则为 0 。
在每个查询 (x, y) 之后 [按照查询的顺序]，我们关闭位于单元格 (x, y) 上或其相邻 8 个方向上（与单元格 (x, y) 共享一个角或边）的任何灯。
返回答案数组 answer。每个值 answer[i] 应等于第 i 次查询 queries[i] 的结果。
示例：
输入：N = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]] 输出：[1,0] 解释： 在执行第一次查询之前，我们位于 [0, 0] 和 [4, 4] 灯是亮着的。 表示哪些单元格亮起的网格如下所示，其中 [0, 0] 位于左上角： 1 1 1 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1 1 1 1 然后，由于单元格 [1, 1] 亮着，第一次查询返回 1。在此查询后，位于 [0，0] 处的灯将关闭，网格现在如下所示： 1 0 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 1 1 1 1 1 1 在执行第二次查询之前，我们只有 [4, 4] 处的灯亮着。现在，[1, 0] 处的查询返回 0，因为该单元格不再亮着。
提示：
1 <= N <= 10^90 <= lamps.length <= 200000 <= queries.length <= 20000lamps[i].length == queries[i].length == 2
1612ms
1 class Solution { 2 func gridIllumination(_ N: Int, _ lamps: [[Int]], _ queries: [[Int]]) -> [Int] { 3 var myLamps = [Int:[Int:Bool]](minimumCapacity: lamps.count) 4 5 var results = Array(repeating: 0, count: queries.count) 6 7 var row = [Int : Int](minimumCapacity: 20000) 8 var col = [Int: Int](minimumCapacity: 20000) 9 10 var diag1 = [Int: Int](minimumCapacity: 20000) 11 var diag2 = [Int: Int](minimumCapacity: 20000) 12 13 for lamp in lamps { 14 row[lamp[0], default: 0] += 1 15 col[lamp[1], default: 0] += 1 16 17 diag1[lamp[0] + lamp[1], default: 0] += 1 18 diag2[lamp[0] - lamp[1], default: 0] += 1 19 20 myLamps[lamp[0], default: [Int:Bool]() ][lamp[1]] = true 21 } 22 23 func lightTo(_ point: [Int], _ lamp: [Int]) -> Bool { 24 if point[0] == lamp[0] || point[1] == lamp[1] { 25 return true 26 } 27 if abs(point[0] - lamp[0]) == abs(point[1] - lamp[1]){ 28 return true 29 } 30 return false 31 } 32 33 34 var removed = Array<[Int]>() 35 removed.reserveCapacity(10) 36 37 for i in 0..<queries.count { 38 let query = queries[i] 39 if row[query[0], default: 0] > 0 || col[query[1], default: 0] > 0 { 40 results[i] = 1 41 } else if diag1[query[0] + query[1], default: 0] > 0 || diag2[query[0] - query[1], default: 0] > 0{ 42 results[i] = 1 43 } 44 45 removed.removeAll(keepingCapacity: true) 46 47 for i in -1...1 { 48 let x = query[0] + i 49 for j in -1...1 { 50 let y = query[1] + j 51 52 if myLamps[x]?[y] == true { 53 removed.append([x,y]) 54 myLamps[x]!.removeValue(forKey: y) 55 } 56 } 57 } 58 59 60 for lamp in removed { 61 row[lamp[0]] = row[lamp[0]]! - 1 62 col[lamp[1]] = col[lamp[1]]! - 1 63 diag1[lamp[0] + lamp[1]] = diag1[lamp[0] + lamp[1]]! - 1 64 diag2[lamp[0] - lamp[1]] = diag2[lamp[0] - lamp[1]]! - 1 65 } 66 67 } 68 69 return results 70 } 71 }
1664ms
1 class Solution { 2 func gridIllumination(_ N: Int, _ lamps: [[Int]], _ queries: [[Int]]) -> [Int] { 3 var rowMap = [Int: Int](), colMap = [Int: Int]() 4 var diag1Map = [Int: Int](), diag2Map = [Int: Int]() 5 var lamps = Set(lamps) 6 7 for lamp in lamps { 8 let i = lamp[0], j = lamp[1] 9 rowMap[i, default: 0] += 1 10 colMap[j, default: 0] += 1 11 diag1Map[i - j, default: 0] += 1 // path:\ 12 diag2Map[i + j, default: 0] += 1 // path:/ 13 } 14 15 var answers = [Int]() 16 for query in queries { 17 // get answer 18 let i = query[0], j = query[1] 19 if rowMap[i, default: 0] > 0 || colMap[j, default: 0] > 0 || diag1Map[i - j, default: 0] > 0 || diag2Map[i + j, default: 0] > 0 { 20 answers.append(1) 21 } else { 22 answers.append(0) 23 } 24 25 // remove lamps 26 for m in i-1...i+1 where m >= 0 && m < N { 27 for n in j-1...j+1 where n >= 0 && n < N { 28 guard lamps.contains([m, n]) else { continue } 29 lamps.remove([m, n]) 30 rowMap[m, default: 0] -= 1 31 colMap[n, default: 0] -= 1 32 diag1Map[m - n, default: 0] -= 1 // path:\ 33 diag2Map[m + n, default: 0] -= 1 // path:/ 34 } 35 } 36 } 37 return answers 38 } 39 }
1684ms
struct Point: Hashable, CustomStringConvertible { var x: Int var y: Int static func == (lhs: Point, rhs: Point) -> Bool { return lhs.x == rhs.x && lhs.y == rhs.y } func hash(into hasher: inout Hasher) { hasher.combine(x) hasher.combine(y) } var description: String { return "{\(x), \(y)}" } } class Solution { func gridIllumination(_ N: Int, _ lamps: [[Int]], _ queries: [[Int]]) -> [Int] { var lightLamps = Set<Point>() var columns = [Int: Int]() var rows = [Int: Int]() var diagonal1s = [Int: Int]() var diagonal2s = [Int: Int]() for lamp in lamps { let row = lamp[0] let column = lamp[1] // print("======\(row) \(column) \(diagonal1Index(row, column, N)) \(diagonal2Index(row, column, N))") increase(&rows, row) increase(&columns, column) increase(&diagonal1s, diagonal1Index(row, column, N)) increase(&diagonal2s, diagonal2Index(row, column, N)) lightLamps.insert(Point(x: column, y: row)) } // print("=====r: \(rows)") // print("=====c: \(columns)") // print("=====d: \(diagonal1s)") // print("=====d: \(diagonal2s)") var answers = [Int](repeating: 0, count: queries.count) for (index, query) in queries.enumerated() { let row = query[0] let column = query[1] // print("===========\(lightLamps)") // print("\(row) -> \(rows[row])") // print("\(column) -> \(columns[column])") // print("\(diagonal1Index(row, column, N)) -> \(diagonal1s[diagonal1Index(row, column, N)])") // print("\(diagonal2Index(row, column, N)) -> \(diagonal2s[diagonal2Index(row, column, N)])") if rows[row] ?? 0 > 0 || columns[column] ?? 0 > 0 || diagonal1s[diagonal1Index(row, column, N)] ?? 0 > 0 || diagonal2s[diagonal2Index(row, column, N)] ?? 0 > 0 { answers[index] = 1 } let points = [ Point(x: column, y: row), Point(x: column, y: row - 1), Point(x: column, y: row + 1), Point(x: column + 1, y: row), Point(x: column + 1, y: row - 1), Point(x: column + 1, y: row + 1), Point(x: column - 1, y: row), Point(x: column - 1, y: row - 1), Point(x: column - 1, y: row + 1) ] for point in points { let row = point.y let column = point.x guard row < N, row >= 0, column < N, column >= 0 else { continue } // print("-----\(point)") guard lightLamps.contains(point) else { continue } // print("-----remove") decrease(&rows, row) decrease(&columns, column) decrease(&diagonal1s, diagonal1Index(row, column, N)) decrease(&diagonal2s, diagonal2Index(row, column, N)) lightLamps.remove(point) } } return answers } func diagonal1Index(_ row: Int, _ column: Int, _ N: Int) -> Int { let diff = column - row return diff >= 0 ? diff : (-diff + N - 1) } func diagonal2Index(_ row: Int, _ column: Int, _ N: Int) -> Int { return column + row } func increase(_ dict: inout [Int: Int], _ key: Int) { let val = dict[key] ?? 0 if dict[key] == nil { dict[key] = val } dict[key] = val + 1 } func decrease(_ dict: inout [Int: Int], _ key: Int) { let val = dict[key] ?? 0 if dict[key] == nil { return } dict[key] = val - 1 if val - 1 == 0 { dict[key] = nil } } }
1780ms
1 class Solution { 2 func gridIllumination(_ N: Int, _ lamps: [[Int]], _ queries: [[Int]]) -> [Int] { 3 var rows: [Int: Set<Int>] = [:], columns: [Int: Set<Int>] = [:], diagPlus: [Int: Set<Int>] = [:], diagMinus: [Int: Set<Int>] = [:] 4 5 for (id, lamp) in lamps.enumerated() { 6 let row = lamp[0], column = lamp[1] 7 8 rows[row, default: []].insert(id) 9 columns[column, default: []].insert(id) 10 diagPlus[row + column, default: []].insert(id) 11 diagMinus[row - column, default: []].insert(id) 12 } 13 14 return queries.map { query in 15 let row = query[0], column = query[1] 16 17 var illuminated = false 18 19 if !(rows[row]?.isEmpty ?? true) { 20 illuminated = true 21 } 22 if !(columns[column]?.isEmpty ?? true) { 23 illuminated = true 24 } 25 if !(diagPlus[row + column]?.isEmpty ?? true) { 26 illuminated = true 27 } 28 if !(diagMinus[row - column]?.isEmpty ?? true) { 29 illuminated = true 30 } 31 32 let rowItems = rows[row, default: []].union(rows[row - 1] ?? []).union(rows[row + 1] ?? []) 33 let columnItems = columns[column, default: []].union(columns[column - 1] ?? []).union(columns[column + 1] ?? []) 34 35 let items = rowItems.intersection(columnItems) 36 37 for lampID in items { 38 let lamp = lamps[lampID], row = lamp[0], column = lamp[1] 39 40 rows[row]?.remove(lampID) 41 columns[column]?.remove(lampID) 42 diagPlus[row + column]?.remove(lampID) 43 diagMinus[row - column]?.remove(lampID) 44 } 45 46 return illuminated ? 1 : 0 47 } 48 } 49 }
Runtime: 1904 ms
Memory Usage: 25.1 MB
1 class Solution { 2 var ver:[Int:Int] = [Int:Int]() 3 var hor:[Int:Int] = [Int:Int]() 4 var d1:[Int:Int] = [Int:Int]() 5 var d2:[Int:Int] = [Int:Int]() 6 var st:Set<[Int]> = Set<[Int]>() 7 func gridIllumination(_ N: Int, _ lamps: [[Int]], _ queries: [[Int]]) -> [Int] { 8 for e in lamps 9 { 10 add([e[0], e[1]]) 11 } 12 var ans:[Int] = [Int]() 13 for e in queries 14 { 15 var x:Int = e[0] 16 var y:Int = e[1] 17 ans.append(query([x,y])) 18 for i in -1...1 19 { 20 for j in -1...1 21 { 22 if st.contains([x+i, y+j]) 23 { 24 close([x+i,y+j]) 25 } 26 } 27 } 28 } 29 return ans 30 } 31 32 func add(_ pr:[Int]) 33 { 34 ver[pr[0],default:0] += 1 35 hor[pr[1],default:0] += 1 36 d1[pr[0] + pr[1],default:0] += 1 37 d2[pr[0] - pr[1],default:0] += 1 38 st.insert(pr) 39 } 40 41 func close(_ pr:[Int]) 42 { 43 ver[pr[0],default:0] -= 1 44 hor[pr[1],default:0] -= 1 45 d1[pr[0]+pr[1],default:0] -= 1 46 d2[pr[0]-pr[1],default:0] -= 1 47 st.remove(pr) 48 } 49 50 func query(_ pr:[Int]) -> Int 51 { 52 return (ver[pr[0],default:0] > 0 || 53 hor[pr[1],default:0] > 0 || 54 d1[pr[0] + pr[1],default:0] > 0 || 55 d2[pr[0] - pr[1],default:0] > 0) ? 1 : 0 56 } 57 }
请发表评论