题目大意
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 次。
解题思路
设计一个数据结构,能完成添加区间 addRange,查询区间 queryRange,移除区间 removeRange 三种操作。查询区间的操作需要更加高效一点。
这一题可以用线段树来解答,但是时间复杂度不高,最优解是用二叉排序树 BST 来解答。先来看线段树。这一题是更新区间内的值,所以需要用到懒惰更新。添加区间可以把区间内的值都赋值为
1。由于题目中未预先确定区间范围,选用树的形式实现线段树比数组实现更加节约空间(当然用数组也可以,区间最大是 1000,点至多有 2000 个)。移除区间的时候就是把区间内的值都赋值标
记为 0。
类似的题目有:第 699 题,第 218 题,第 732 题。第 715 题是区间更新定值(不是增减),第 218 题可以用扫描线,第 732 题和第 699 题类似,也是俄罗斯方块的题目,但是第 732 题的俄罗斯方
块的方块会“断裂”。
代码
// RangeModule define type RangeModule struct {
Root *SegmentTreeNode }
// SegmentTreeNode define type SegmentTreeNode struct {
Start, Endint Trackedbool
Lazyint Left, Right *SegmentTreeNode
}
// Constructor715 define func Constructor715() RangeModule {
return RangeModule{&SegmentTreeNode{0, 1e9, false, 0, nil, nil}} }
// AddRange define func (rm *RangeModule) AddRange(left int, right int) {
update(rm.Root, left, right-1, true)
}
// QueryRange define func (rm *RangeModule) QueryRange(left int, right int) bool {
return query(rm.Root, left, right-1)
}
// RemoveRange define func (rm *RangeModule) RemoveRange(left int, right int) {
update(rm.Root, left, right-1, false)
}
func lazyUpdate(node *SegmentTreeNode) { if node.Lazy != 0 {
node.Tracked = node.Lazy == 2 }
if node.Start != node.End { if node.Left == nil || node.Right == nil {
m := node.Start + (node.End-node.Start)/2 node.Left = &SegmentTreeNode{node.Start, m, node.Tracked, 0, nil, nil}
node.Right = &SegmentTreeNode{m + 1, node.End, node.Tracked, 0, nil, nil}
} else if node.Lazy != 0 {
}
func update(node *SegmentTreeNode, start, end int, track bool) { lazyUpdate(node)
if start > end || node == nil || end < node.Start || node.End < start { return
} if start <= node.Start && node.End <= end {
// segment completely covered by the update range node.Tracked = track
if node.Start != node.End { if track {
node.Left.Lazy = 2 node.Right.Lazy = 2
} else { node.Left.Lazy = 1
node.Right.Lazy = 1 }
} return
} update(node.Left, start, end, track)
update(node.Right, start, end, track)
node.Tracked = node.Left.Tracked && node.Right.Tracked }
func query(node *SegmentTreeNode, start, end int) bool { lazyUpdate(node)
if start > end || node == nil || end < node.Start || node.End < start { return true
} if start <= node.Start && node.End <= end {
// segment completely covered by the update range return node.Tracked
} return query(node.Left, start, end) && query(node.Right, start, end)
}
// 解法二 BST // type RangeModule struct {
//Root *BSTNode // }
// type BSTNode struct { //Interval[]int
//return RangeModule{} // }
// func (this *RangeModule) AddRange(left int, right int) { //interval := []int{left, right - 1}
//this.Root = insert(this.Root, interval)
// }
// func (this *RangeModule) RemoveRange(left int, right int) { //interval := []int{left, right - 1}
//this.Root = delete(this.Root, interval)
// }
// func (this *RangeModule) QueryRange(left int, right int) bool { //return query(this.Root, []int{left, right - 1})
// }
// func (this *RangeModule) insert(root *BSTNode, interval []int) *BSTNode { //if root == nil {
//return &BSTNode{interval, nil, nil} //}
| // | ifroot.Interval[0]<=interval[0]&&interval[1]<=root.Interval[1]{ |
|---|---|
| // | returnroot |
| // | } |
| // | ifinterval[0]<root.Interval[0]{ |
| // | root.Left=insert(root.Left,[]int{interval[0],min(interval[1], |
root.Interval[0]-1)})
//} //if root.Interval[1] < interval[1] {
//root.Right = insert(root.Right, []int{max(interval[0], root.Interval[1]+1), interval[1]})
//} //return root
// }
// func (this *RangeModule) delete(root *BSTNode, interval []int) *BSTNode { //if root == nil {
//return nil //}
//if interval[0] < root.Interval[0] { //root.Left = delete(root.Left, []int{interval[0], min(interval[1],
root.Interval[0]-1)})
//} //if root.Interval[1] < interval[1] {
//root.Right = delete(root.Right, []int{max(interval[0],
//}
| // | ifinterval[0]<=root.Interval[0]&&root.Interval[1]<=interval[1]{ |
|---|---|
| // | ifroot.Left==nil{ |
| // | returnroot.Right |
| // | }elseifroot.Right==nil{ |
| // | returnroot.Left |
| // | }else{ |
| // | pred:=root.Left |
| // | forpred.Right!=nil{ |
| // | pred=pred.Right |
| // | } |
| // | root.Interval=pred.Interval |
| // | root.Left=delete(root.Left,pred.Interval) |
| // | returnroot |
| // | } |
| // | } |
| // | ifroot.Interval[0]<interval[0]&&interval[1]<root.Interval[1]{ |
| // | left:=&BSTNode{[]int{root.Interval[0],interval[0]-1},root.Left, |
nil} //right := &BSTNode{[]int{interval[1] + 1, root.Interval[1]}, nil,
root.Right} //left.Right = right
//return left //}
//if interval[0] <= root.Interval[0] { //root.Interval[0] = interval[1] + 1
//} //if root.Interval[1] <= interval[1] {
//root.Interval[1] = interval[0] - 1 //}
//return root // }
// func (this *RangeModule) query(root *BSTNode, interval []int) bool { //if root == nil {
//return false //}
//if interval[1] < root.Interval[0] { //return query(root.Left, interval)
//} //if root.Interval[1] < interval[0] {
//return query(root.Right, interval)
//} //left := true
//if interval[0] < root.Interval[0] {
全站分卷索引 · 462 卷
- 1532. K-diff Pairs in an Array
- 2题目大意
- 3537. Complex Number Multiplication
- 4541. Reverse String II
- 5解题思路
- 6题目大意
- 7代码
- 8547. Friend Circles
- 9解题思路
- 10557. Reverse Words in a String III
- 11代码
- 12题目大意
- 13题目
- 14566. Reshape the Matrix
- 15题目大意
- 16代码
- 17题目大意
- 18572. Subtree of Another Tree
- 19题目大意
- 20575. Distribute Candies
- 21题目大意
- 22解题思路
- 23题目大意
- 24代码
- 25题目大意
- 26628. Maximum Product of Three Numbers
- 27632. Smallest Range Covering Elements from K Lists
- 28代码
- 29633. Sum of Square Numbers
- 30解题思路
- 31题目大意
- 32代码
- 33637. Average of Levels in Binary Tree
- 34638. Shopping Offers
- 35题目大意
- 36解题思路
- 37645. Set Mismatch
- 38题目大意
- 39648. Replace Words
- 40653. Two Sum IV - Input is a BST
- 41题目大意
- 42题目大意
- 43代码
- 44题目大意
- 45662. Maximum Width of Binary Tree
- 46题目大意
- 47代码
- 48668. Kth Smallest Number in Multiplication Table
- 49题目大意
- 50676. Implement Magic Dictionary
- 51题目大意
- 52682. Baseball Game
- 53题目大意
- 54684. Redundant Connection
- 55题目大意
- 56解题思路
- 57题目大意
- 58代码
- 59693. Binary Number with Alternating Bits
- 60题目大意
- 61695. Max Area of Island
- 62题目大意
- 63697. Degree of an Array
- 64代码
- 65题目大意
- 66解题思路
- 67代码
- 68704. Binary Search
- 69代码
- 70题目大意
- 71706. Design HashMap
- 72题目大意
- 73707. Design Linked List
- 74题目大意
- 75710. Random Pick with Blacklist
- 76题目大意
- 77代码
- 78713. Subarray Product Less Than K
- 79代码
- 80题目大意
- 81715. Range Module
- 82题目大意
- 83717. 1-bit and 2-bit Characters
- 84题目大意
- 85题目大意
- 86719. Find K-th Smallest Pair Distance
- 87题目大意
- 88720. Longest Word in Dictionary
- 89题目大意
- 90721. Accounts Merge
- 91题目大意
- 92代码
- 93725. Split Linked List in Parts
- 94题目大意
- 95726. Number of Atoms
- 96题目大意
- 97解题思路
- 98729. My Calendar I
- 99题目大意
- 100解题思路
- 101732. My Calendar III
- 102题目大意
- 103解题思路
- 104733. Flood Fill
- 105解题思路
- 106题目
- 107题目大意
- 108739. Daily Temperatures
- 109744. Find Smallest Letter Greater Than Target
- 110题目大意
- 111745. Prefix and Suffix Search
- 112解题思路
- 113746. Min Cost Climbing Stairs
- 114题目大意
- 115748. Shortest Completing Word
- 116题目大意
- 117753. Cracking the Safe
- 118题目大意
- 119756. Pyramid Transition Matrix
- 120题目大意
- 121代码
- 122题目大意
- 123763. Partition Labels
- 124解题思路
- 125765. Couples Holding Hands
- 126题目大意
- 127代码
- 128题目大意
- 129767. Reorganize String
- 130代码
- 131771. Jewels and Stones
- 132代码
- 133题目大意
- 134代码
- 135781. Rabbits in Forest
- 136题目大意
- 137784. Letter Case Permutation
- 138786. K-th Smallest Prime Fraction
- 139题目大意
- 140793. Preimage Size of Factorial Zeroes Function
- 141解题思路
- 142代码
- 143802. Find Eventual Safe States
- 144解题思路
- 145题目大意
- 146解题思路
- 147811. Subdomain Visit Count
- 148题目
- 149解题思路
- 150812. Largest Triangle Area
- 151题目大意
- 152815. Bus Routes
- 153代码
- 154817. Linked List Components
- 155解题思路
- 156819. Most Common Word
- 157题目大意
- 158826. Most Profit Assigning Work
- 159代码
- 160828. Unique Letter String
- 161代码
- 162832. Flipping an Image
- 163题目大意
- 164题目大意
- 165836. Rectangle Overlap
- 166解题思路
- 167题目大意
- 168839. Similar String Groups
- 169题目大意
- 170841. Keys and Rooms
- 171题目大意
- 172842. Split Array into Fibonacci Sequence
- 173题目大意
- 174844. Backspace String Compare
- 175题目大意
- 176845. Longest Mountain in Array
- 177题目大意
- 178850. Rectangle Area II
- 179题目大意
- 180代码
- 181851. Loud and Rich
- 182题目大意
- 183解题思路
- 184852. Peak Index in a Mountain Array
- 185解题思路
- 186853. Car Fleet
- 187题目大意
- 188856. Score of Parentheses
- 189题目大意
- 190862. Shortest Subarray with Sum at Least K
- 191题目大意
- 192863. All Nodes Distance K in Binary Tree
- 193题目大意
- 194代码
- 195864. Shortest Path to Get All Keys
- 196解题思路
- 197867. Transpose Matrix
- 198872. Leaf-Similar Trees
- 199题目大意
- 200代码
- 201题目大意
- 202876. Middle of the Linked List
- 203题目大意
- 204878. Nth Magical Number
- 205题目大意
- 206880. Decoded String at Index
- 207题目大意
- 208881. Boats to Save People
- 209解题思路
- 210题目大意
- 211885. Spiral Matrix III
- 212题目大意
- 213887. Super Egg Drop
- 214题目大意
- 215代码
- 216题目
- 217解题思路
- 218891. Sum of Subsequence Widths
- 219代码
- 220题目大意
- 221895. Maximum Frequency Stack
- 222题目大意
- 223解题思路
- 224896. Monotonic Array
- 225题目大意
- 226897. Increasing Order Search Tree
- 227解题思路
- 228898. Bitwise ORs of Subarrays
- 229题目大意
- 230代码
- 231901. Online Stock Span
- 232题目大意
- 233904. Fruit Into Baskets
- 234题目大意
- 235907. Sum of Subarray Minimums
- 236代码
- 237911. Online Election
- 238解题思路
- 239914. X of a Kind in a Deck of Cards
- 240题目大意
- 241918. Maximum Sum Circular Subarray
- 242题目大意
- 243代码
- 244题目大意
- 245代码
- 246921. Minimum Add to Make Parentheses Valid
- 247题目大意
- 248题目大意
- 249题目
- 250924. Minimize Malware Spread
- 251题目大意
- 252解题思路
- 253925. Long Pressed Name
- 254题目大意
- 255927. Three Equal Parts
- 256题目大意
- 257928. Minimize Malware Spread II
- 258题目大意
- 259解题思路
- 260930. Binary Subarrays With Sum
- 261代码
- 262题目大意
- 263942. DI String Match
- 264代码
- 265题目大意
- 266题目
- 267代码
- 268题目大意
- 269952. Largest Component Size by Common Factor
- 270题目大意
- 271代码
- 272953. Verifying an Alien Dictionary
- 273题目大意
- 274959. Regions Cut By Slashes
- 275题目大意
- 276代码
- 277961. N-Repeated Element in Size 2N Array
- 278代码
- 279题目大意
- 280代码
- 281969. Pancake Sorting
- 282题目大意
- 283970. Powerful Integers
- 284题目大意
- 285973. K Closest Points to Origin
- 286题目大意
- 287976. Largest Perimeter Triangle
- 288题目大意
- 289题目大意
- 290978. Longest Turbulent Subarray
- 291题目大意
- 292979. Distribute Coins in Binary Tree
- 293题目大意
- 294代码
- 295980. Unique Paths III
- 296题目大意
- 297981. Time Based Key-Value Store
- 298题目大意
- 299解题思路
- 300984. String Without AAA or BBB
- 301题目大意
- 302985. Sum of Even Numbers After Queries
- 303题目大意
- 304986. Interval List Intersections
- 305代码
- 306题目大意
- 307解题思路
- 308题目
- 309代码
- 310993. Cousins in Binary Tree
- 311题目大意
- 312解题思路
- 313995. Minimum Number of K Consecutive Bit Flips
- 314题目大意
- 315代码
- 316996. Number of Squareful Arrays
- 317代码
- 318999. Available Captures for Rook
- 319题目大意
- 320解题思路
- 3211002. Find Common Characters
- 3221003. Check If Word Is Valid After Substitutions
- 323题目大意
- 324解题思路
- 3251004. Max Consecutive Ones III
- 3261005. Maximize Sum Of Array After K Negations
- 327题目大意
- 3281011. Capacity To Ship Packages Within D Days
- 329题目大意
- 3301017. Convert to Base -2
- 331解题思路
- 332题目大意
- 3331020. Number of Enclaves
- 334题目大意
- 3351021. Remove Outermost Parentheses
- 336题目大意
- 337代码
- 3381025. Divisor Game
- 339代码
- 340题目大意
- 341解题思路
- 342题目大意
- 343解题思路
- 3441030. Matrix Cells in Distance Order
- 345题目大意
- 346代码
- 347题目大意
- 348题目大意
- 349代码
- 3501047. Remove All Adjacent Duplicates In String
- 351题目大意
- 3521049. Last Stone Weight II
- 353代码
- 354题目大意
- 3551052. Grumpy Bookstore Owner
- 356解题思路
- 3571054. Distant Barcodes
- 358题目大意
- 3591073. Adding Two Negabinary Numbers
- 360题目大意
- 361代码
- 3621074. Number of Submatrices That Sum to Target
- 363解题思路
- 3641078. Occurrences After Bigram
- 365解题思路
- 366题目大意
- 3671089. Duplicate Zeros
- 3681093. Statistics from a Large Sample
- 369题目大意
- 3701105. Filling Bookcase Shelves
- 371题目大意
- 3721108. Defanging an IP Address
- 373代码
- 374题目大意
- 3751111. Maximum Nesting Depth of Two Valid Parentheses Strings
- 376题目大意
- 377代码
- 3781122. Relative Sort Array
- 379解题思路
- 3801123. Lowest Common Ancestor of Deepest Leaves
- 381题目大意
- 3821128. Number of Equivalent Domino Pairs
- 383解题思路
- 384题目大意
- 3851145. Binary Tree Coloring Game
- 386题目大意
- 387解题思路
- 3881154. Day of the Year
- 389题目大意
- 390题目
- 391解题思路
- 392代码
- 3931160. Find Words That Can Be Formed by Characters
- 394解题思路
- 395题目大意
- 396代码
- 397题目大意
- 3981175. Prime Arrangements
- 399题目大意
- 4001184. Distance Between Bus Stops
- 401题目大意
- 402解题思路
- 403题目大意
- 404题目
- 405代码
- 406题目大意
- 4071201. Ugly Number III
- 408解题思路
- 409题目大意
- 410解题思路
- 4111207. Unique Number of Occurrences
- 4121208. Get Equal Substrings Within Budget
- 413题目大意
- 4141217. Play with Chips
- 415题目大意
- 416题目
- 417代码
- 418题目大意
- 419解题思路
- 420题目大意
- 421代码
- 422题目大意
- 4231252. Cells with Odd Values in a Matrix
- 424题目大意
- 425解题思路
- 4261254. Number of Closed Islands
- 427题目大意
- 4281260. Shift 2D Grid
- 429题目大意
- 430代码
- 431题目大意
- 432题目大意
- 433代码
- 4341281. Subtract the Product and Sum of Digits of an Integer
- 4351283. Find the Smallest Divisor Given a Threshold
- 436题目大意
- 4371287. Element Appearing More Than 25% In Sorted Array
- 4381290. Convert Binary Number in a Linked List to Integer
- 439题目大意
- 440题目大意
- 4411299. Replace Elements with Greatest Element on Right Side
- 4421300. Sum of Mutated Array Closest to Target
- 443解题思路
- 4441302. Deepest Leaves Sum
- 4451304. Find N Unique Integers Sum up to Zero
- 446解题思路
- 447题目大意
- 448解题思路
- 449题目大意
- 4501313. Decompress Run-Length Encoded List
- 451解题思路
- 452题目大意
- 4531380. Lucky Numbers in a Matrix
- 454题目大意
- 4551385. Find the Distance Value Between Two Arrays
- 456题目大意
- 4571389. Create Target Array in the Given Order
- 458题目大意
- 459题目大意
- 460题目大意
- 4611470. Shuffle the Array
- 462解题思路