LC-前K个高频元素、数据流的中位数、买卖股票的最佳时机、跳跃游戏、跳跃游戏II

LC-前K个高频元素、数据流的中位数、买卖股票的最佳时机、跳跃游戏、跳跃游戏II

引用

CSDN

1.

https://m.blog.csdn.net/m0_73902080/article/details/145814469

本文精选了5个经典的算法问题及其解决方案，包括前K个高频元素、数据流的中位数、买卖股票的最佳时机、跳跃游戏以及跳跃游戏II。每个问题都包含了详细的思路分析和代码实现，适合对算法感兴趣的读者深入学习。

前K个高频元素

思路：

1. 统计频率：

• 首先，我们需要统计数组中每个元素的出现频率。这可以通过哈希表（HashMap）来实现，其中键是数组中的元素，值是该元素的出现次数。

2. 使用堆：

• 我们需要找出频率前 k 高的元素。为了实现这一点，可以使用一个最小堆。堆的大小保持为
  k
  ，每次插入元素时，如果堆的大小超过
  k
  ，则弹出堆顶元素。这样，堆中的元素就是出现频率前
  k
  高的元素。
• 通过维护一个大小为
  k
  的堆，保证了堆顶元素是频率最低的元素，而堆中的其他元素频率都较高。
  解法步骤：

1. 统计元素频率：使用哈希表统计每个元素出现的频率。
2. 使用最小堆：遍历频率表，将元素根据频率插入最小堆中。
3. 返回堆中的元素：堆中的元素就是出现频率前
   k
   高的元素。

  
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        //使用哈希表统计每个元素的频率
        Map<Integer,Integer> frequencyMap = new HashMap<>();
        for(int num : nums){
            frequencyMap.put(num,frequencyMap.getOrDefault(num,0) + 1);
        }
        //使用最小堆存储频率前k高的元素
        PriorityQueue<Map.Entry<Integer,Integer>> minHeap = new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));//按照频率升序排列
        for(Map.Entry<Integer,Integer> entry : frequencyMap.entrySet()){
            minHeap.offer(entry);
            if(minHeap.size() > k){
                minHeap.poll();//保证堆中最多有k个元素
            }
        }
        //获取堆中的元素
        int[] result = new int[k];
        int index = 0;
        while (!minHeap.isEmpty()) {
            result[index++] = minHeap.poll().getKey();  // 只取元素的值
        }
        return result;
    }
}  

数据流的中位数

思路：

1. 两个堆的维护：

• 最大堆用于存储数据流中较小的一半元素，堆顶元素是这部分数据的最大值。
• 最小堆用于存储数据流中较大的一部分元素，堆顶元素是这部分数据的最小值。
  

2. 插入数据：

• 对于每次插入数据，首先将数据插入合适的堆中。为了保持堆的平衡（即最大堆的大小和最小堆的大小之差不超过 1），可能需要从一个堆向另一个堆移动元素。

3. 中位数的计算：

• 如果两个堆的大小相等，中位数是两个堆顶元素的平均值。
• 如果最大堆的大小多一个元素，则中位数是最大堆的堆顶元素。

  
class MedianFinder {
    //最大堆，存储较小的一半元素
    private PriorityQueue<Integer> maxHeap;
    //最小堆，存储较大的一半元素
    private PriorityQueue<Integer> minHeap;
    //初始化对象
    public MedianFinder() {
        maxHeap = new PriorityQueue<>((a,b) -> b - a);//最大堆（降序排列）
        minHeap = new PriorityQueue<>();//最小堆（升序排列）
    }
    
    //添加一个数字到数据流中
    public void addNum(int num) {
        //将元素添加到最大堆
        maxHeap.offer(num);
        //将最大堆的最大元素移到最小堆
        minHeap.offer(maxHeap.poll());
        //如果最小堆的大小大于最大堆，则将最小堆的最小元素移回最大堆
        if(minHeap.size() > maxHeap.size()){
            maxHeap.offer(minHeap.poll());
        }
    }
    
    //返回当前数据流的中位数
    public double findMedian() {
        //如果两个堆的大小相等，中位数是两个堆顶元素的平均值
        if(maxHeap.size() == minHeap.size()){
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        }else{
            //如果最大堆的大小小于最小堆，中位数是最大堆的堆顶元素
            return maxHeap.peek();
        }
    }
}
/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */  

买卖股票的最佳时机

贪心算法思路：

1. 核心思想：

• 在贪心算法中，我们的目标是在每个步骤中做出最优的选择，即在每一天选择买入股票时，我们会选择当前为止的最低股价。
• 然后，每次我们计算可能的利润，即当前价格减去最低股价，更新最大利润。

