Skip to content

Commit 048c42d

Browse files
halfrosthalfrost
committed
Add solution 0284、0703
1 parent 3c1ad91 commit 048c42d

31 files changed

+686
-196
lines changed

‎README.md

Lines changed: 142 additions & 141 deletions
Large diffs are not rendered by default.

‎leetcode/0173.Binary-Search-Tree-Iterator/173. Binary Search Tree Iterator.go

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,8 @@
11
package leetcode
22

3-
import "container/heap"
4-
53
import (
4+
"container/heap"
5+
66
"github.com/halfrost/LeetCode-Go/structures"
77
)
88

‎leetcode/0284.Peeking-Iterator/284. Peeking Iterator.go

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
package leetcode
2+
3+
//Below is the interface for Iterator, which is already defined for you.
4+
5+
type Iterator struct {
6+
}
7+
8+
func (this *Iterator) hasNext() bool {
9+
// Returns true if the iteration has more elements.
10+
return true
11+
}
12+
13+
func (this *Iterator) next() int {
14+
// Returns the next element in the iteration.
15+
return 0
16+
}
17+
18+
type PeekingIterator struct {
19+
nextEl int
20+
hasEl bool
21+
iter *Iterator
22+
}
23+
24+
func Constructor(iter *Iterator) *PeekingIterator {
25+
return &PeekingIterator{
26+
iter: iter,
27+
}
28+
}
29+
30+
func (this *PeekingIterator) hasNext() bool {
31+
if this.hasEl {
32+
return true
33+
}
34+
return this.iter.hasNext()
35+
}
36+
37+
func (this *PeekingIterator) next() int {
38+
if this.hasEl {
39+
this.hasEl = false
40+
return this.nextEl
41+
} else {
42+
return this.iter.next()
43+
}
44+
}
45+
46+
func (this *PeekingIterator) peek() int {
47+
if this.hasEl {
48+
return this.nextEl
49+
}
50+
this.hasEl = true
51+
this.nextEl = this.iter.next()
52+
return this.nextEl
53+
}

‎leetcode/0284.Peeking-Iterator/284. Peeking Iterator_test.go

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
package leetcode
2+
3+
import (
4+
"testing"
5+
)
6+
7+
func Test_Problem284(t *testing.T) {
8+
9+
}

‎leetcode/0284.Peeking-Iterator/README.md

Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
1+
# [284. Peeking Iterator](https://leetcode.com/problems/peeking-iterator/)
2+
3+
## 题目
4+
5+
Given an Iterator class interface with methods: `next()` and `hasNext()`, design and implement a PeekingIterator that support the `peek()` operation -- it essentially peek() at the element that will be returned by the next call to next().
6+
7+
**Example:**
8+
9+
```
10+
Assume that the iterator is initialized to the beginning of the list: [1,2,3].
11+
12+
Call next() gets you 1, the first element in the list.
13+
Now you call peek() and it returns 2, the next element. Calling next() after that still return 2.
14+
You call next() the final time and it returns 3, the last element.
15+
Calling hasNext() after that should return false.
16+
```
17+
18+
**Follow up**: How would you extend your design to be generic and work with all types, not just integer?
19+
20+
## 题目大意
21+
22+
给定一个迭代器类的接口，接口包含两个方法： next() 和 hasNext()。设计并实现一个支持 peek() 操作的顶端迭代器 -- 其本质就是把原本应由 next() 方法返回的元素 peek() 出来。
23+
24+
> peek() 是偷看的意思。偷偷看一看下一个元素是什么，但是并不是 next() 访问。
25+
26+
## 解题思路
27+
28+
- 简单题。在 PeekingIterator 内部保存 2 个变量，一个是下一个元素值，另一个是是否有下一个元素。在 next() 操作和 hasNext() 操作时，访问保存的这 2 个变量。peek() 操作也比较简单，判断是否有下一个元素，如果有，即返回该元素值。这里实现了迭代指针不移动的功能。如果没有保存下一个元素值，即没有 peek() 偷看，next() 操作继续往后移动指针，读取后一位元素。
29+
- 这里复用了是否有下一个元素值，来判断 hasNext() 和 peek() 操作中不移动指针的逻辑。
30+
31+
## 代码
32+
33+
```go
34+
package leetcode
35+
36+
//Below is the interface for Iterator, which is already defined for you.
37+
38+
type Iterator struct {
39+
}
40+
41+
func (this *Iterator) hasNext() bool {
42+
// Returns true if the iteration has more elements.
43+
return true
44+
}
45+
46+
func (this *Iterator) next() int {
47+
// Returns the next element in the iteration.
48+
return 0
49+
}
50+
51+
type PeekingIterator struct {
52+
nextEl int
53+
hasEl bool
54+
iter *Iterator
55+
}
56+
57+
func Constructor(iter *Iterator) *PeekingIterator {
58+
return &PeekingIterator{
59+
iter: iter,
60+
}
61+
}
62+
63+
func (this *PeekingIterator) hasNext() bool {
64+
if this.hasEl {
65+
return true
66+
}
67+
return this.iter.hasNext()
68+
}
69+
70+
func (this *PeekingIterator) next() int {
71+
if this.hasEl {
72+
this.hasEl = false
73+
return this.nextEl
74+
} else {
75+
return this.iter.next()
76+
}
77+
}
78+
79+
func (this *PeekingIterator) peek() int {
80+
if this.hasEl {
81+
return this.nextEl
82+
}
83+
this.hasEl = true
84+
this.nextEl = this.iter.next()
85+
return this.nextEl
86+
}
87+
```

