目录
284. 顶端迭代器 Peeking Iterator 🌟🌟
287. 寻找重复数 Find the Duplicate Number 🌟🌟
284. 顶端迭代器 Peeking Iterator
请你在设计一个迭代器，在集成现有迭代器拥有的 hasNext 和 next 操作的基础上，还额外支持 peek 操作。
实现 PeekingIterator 类：
PeekingIterator(Iterator<int> nums)使用指定整数迭代器nums初始化迭代器。int next()返回数组中的下一个元素，并将指针移动到下个元素处。bool hasNext()如果数组中存在下一个元素，返回true；否则，返回false。int peek()返回数组中的下一个元素，但 不 移动指针。
注意：每种语言可能有不同的构造函数和迭代器 Iterator，但均支持 int next() 和 boolean hasNext() 函数。
示例 ：
输入： ["PeekingIterator", "next", "peek", "next", "next", "hasNext"] [[[1, 2, 3]], [], [], [], [], []] 输出： [null, 1, 2, 2, 3, false] 解释： PeekingIterator peekingIterator = new PeekingIterator([1, 2, 3]); // [1,2,3] peekingIterator.next(); // 返回 1 ，指针移动到下一个元素 [1,2,3] peekingIterator.peek(); // 返回 2 ，指针未发生移动 [1,2,3] peekingIterator.next(); // 返回 2 ，指针移动到下一个元素 [1,2,3] peekingIterator.next(); // 返回 3 ，指针移动到下一个元素 [1,2,3] peekingIterator.hasNext(); // 返回 False
提示：
1 <= nums.length <= 10001 <= nums[i] <= 1000- 对
next和peek的调用均有效 next、hasNext和peek最多调用1000次
进阶：你将如何拓展你的设计？使之变得通用化，从而适应所有的类型，而不只是整数型？
代码：
package main
import "fmt"
type PeekingIterator struct {
iter *Iterator
hasPeek bool // 是否有 Peek 缓存
peekVal int // Peek 缓存值
}
func Constructor(iter *Iterator) *PeekingIterator {
return &PeekingIterator{iter: iter}
}
func (it *PeekingIterator) hasNext() bool {
if it.hasPeek {
return true
}
return it.iter.hasNext()
}
func (it *PeekingIterator) next() int {
if it.hasPeek {
it.hasPeek = false // 清除 Peek 缓存
return it.peekVal
}
return it.iter.next()
}
func (it *PeekingIterator) peek() int {
if it.hasPeek {
return it.peekVal
}
it.peekVal = it.iter.next()
it.hasPeek = true // 更新 Peek 缓存状态
return it.peekVal
}
type Iterator struct {
nums []int
idx int
}
func (it *Iterator) hasNext() bool {
return it.idx < len(it.nums)
}
func (it *Iterator) next() int {
if !it.hasNext() {
panic("out of index")
}
val := it.nums[it.idx]
it.idx++
return val
}
func main() {
nums := []int{1, 2, 3}
iter := &Iterator{nums: nums}
pIter := Constructor(iter)
fmt.Println(pIter.next()) // 1
fmt.Println(pIter.peek()) // 2
fmt.Println(pIter.next()) // 2
fmt.Println(pIter.next()) // 3
fmt.Println(pIter.hasNext()) // false
}
输出：
1
2
2
3
false
287. 寻找重复数 Find the Duplicate Number
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
示例 1：
输入：nums = [1,3,4,2,2] 输出：2
示例 2：
输入：nums = [3,1,3,4,2] 输出：3
提示：
1 <= n <= 10^5nums.length == n + 11 <= nums[i] <= nnums中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次
进阶：
- 如何证明
nums中至少存在一个重复的数字? - 你可以设计一个线性级时间复杂度
O(n)的解决方案吗？
代码1：二分查找
package main
import "fmt"
func findDuplicate(nums []int) int {
n := len(nums)
l, r := 1, n-1
for l < r {
mid := (l + r) >> 1
cnt := 0
for _, num := range nums {
if num <= mid {
cnt++
}
}
if cnt > mid {
r = mid
} else {
l = mid + 1
}
}
return l
}
func main() {
nums1 := []int{1, 3, 4, 2, 2}
fmt.Println(findDuplicate(nums1)) // 2
nums2 := []int{3, 1, 3, 4, 2}
fmt.Println(findDuplicate(nums2)) // 3
}
代码2：双指针
package main
import "fmt"
func findDuplicate(nums []int) int {
slow, fast := nums[0], nums[0]
for {
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast {
break
}
}
slow = nums[0]
for slow != fast {
slow = nums[slow]
fast = nums[fast]
}
return slow
}
func main() {
nums1 := []int{1, 3, 4, 2, 2}
fmt.Println(findDuplicate(nums1)) // 2
nums2 := []int{3, 1, 3, 4, 2}
fmt.Println(findDuplicate(nums2)) // 3
}
代码2：桶排序法
package main
import "fmt"
func findDuplicate(nums []int) int {
n := len(nums)
buckets := make([]int, n)
for _, num := range nums {
if buckets[num-1] > 0 {
return num
}
buckets[num-1]++
}
return -1
}
func main() {
nums1 := []int{1, 3, 4, 2, 2}
fmt.Println(findDuplicate(nums1)) // 2
nums2 := []int{3, 1, 3, 4, 2}
fmt.Println(findDuplicate(nums2)) // 3
}
输出：
2
3
🌟 每日一练刷题专栏 🌟
✨ 持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/