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

[Swift]LeetCode715.Range模块|RangeModule

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

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

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

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

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

A Range Module is a module that tracks ranges of numbers. Your task is to design and implement the following interfaces in an efficient manner.

  • addRange(int left, int right) Adds the half-open interval [left, right), tracking every real number in that interval. Adding an interval that partially overlaps with currently tracked numbers should add any numbers in the interval [left, right) that are not already tracked.
  • queryRange(int left, int right) Returns true if and only if every real number in the interval [left, right) is currently being tracked. 
  • removeRange(int left, int right) Stops tracking every real number currently being tracked in the interval [left, right).

Example 1:

addRange(10, 20): null
removeRange(14, 16): null
queryRange(10, 14): true (Every number in [10, 14) is being tracked)
queryRange(13, 15): false (Numbers like 14, 14.03, 14.17 in [13, 15) are not being tracked)
queryRange(16, 17): true (The number 16 in [16, 17) is still being tracked, despite the remove operation)

Note:

  • A half open interval [left, right) denotes all real numbers left <= x < right.
  • 0 < left < right < 10^9 in all calls to addRange, queryRange, removeRange.
  • The total number of calls to addRange in a single test case is at most 1000.
  • The total number of calls to queryRange in a single test case is at most 5000.
  • The total number of calls to removeRange in a single test case is at most 1000.

Range 模块是跟踪数字范围的模块。你的任务是以一种有效的方式设计和实现以下接口。

  • addRange(int left, int right) 添加半开区间 [left, right),跟踪该区间中的每个实数。添加与当前跟踪的数字部分重叠的区间时,应当添加在区间 [left, right) 中尚未跟踪的任何数字到该区间中。
  • queryRange(int left, int right) 只有在当前正在跟踪区间 [left, right) 中的每一个实数时,才返回 true。
  • removeRange(int left, int right) 停止跟踪区间 [left, right) 中当前正在跟踪的每个实数。

示例:

addRange(10, 20): null
removeRange(14, 16): null
queryRange(10, 14): true (区间 [10, 14) 中的每个数都正在被跟踪)
queryRange(13, 15): false (未跟踪区间 [13, 15) 中像 14, 14.03, 14.17 这样的数字)
queryRange(16, 17): true (尽管执行了删除操作,区间 [16, 17) 中的数字 16 仍然会被跟踪)

提示:

  • 半开区间 [left, right) 表示所有满足 left <= x < right 的实数。
  • 对 addRange, queryRange, removeRange 的所有调用中 0 < left < right < 10^9
  • 在单个测试用例中,对 addRange 的调用总数不超过 1000 次。
  • 在单个测试用例中,对  queryRange 的调用总数不超过 5000次。
  • 在单个测试用例中,对 removeRange 的调用总数不超过 1000 次。

Runtime: 2188 ms
Memory Usage: 20.9 MB
 1 class RangeModule {
 2     var v:[(Int,Int)]
 3 
 4     init() {
 5         v = [(Int,Int)]()
 6     }
 7     
 8     func addRange(_ left: Int, _ right: Int) {
 9         var left = left
10         var right = right
11         var res:[(Int,Int)] = [(Int,Int)]()
12         var n:Int = v.count
13         var cur:Int = 0
14         for i in 0..<n
15         {
16             if v[i].1 < left
17             {
18                 res.append(v[i])
19                 cur += 1
20             }
21             else if v[i].0 > right
22             {
23                 res.append(v[i])            
24             }
25             else
26             {
27                 left = min(left, v[i].0)
28                 right = max(right, v[i].1)
29             }
30         }
31         res.insert((left, right),at:cur)
32         v = res      
33     }
34     
35     func queryRange(_ left: Int, _ right: Int) -> Bool {
36         for a in v
37         {
38             if a.0 <= left && a.1 >= right
39             {
40                 return true
41             }            
42         }   
43         return false
44     }
45     
46     func removeRange(_ left: Int, _ right: Int) {
47         var res:[(Int,Int)] = [(Int,Int)]()
48         var t:[(Int,Int)] = [(Int,Int)]()
49         var n:Int = v.count
50         var cur:Int = 0
51         for i in 0..<n
52         {
53             if v[i].1 <= left
54             {
55                 res.append(v[i])
56                 cur += 1
57             }
58             else if v[i].0 >= right
59             {
60                 res.append(v[i])
61             }
62             else
63             {
64                 if v[i].0 < left
65                 {
66                     t.append((v[i].0, left))
67                 }
68                 if v[i].1 > right
69                 {
70                     t.append((right, v[i].1))
71                 }                
72             }
73         }
74         res += t
75         v = res      
76     }
77 }
78 
79 /**
80  * Your RangeModule object will be instantiated and called as such:
81  * let obj = RangeModule()
82  * obj.addRange(left, right)
83  * let ret_2: Bool = obj.queryRange(left, right)
84  * obj.removeRange(left, right)
85  */ 

 


鲜花

握手

雷人

路过

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

请发表评论

全部评论

专题导读
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

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

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

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