284. 顶端迭代器 Peeking Iterator
请你在设计一个迭代器，在集成现有迭代器拥有的 hasNext 和 next 操作的基础上，还额外支持 peek 操作。
实现 PeekingIterator 类：
PeekingIterator(Iterator 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/
|
Rust每日一练 专栏 （2023.5.16~）更新中... |
|
Golang每日一练 专栏 （2023.3.11~）更新中... |
|
Python每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
C/C++每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
Java每日一练 专栏 （2023.3.11~2023.5.18）暂停更 |