‎leetcode/0703.Kth-Largest-Element-in-a-Stream/703. Kth Largest Element in a Stream.go

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
package leetcode
2+
3+
import (
4+
"container/heap"
5+
"sort"
6+
)
7+
8+
type KthLargest struct {
9+
sort.IntSlice
10+
k int
11+
}
12+
13+
func Constructor(k int, nums []int) KthLargest {
14+
kl := KthLargest{k: k}
15+
for _, val := range nums {
16+
kl.Add(val)
17+
}
18+
return kl
19+
}
20+
21+
func (kl *KthLargest) Push(v interface{}) {
22+
kl.IntSlice = append(kl.IntSlice, v.(int))
23+
}
24+
25+
func (kl *KthLargest) Pop() interface{} {
26+
a := kl.IntSlice
27+
v := a[len(a)-1]
28+
kl.IntSlice = a[:len(a)-1]
29+
return v
30+
}
31+
32+
func (kl *KthLargest) Add(val int) int {
33+
heap.Push(kl, val)
34+
if kl.Len() > kl.k {
35+
heap.Pop(kl)
36+
}
37+
return kl.IntSlice[0]
38+
}

‎leetcode/0703.Kth-Largest-Element-in-a-Stream/703. Kth Largest Element in a Stream_test.go

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
package leetcode
2+
3+
import (
4+
"fmt"
5+
"testing"
6+
)
7+
8+
func Test_Problem703(t *testing.T) {
9+
obj := Constructor(3, []int{4, 5, 8, 2})
10+
fmt.Printf("Add 7 = %v\n", obj.Add(3))
11+
fmt.Printf("Add 7 = %v\n", obj.Add(5))
12+
fmt.Printf("Add 7 = %v\n", obj.Add(10))
13+
fmt.Printf("Add 7 = %v\n", obj.Add(9))
14+
fmt.Printf("Add 7 = %v\n", obj.Add(4))
15+
}

‎leetcode/0703.Kth-Largest-Element-in-a-Stream/README.md

Lines changed: 93 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,93 @@
1+
# [703. Kth Largest Element in a Stream](https://leetcode.com/problems/kth-largest-element-in-a-stream/)
2+
3+
## 题目
4+
5+
Design a class to find the `kth` largest element in a stream. Note that it is the `kth` largest element in the sorted order, not the `kth` distinct element.
6+
7+
Implement `KthLargest` class:
8+
9+
- `KthLargest(int k, int[] nums)` Initializes the object with the integer `k` and the stream of integers `nums`.
10+
- `int add(int val)` Returns the element representing the `kth` largest element in the stream.
11+
12+
**Example 1:**
13+
14+
```
15+
Input
16+
["KthLargest", "add", "add", "add", "add", "add"]
17+
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
18+
Output
19+
[null, 4, 5, 5, 8, 8]
20+
21+
Explanation
22+
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
23+
kthLargest.add(3); // return 4
24+
kthLargest.add(5); // return 5
25+
kthLargest.add(10); // return 5
26+
kthLargest.add(9); // return 8
27+
kthLargest.add(4); // return 8
28+
29+
```
30+
31+
**Constraints:**
32+
33+
- `1 <= k <= 104`
34+
- `0 <= nums.length <= 104`
35+
- `104 <= nums[i] <= 104`
36+
- `104 <= val <= 104`
37+
- At most `104` calls will be made to `add`.
38+
- It is guaranteed that there will be at least `k` elements in the array when you search for the `kth` element.
39+
40+
## 题目大意
41+
42+
设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。请实现 KthLargest 类：
43+
44+
- KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
45+
- int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。
46+
47+
## 解题思路
48+
49+
- 读完题就能明白这一题考察的是最小堆。构建一个长度为 K 的最小堆，每次 pop 堆首(堆中最小的元素)，维护堆首即为第 K 大元素。
50+
- 这里有一个简洁的写法，常规的构建一个 pq 优先队列需要自己新建一个类型，然后实现 Len()、Less()、Swap()、Push()、Pop() 这 5 个方法。在 sort 包里有一个现成的最小堆，sort.IntSlice。可以借用它，再自己实现 Push()、Pop()就可以使用最小堆了，节约一部分代码。
51+
52+
## 代码
53+
54+
```go
55+
package leetcode
56+
57+
import (
58+
"container/heap"
59+
"sort"
60+
)
61+
62+
type KthLargest struct {
63+
sort.IntSlice
64+
k int
65+
}
66+
67+
func Constructor(k int, nums []int) KthLargest {
68+
kl := KthLargest{k: k}
69+
for _, val := range nums {
70+
kl.Add(val)
71+
}
72+
return kl
73+
}
74+
75+
func (kl *KthLargest) Push(v interface{}) {
76+
kl.IntSlice = append(kl.IntSlice, v.(int))
77+
}
78+
79+
func (kl *KthLargest) Pop() interface{} {
80+
a := kl.IntSlice
81+
v := a[len(a)-1]
82+
kl.IntSlice = a[:len(a)-1]
83+
return v
84+
}
85+
86+
func (kl *KthLargest) Add(val int) int {
87+
heap.Push(kl, val)
88+
if kl.Len() > kl.k {
89+
heap.Pop(kl)
90+
}
91+
return kl.IntSlice[0]
92+
}
93+
```

‎website/content/ChapterFour/0200~0299/0283.Move-Zeroes.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -58,5 +58,5 @@ func moveZeroes(nums []int) {
5858
----------------------------------------------
5959
<div style="display: flex;justify-content: space-between;align-items: center;">
6060
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0200~0299/0275.H-Index-II/">⬅️上一页</a></p>
61-
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0200~0299/0287.Find-the-Duplicate-Number/">下一页➡️</a></p>
61+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0200~0299/0284.Peeking-Iterator/">下一页➡️</a></p>
6262
</div>

0 commit comments

Comments
 (0)