7.2 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]。
我的思路：
这一题和上一题不同的是要返回最小的跳跃次数，所以我们需要动态维护三个数据：当前范围内能够到达的最远元素，当前跳跃能到达的最远位置，跳跃次数
- currentMax是当前能够到达的最大位置，每一次都要把它和nums[i]+i进行比较，更新最大的位置
- 什么时候才跳跃呢？当i等于当前范围内能够到达的最远元素，动态更新currentMax
- 提高效率：提前判断currentMax和len -1的长度，提前跳出
我的代码：
function jump(nums: number[]): number {
let jumps = 0; // 跳跃次数
let currentMax = 0; // 当前跳跃能到达的最远位置
let farthest = 0; // 记录在当前跳跃范围内能到达的最远位置
let len = nums.length;
// 处理特殊情况
if (len === 1) {
return 0; // 如果数组长度为 1，不需要跳跃
}
for (let i = 0; i < len - 1; i++) {
farthest = Math.max(farthest, nums[i] + i);
if (i === currentMax) {
jumps++;
currentMax = farthest;
if(currentMax > len - 1){
return jumps;
}
}
}
return jumps;
}
总结：
通过贪心算法，我们可以在每一步选择能跳到最远位置的跳跃，从而计算出到达数组末尾所需的最小跳跃次数。这种方法的时间复杂度是 O(n)，空间复杂度是 O(1)，非常高效。
7.2 274. H 指数
给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且 至少 有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值，h 指数 是其中最大的那个。
我的思路：
高引用次数：
还是先对数组进行降序处理，如果说当前的引用次数大于1，h++,如果说当前的引用次数是小于等于h的就返回，如果说大于0而且是大于h的，就要对h++
但是要注意数组中只有一个的情况，因为sort排序它需要的是灵感数字嘛，所以要对0和非0的数进行处理
最后处理如果数组中的每一个数都大于h的情况，比如[11,15]，直接返回len就可以了
我的代码：
function hIndex(citations: number[]): number {
let h = 0 ;//高引用次数
let len = citations.length;
// 因为排序至少需要两个，所以要考虑一个的情况
if(len === 1){
if(citations[0] === 0){
return 0;
}else {
return 1;
}
}
// 进行降序处理
citations.sort((a , b) => b -a);
// 开始遍历
for(let i = 0 ;i < len ; i++){
if(citations[i] <= h){
return h;
}
if(citations[i] > 0 ){
h++;
}
}
return len ;
};
但是哈，其实我觉得我的代码就是在缝缝补补，最后过得也有点莫名其妙哈哈
后面我对h的更新机制进行了优化，不应该是大于0，应该是大于h，h就要++
if(citations[i] > h ){
h++;
}
总结：
H 指数的计算思路是：将引用次数降序排序后，从高到低遍历，不断更新 H 值，直到某个论文的引用次数小于当前的 H 值，此时 H 值即为所求。