力扣爆刷第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;
}
}