力扣爆刷第98天之hot100五连刷76-80

力扣爆刷第98天之hot100五连刷76-80

文章目录

      • 力扣爆刷第98天之hot100五连刷76-80
      • 一、295. 数据流的中位数
      • 二、121. 买卖股票的最佳时机
      • 三、55. 跳跃游戏
      • 四、45. 跳跃游戏 II
      • 五、763. 划分字母区间

一、295. 数据流的中位数

题目链接:https://leetcode.cn/problems/find-median-from-data-stream/description/?envType=study-plan-v2&envId=top-100-liked
思路:求数据流的中位数,构造数组需要考虑排序,使用优先级队列可以保证排序,可以将整个有序序列从中间划分,分为大顶堆和小顶堆,我们只需要维护大顶堆和小顶堆的size相差不超过一,那么多出一个元素的即为中位数,相等加和除二也是中位数,另外就是要维护好大顶堆里的数都小于小顶堆里的数,所以要保证这个,就要如果想往大顶堆里加数,就得先把数加入小顶堆,然后再把小顶堆的栈顶元素添加到大顶堆中,这样就可以保证有序性。
在这里插入图片描述

class MedianFinder {
        PriorityQueue<Integer> maxHeap;
        PriorityQueue<Integer> minHeap;
        public MedianFinder() {
            maxHeap = new PriorityQueue<>((a, b)-> b-a);
            minHeap = new PriorityQueue<>();
        }

        public void addNum(int num) {
            if(maxHeap.size() >= minHeap.size()) {
                maxHeap.add(num);
                minHeap.add(maxHeap.poll());
            }else{
                minHeap.add(num);
                maxHeap.add(minHeap.poll());
            }
        }

        public double findMedian() {
           if(maxHeap.size() > minHeap.size()) {
                return maxHeap.peek();
            }else if (maxHeap.size() < minHeap.size()) {
                return minHeap.peek();
            }else{
                return (maxHeap.peek() + minHeap.peek()) / 2.0;
            }
        }
    }

二、121. 买卖股票的最佳时机

题目链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/?envType=study-plan-v2&envId=top-100-liked
思路:用每一个值去减去最小值,即可得到最大值,如果prices[i] - prices[left]<0说明找到了更小的值,就要更新left。

class Solution {
    public int maxProfit(int[] prices) {
       int max = 0, left = 0;
        for(int i = 1; i < prices.length; i++) {
            if(prices[i] - prices[left] >= 0) {
                max = Math.max(max, prices[i] - prices[left]);
            }else{
                left = i;
            }
        }
        return max;
    }
}

三、55. 跳跃游戏

题目链接:https://leetcode.cn/problems/jump-game/description/?envType=study-plan-v2&envId=top-100-liked
思路:很正常的思路,维护一个最远距离,只要在到达结尾之前,i没有追上最远距离,就可以一直跳,如果追上了说明无法跳到最后。

class Solution {
    public boolean canJump(int[] nums) {
        int right = nums[0];
        for(int i = 0; i < nums.length && i <= right; i++) {
            if(i + nums[i] > right) {
                right = i + nums[i];
            }
        }
        return right >= nums.length - 1;
    }
}

四、45. 跳跃游戏 II

题目链接:https://leetcode.cn/problems/jump-game-ii/description/?envType=study-plan-v2&envId=top-100-liked
思路:不停的记录当前可以抵达的最远距离,当i抵达right时更新为最远距离,然后记录跳跃一次,即可。符合贪心思想,每次都在当前区间内选择可以跳跃的最远距离作为下一条。

class Solution {
    public int jump(int[] nums) {
        
        int right = 0, newRight = 0, count = 0;
        for(int i = 0; i < nums.length && right < nums.length-1; i++) {
            newRight = Math.max(i + nums[i], newRight);
            if(i == right) {
                right = newRight;
                count++;
            }
        }
        return count;
    }
}

五、763. 划分字母区间

题目链接:https://leetcode.cn/problems/partition-labels/description/?envType=study-plan-v2&envId=top-100-liked
思路:本题划分区间和求跳跃最远距离是差不多的思路,先记录下每种元素所能抵达的最远距离,然后在抵达当前最远距离的过程中,一直更新所能抵达的最远距离,直到i抵达最远距离,说明此区间内的元素不会出现在别的区间,即可划分该区间。

class Solution {
    
    public List<Integer> partitionLabels(String s) {
        List<Integer> list = new ArrayList<>();
        int[] nums = new int[26];
        for(int i = 0; i < s.length(); i++) {
            nums[s.charAt(i)-'a'] = i;
        }
        int left = -1, max = 0;
        for(int i = 0; i < s.length(); i++) {
            max = Math.max(max, nums[s.charAt(i)-'a']);
            if(i == max) {
                list.add(i - left);
                left = i;
            }
        }
        return list;
    }
}
上一篇:LeetCode 热题 HOT 100(P11~P20)


下一篇:【uniapp】uniapp返回上一页,并实现刷新界面数据