Skip to content

Commit f68bec2

Browse files
tphyhFightingtphyhFighting
committed
add: leetcode 0352 solution
1 parent 0e69148 commit f68bec2

File tree

3 files changed

+220
-0
lines changed

3 files changed

+220
-0
lines changed

‎leetcode/0352.Data-Stream-as-Disjoint-Intervals/352.Data Stream as Disjoint Intervals.go

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
package leetcode
2+
3+
import "sort"
4+
5+
type SummaryRanges struct {
6+
nums []int
7+
mp map[int]int
8+
}
9+
10+
func Constructor() SummaryRanges {
11+
return SummaryRanges{
12+
nums: []int{},
13+
mp: map[int]int{},
14+
}
15+
}
16+
17+
func (this *SummaryRanges) AddNum(val int) {
18+
if _, ok := this.mp[val]; !ok {
19+
this.mp[val] = 1
20+
this.nums = append(this.nums, val)
21+
}
22+
sort.Ints(this.nums)
23+
}
24+
25+
func (this *SummaryRanges) GetIntervals() [][]int {
26+
n := len(this.nums)
27+
var ans [][]int
28+
if n == 0 {
29+
return ans
30+
}
31+
if n == 1 {
32+
ans = append(ans, []int{this.nums[0], this.nums[0]})
33+
return ans
34+
}
35+
start, end := this.nums[0], this.nums[0]
36+
ans = append(ans, []int{start, end})
37+
index := 0
38+
for i := 1; i < n; i++ {
39+
if this.nums[i] == end+1 {
40+
end = this.nums[i]
41+
ans[index][1] = end
42+
} else {
43+
start, end = this.nums[i], this.nums[i]
44+
ans = append(ans, []int{start, end})
45+
index++
46+
}
47+
}
48+
return ans
49+
}

‎leetcode/0352.Data-Stream-as-Disjoint-Intervals/352.Data Stream as Disjoint Intervals_test.go

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
package leetcode
2+
3+
import (
4+
"fmt"
5+
"testing"
6+
)
7+
8+
type question352 struct {
9+
para352
10+
ans352
11+
}
12+
13+
// para 是参数
14+
type para352 struct {
15+
para string
16+
num int
17+
}
18+
19+
// ans 是答案
20+
type ans352 struct {
21+
ans [][]int
22+
}
23+
24+
func Test_Problem352(t *testing.T) {
25+
26+
qs := []question352{
27+
28+
{
29+
para352{"addNum", 1},
30+
ans352{[][]int{{1, 1}}},
31+
},
32+
33+
{
34+
para352{"addNum", 3},
35+
ans352{[][]int{{1, 1}, {3, 3}}},
36+
},
37+
38+
{
39+
para352{"addNum", 7},
40+
ans352{[][]int{{1, 1}, {3, 3}, {7, 7}}},
41+
},
42+
43+
{
44+
para352{"addNum", 2},
45+
ans352{[][]int{{1, 3}, {7, 7}}},
46+
},
47+
48+
{
49+
para352{"addNum", 6},
50+
ans352{[][]int{{1, 3}, {6, 7}}},
51+
},
52+
}
53+
54+
fmt.Printf("------------------------Leetcode Problem 352------------------------\n")
55+
56+
obj := Constructor()
57+
for _, q := range qs {
58+
_, p := q.ans352, q.para352
59+
obj.AddNum(p.num)
60+
fmt.Printf("【input】:%v 【output】:%v\n", p, obj.GetIntervals())
61+
}
62+
fmt.Printf("\n\n\n")
63+
}

‎leetcode/0352.Data-Stream-as-Disjoint-Intervals/README.md

Lines changed: 108 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,108 @@
1+
# [352. Data Stream as Disjoint Intervals](https://leetcode-cn.com/problems/data-stream-as-disjoint-intervals/)
2+
3+
4+
## 题目
5+
6+
Given a data stream input of non-negative integers a1, a2, ..., an, summarize the numbers seen so far as a list of disjoint intervals.
7+
8+
Implement the SummaryRanges class:
9+
10+
- SummaryRanges() Initializes the object with an empty stream.
11+
- void addNum(int val) Adds the integer val to the stream.
12+
- int[][] getIntervals() Returns a summary of the integers in the stream currently as a list of disjoint intervals [starti, endi].
13+
14+
**Example 1:**
15+
16+
Input
17+
["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
18+
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
19+
Output
20+
[null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]]
21+
22+
Explanation
23+
SummaryRanges summaryRanges = new SummaryRanges();
24+
summaryRanges.addNum(1); // arr = [1]
25+
summaryRanges.getIntervals(); // return [[1, 1]]
26+
summaryRanges.addNum(3); // arr = [1, 3]
27+
summaryRanges.getIntervals(); // return [[1, 1], [3, 3]]
28+
summaryRanges.addNum(7); // arr = [1, 3, 7]
29+
summaryRanges.getIntervals(); // return [[1, 1], [3, 3], [7, 7]]
30+
summaryRanges.addNum(2); // arr = [1, 2, 3, 7]
31+
summaryRanges.getIntervals(); // return [[1, 3], [7, 7]]
32+
summaryRanges.addNum(6); // arr = [1, 2, 3, 6, 7]
33+
summaryRanges.getIntervals(); // return [[1, 3], [6, 7]]
34+
35+
**Constraints**
36+
37+
- 0 <= val <= 10000
38+
- At most 3 * 10000 calls will be made to addNum and getIntervals.
39+
40+
## 题目大意
41+
42+
给你一个由非负整数a1, a2, ..., an 组成的数据流输入，请你将到目前为止看到的数字总结为不相交的区间列表。
43+
44+
实现 SummaryRanges 类：
45+
46+
- SummaryRanges() 使用一个空数据流初始化对象。
47+
- void addNum(int val) 向数据流中加入整数 val 。
48+
- int[][] getIntervals() 以不相交区间[starti, endi] 的列表形式返回对数据流中整数的总结
49+
50+
## 解题思路
51+
52+
- 使用字典过滤掉重复的数字
53+
- 把过滤后的数字放到nums中,并进行排序
54+
- 使用nums构建不重复的区间
55+
56+
## 代码
57+
58+
```go
59+
package leetcode
60+
61+
import "sort"
62+
63+
type SummaryRanges struct {
64+
nums []int
65+
mp map[int]int
66+
}
67+
68+
func Constructor() SummaryRanges {
69+
return SummaryRanges{
70+
nums: []int{},
71+
mp : map[int]int{},
72+
}
73+
}
74+
75+
func (this *SummaryRanges) AddNum(val int) {
76+
if _, ok := this.mp[val]; !ok {
77+
this.mp[val] = 1
78+
this.nums = append(this.nums, val)
79+
}
80+
sort.Ints(this.nums)
81+
}
82+
83+
func (this *SummaryRanges) GetIntervals() [][]int {
84+
n := len(this.nums)
85+
var ans [][]int
86+
if n == 0 {
87+
return ans
88+
}
89+
if n == 1 {
90+
ans = append(ans, []int{this.nums[0], this.nums[0]})
91+
return ans
92+
}
93+
start, end := this.nums[0], this.nums[0]
94+
ans = append(ans, []int{start, end})
95+
index := 0
96+
for i := 1; i < n; i++ {
97+
if this.nums[i] == end + 1 {
98+
end = this.nums[i]
99+
ans[index][1] = end
100+
} else {
101+
start, end = this.nums[i], this.nums[i]
102+
ans = append(ans, []int{start, end})
103+
index++
104+
}
105+
}
106+
return ans
107+
}
108+
```

0 commit comments

Comments
 (0)