2. 详细步骤：

• 每天我们都会尝试买入股票（即记录当前的最低股价）。
• 每次卖出时，计算当前的利润并与之前的最大利润比较。
• 每次选择的都是当前最优（最低股价买入，当前股价卖出），这就是贪心算法的思路。

  
class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length == 0){
            return 0;
        }
        int minPrice = Integer.MAX_VALUE;//初始化为一个很大的数，表示最低股价
        int maxProfit = 0;//初始化最大利润为0
        for(int price : prices){
            //更新最低股价
            minPrice = Math.min(minPrice,price);
            //计算当前价格卖出时的利润
            int profit = price - minPrice;
            //更新最大利润
            maxProfit = Math.max(maxProfit,profit);
        }
        return maxProfit;
    }
}  

跳跃游戏

思路：
我们希望判断是否能够从数组的第一个位置跳跃到最后一个位置。对于每个位置，我们知道你最多可以跳跃的长度。我们需要判断在遍历整个数组时，是否有可能到达最后一个位置。
贪心算法的关键思想是：

• 在遍历过程中，我们维护一个变量
  maxReach
  ，表示从当前位置能够到达的最远位置。
• 如果
  maxReach
  在某个时刻等于或超过了数组的最后一个下标，说明我们能够到达最后一个位置。
• 如果在遍历时，
  maxReach
  永远无法到达当前的位置，则说明无法到达最后一个位置。
  步骤：

1. 初始化
   maxReach
   为 0，表示从第一个位置能够跳跃的最远距离。
2. 遍历数组中的每个位置
   i
   ：

• 如果当前索引
  i
  超出了
  maxReach
  ，说明无法到达该位置，返回
  false
  。
• 否则，更新
  maxReach = Math.max(maxReach, i + nums[i])
  ，表示当前能够到达的最远位置。

3. 如果在遍历过程中，
   maxReach
   达到或超过了最后一个位置，返回
   true
   。
4. 如果遍历结束，仍然无法到达最后一个位置，返回
   false
   。

  
class Solution {
    public boolean canJump(int[] nums) {
        int maxReach = 0;//最远能到达的距离
        int n = nums.length;
        for(int i = 0;i < n;i++){
            //如果当前位置无法到达，返回false
            if(i > maxReach){
                return false;
            }
            //更新最远能到达的距离
            maxReach = Math.max(maxReach,i + nums[i]);
            //如果已经能够到达最后一个位置，返回true
            if(maxReach >= n - 1){
                return true;
            }
        }
        return false;
    }
}  

跳跃游戏II

这个问题是跳跃游戏 问题的一个变种，要求在数组中找到最少的跳跃次数以到达数组的最后一个位置。与跳跃游戏 I 的问题不同，这里我们需要返回最小跳跃次数，而不是判断是否可以到达。
思路：
为了找到最小跳跃次数，我们可以使用贪心算法。核心思想是：

1. 我们从左到右遍历数组，维护一个区间
   [start, end]
   ，表示可以通过当前跳跃到达的最远位置。
2. 每次我们尝试更新这个区间，在遍历过程中找到当前跳跃可以到达的最远位置
   end
   。
3. 当
   end
   达到或超过数组的最后一个位置时，说明我们已经找到最小的跳跃次数。
   步骤：
4. 初始化
   jumps
   （跳跃次数）为 0，
   currentEnd
   （当前跳跃能够到达的最远位置）为 0，
   farthest
   （当前可以跳跃的最远位置）为 0。
5. 遍历数组，对于每个位置
   i
   ，更新
   farthest = Math.max(farthest, i + nums[i])
   ，表示当前位置能跳跃到的最远位置。
6. 如果遍历到的位置
   i
   达到
   currentEnd
   （即当前跳跃的最远位置），则进行跳跃（即更新
   jumps
   ），并将
   currentEnd
   更新为
   farthest
   。
7. 如果
   currentEnd
   达到或超过最后一个位置，说明已经到达终点，返回跳跃次数。

  
class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int jumps = 0;
        int currentEnd = 0;//当前跳跃能够到达的最远位置
        int farthest = 0;//当前可以跳跃到的最远位置
        for(int i = 0;i < n - 1;i++){//遍历到倒数第二个元素
            farthest = Math.max(farthest,i + nums[i]);//更新能跳到的最远位置 
            //如果当前已经到达了最远位置，进行一次跳跃
            if(i == currentEnd){
                jumps++;
                currentEnd = farthest;//更新当前跳跃的最远位置
                //如果当前跳跃可以到达最后一个位置，直接返回
                if(currentEnd >= n - 1){
                    return jumps;
                }
            }
        }
        return jumps;
    }
}