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 值即为所求。