• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode1001. 网格照明 | Grid Illumination

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:https://www.cnblogs.com/strengthen/p/10430537.html 
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

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. 1 <= N <= 10^9
  2. 0 <= lamps.length <= 20000
  3. 0 <= queries.length <= 20000
  4. lamps[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. 1 <= N <= 10^9
  2. 0 <= lamps.length <= 20000
  3. 0 <= queries.length <= 20000
  4. lamps[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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Swift_使用命名空间创建发布时间:2022-07-13
下一篇:
清风注解-Swift程序设计语言:Point11~15 - 清风抚柳发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap