力扣面试150(11/150)

发布于:2025-07-07 ⋅ 阅读:(13) ⋅ 点赞:(0)

7.2 45. 跳跃游戏 II

给定一个长度为 n0 索引整数数组 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 值即为所求。


网站公告

今日签到

点亮在社区的每一天
去签到