2023-12-08

45. 跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

提示:

1 <= nums.length <= 104
0 <= nums[i] <= 1000
题目保证可以到达 nums[n-1]

1// 贪心
2func jump(nums []int) int {
3	n := len(nums)
4	if n == 1 {
5		return 0
6	}
7
8	steps := 0          // 记录跳跃的步数
9	maxPosition := 0    // 记录当前步数下能够到达的最远位置
10	end := 0            // 记录当前步数的结束位置
11
12	// 遍历数组
13	for i := 0; i < n-1; i++ {
14		maxPosition = max(maxPosition, i+nums[i])
15
16		// 到达当前步数的最远位置，更新步数并更新结束位置
17		if i == end {
18			end = maxPosition
19			steps++
20		}
21
22        // 如果当前结束位置已经能够达到数组末尾，则直接返回步数
23        if end >= n-1 {
24            return steps
25        }
26	}
27
28	return steps
29}
30
31// 动态规划，O(n^2)
32func jump(nums []int) int {
33    n:=len(nums)
34    if n<=1{
35        return 0
36    }
37
38    dp := make([]int, n)
39    for i := range dp {
40        dp[i] = math.MaxInt32 // 设置为一个大的数，表示无穷大
41    }
42    dp[0] = 0 // 初始位置的跳跃次数为 0
43
44    // 动态规划更新 dp 数组，检查到达每个位置需要的最少步数
45    for i := 0; i < n; i++ {
46        for j := 1; j <= nums[i] && i+j < n; j++ {
47            dp[i+j] = min(dp[i+j], dp[i]+1)
48        }
49    }
50  
51    return dp[n-1]
52}

　　‍

274. H 指数

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。

根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数是指他（她）至少发表了 h 篇论文，并且每篇论文至少被引用 h 次。如果 h 有多种可能的值，h 指数是其中最大的那个。

示例 1：

输入：citations = [3,0,6,1,5]
输出：3
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
由于研究者有 3 篇论文每篇至少被引用了 3 次，其余两篇论文每篇被引用不多于 3 次，所以她的 h 指数是 3。
示例 2：

输入：citations = [1,3,1]
输出：1

提示：

n == citations.length
1 <= n <= 5000
0 <= citations[i] <= 1000

1func hIndex(citations []int) int {
2	// 获取数组的长度
3	n := len(citations)
4	// 创建一个长度为 n+1 的数组 counts，用于记录引用次数的统计
5	counts := make([]int, n+1)
6
7	// 遍历论文引用次数数组，统计每个引用次数对应的论文数量
8	for _, cite := range citations {
9		// 如果引用次数大于等于总论文数 n，将 counts[n] 增加 1
10		if cite >= n {
11			counts[n]++
12		} else {
13			// 否则，将 counts[cite] 增加 1
14			counts[cite]++
15		}
16	}
17
18	// 从总论文数 n 开始向下遍历 counts 数组，累加论文数量
19	// 如果累加的论文数量大于等于当前引用次数 i，则返回 i
20	for i, total := n, 0; i >= 0; i-- {
21		total += counts[i]
22		if total >= i {
23			return i
24		}
25	}
26
27	// 如果遍历结束仍未找到合适的 h 指数，则返回 0
28	return 0
29}

　　‍

380. O(1) 时间插入、删除和获取随机元素

实现RandomizedSet 类：

RandomizedSet() 初始化 RandomizedSet 对象
bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有相同的概率被返回。
你必须实现类的所有函数，并满足每个函数的平均时间复杂度为 O(1) 。

示例：

输入
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
输出
[null, true, false, true, 2, true, false, 2]

解释
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomizedSet.remove(2); // 返回 false ，表示集合中不存在 2 。
randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。
randomizedSet.remove(1); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomizedSet.insert(2); // 2 已在集合中，所以返回 false 。
randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。

提示：

-231 <= val <= 231 - 1
最多调用 insert、remove 和 getRandom 函数 2 * 105 次
在调用 getRandom 方法时，数据结构中至少存在一个元素。

1// RandomizedSet 结构体定义了数据结构的属性，包括一个切片 nums 用于存储元素，和一个映射 indices 用于存储元素值到在 nums 中的索引的映射。
2type RandomizedSet struct {
3    nums    []int         // 用于存储元素的切片
4    indices map[int]int   // 用于存储元素值到在 nums 中的索引的映射
5}
6
7// Constructor 构造函数，初始化 RandomizedSet 对象。
8func Constructor() RandomizedSet {
9    // 返回一个新的 RandomizedSet 对象，其中 nums 为空切片，indices 为一个空的映射。
10    return RandomizedSet{make([]int, 0), make(map[int]int)}
11}
12
13// Insert 方法用于向集合中插入元素。
14func (this *RandomizedSet) Insert(val int) bool {
15    // 检查元素是否已经存在于集合中，如果存在则返回 false。
16    if _, exist := this.indices[val]; exist {
17        return false
18    }
19    // 将元素添加到 nums 切片末尾，并更新 indices 映射。
20    this.indices[val] = len(this.nums)
21    this.nums = append(this.nums, val)
22    return true
23}
24
25// Remove 方法用于从集合中移除元素。
26func (this *RandomizedSet) Remove(val int) bool {
27    // 检查元素是否存在于集合中，如果不存在则返回 false。
28    idx, exist := this.indices[val]
29    if !exist {
30        return false
31    }
32    // 将要移除的元素与最后一个元素交换位置，然后更新 indices 映射和 nums 切片。
33    lastIdx := len(this.nums) - 1
34    this.nums[idx] = this.nums[lastIdx]
35    this.indices[this.nums[idx]] = idx
36    this.nums = this.nums[:lastIdx]
37    // 删除 indices 中对应的映射。
38    delete(this.indices, val)
39    return true
40}
41
42// GetRandom 方法用于随机获取集合中的一个元素。
43func (this *RandomizedSet) GetRandom() int {
44    // 通过 rand.Intn 随机获取 nums 切片中的一个索引，然后返回对应的元素值。
45    return this.nums[rand.Intn(len(this.nums))]
46}
47
48/**
49 * Your RandomizedSet object will be instantiated and called as such:
50 * obj := Constructor();
51 * param_1 := obj.Insert(val);
52 * param_2 := obj.Remove(val);
53 * param_3 := obj.GetRandom();
54 */
55