前言
除了去年11月份以及今年近几月的算法刷题之外，只有在当时20年蓝桥杯准备的时候才刷过一些题，在当时就有接触到一些动归、递归回溯、贪心等等，不过那会也还是一知半解，做的题目也特别少，因为考虑到之后面试有算法题以及数据结构算法对于一个程序员十分重要，我也开始了刷题之路。
我目前的学习数据结构与算法及刷题路径：
1、学习数据结构的原理以及一些常见算法。
2、代码随想录：跟着这个github算法刷题项目进行分类刷，在刷题前可以学习一下对应类别的知识点，而且这里面每道题都讲的很详细。
3、牛客网高频面试101题：牛客网—面试必刷101题，在刷的过程中可以在leetcode同步刷一下。
4、接下来就是力扣上的专栏《剑指offer II》、《程序员面试金典（第 6 版）》…有对应的精选题单来对着刷即可。
5、大部分的高频面试、算法题刷完后，就可以指定力扣分类专栏进行一下刷题了。
刚开始刷的时候真的是很痛苦的，想到去年一道题可能就需要好几小时，真的就很难受的，不过熬过来一切都会好起来，随着题量的增多，很多题目你看到就会知道使用什么数据结构或者算法来去求解，并且思考对应的时间空间复杂度，并寻求最优解，我们一起加油！
我的刷题历程
截止2022.8.18：
1、牛客网101题(其中1题是平台案例有问题)：
2、剑指offerII：
力扣总记录数：
加油加油！
剑指offer
剑指 Offer 41. 数据流中的中位数【中等】
学习资料：LeetCode刷题力扣题解 | 剑指 Offer 41. 数据流中的中位数 | 思路讲解及Python3代码实现
题目链接：剑指 Offer 41. 数据流中的中位数
题目内容：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
思路：
1、小顶堆与大顶堆
复杂度分析：
时间复杂度：add操作时O(logn)、find是O(1) class MedianFinder { //定义小顶堆和大顶堆 //大顶堆：3 小顶堆： 4 // 2 5 // 1 6 private Queue<Integer> minQueue = new PriorityQueue<>();//小顶堆，小的在顶部，存储较大值 private Queue<Integer> maxQueue = new PriorityQueue<>((x, y) -> y - x);//大顶堆，大的在顶部，存储较小值 /** initialize your data structure here. */ public MedianFinder() { } public void addNum(int num) { //若是两边数量不相等，插入到小顶堆中 if (minQueue.size() != maxQueue.size()) { //先放入到大顶堆（先放入到小顶堆，再放入到大顶堆） minQueue.offer(num); maxQueue.offer(minQueue.poll()); }else { //初步是放入到小顶堆中（先放入到大顶堆，再放入到小顶堆） maxQueue.offer(num); minQueue.offer(maxQueue.poll()); } } public double findMedian() { //若是数量不一致，就直接返回小顶堆的元素，因为首先插入进入的是小顶堆，顶部的就是数据流中的中间数 if (minQueue.size() != maxQueue.size()) { return minQueue.peek() * 1.0; } //数量相等，那么两个堆同时相加/2 return (minQueue.peek() + maxQueue.peek()) / 2.0; } }
牛客网
最小的k个数【中等】
题目链接：最小的K个数
题目内容：给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。
**思路1：优先队列（大顶堆）**存储k个值(由大到小)，然后后面的值不断的与大顶堆的最大值作比较。
复杂度分析：
时间复杂度：O(nlogk) 空间复杂度：O(k) import java.util.ArrayList; //需要加上这个import import java.util.*; public class Solution { public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { ArrayList<Integer> res = new ArrayList<>(); if (k == 0 || input == null || input.length == 0) { return res; } //借助优先队列(大到小排序) PriorityQueue<Integer> queue = new PriorityQueue<>((o1,o2)->o2.compareTo(o1)); for (int i = 0;i < k;i++) { queue.offer(input[i]); } for (int i = k;i < input.length;i++) { if (queue.peek() > input[i]) { queue.poll(); queue.offer(input[i]); } } while (!queue.isEmpty()){ res.add(queue.poll()); } return res; } }
思路2：排序。使用快排，然后返回前k个元素即可。
复杂度分析：
时间复杂度：O(nlogn) 空间复杂度：O(1) import java.util.ArrayList; //需要加上这个import import java.util.*; public class Solution { public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { ArrayList<Integer> res = new ArrayList<>(); if (k == 0 || input == null || input.length == 0) { return res; } //快排：O(nlogn) Arrays.sort(input); for (int i = 0;i < k;i++) { res.add(input[i]); } return res; } }
数据流中的中位数【中等】
题目链接：数据流中的中位数
题目内容：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使GetMedian()方法获取当前读取数据的中位数。
思路1：使用一个集合来进行插入排序。
问题：在leetcode中超时了。
复杂度分析：
时间复杂度：Insert操作是O(n)，get是O(1) 空间复杂度：O(n) import java.util.*; public class Solution { private ArrayList<Integer> list = new ArrayList<>(); //插入操作 public void Insert(Integer num) { if (list.size() == 0) { list.add(num); }else { int i = 0; for (;i < list.size();i++) { if (list.get(i) > num){ break; } } list.add(i, num); } } public Double GetMedian() { int size = list.size(); //奇、偶个数情况 if (size % 2 == 1) { return (double)list.get(size / 2); }else { int a = list.get(size / 2 - 1); int b = list.get(size / 2); return (double)(a + b) / 2; } } }
滑动窗口的最大值【中等】
题目链接：滑动窗口的最大值
题目内容：给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
思路1：借助优先队列来实现。【牛客网超时】
复杂度分析：
时间复杂度：O(n*m) 空间复杂度：O(n) import java.util.*; public class Solution { public ArrayList<Integer> maxInWindows(int [] num, int size) { ArrayList<Integer> res = new ArrayList<>(); //越大的优先 PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2)->{ if (o1 > o2) { return -1; }else if (o1 < o2) { return 1; } return 0; }); for (int slow = 0, fast = 0; fast < num.length; fast++) { queue.add(num[fast]); //fast表示数组的坐标位置 if (fast >= (size - 1)) { //出队最大的元素 res.add(queue.peek()); //移除元素 queue.remove(num[slow]); slow++; } } return res; } }
思路2：双端队列来进行。【推荐】
时间复杂度：O(n)，数组长度为n，只遍历一遍数组。 空间复杂度：O(m)，窗口长度m，双向队列最长时，将窗口填满。 import java.util.*; public class Solution { public ArrayList<Integer> maxInWindows(int [] num, int size) { ArrayList<Integer> res = new ArrayList<>(); if (num.length < size) { return res; } //双端队列 //1、第一个窗口 ArrayDeque<Integer> queue = new ArrayDeque<Integer>(); for (int i = 0; i < size; i++) { while (!queue.isEmpty() && num[i] > queue.peekLast()) { queue.pollLast(); } queue.add(num[i]); } res.add(queue.peek()); //2、之后窗口 //后面循环遍历 （1、看当前i-size的元素值是否与当前元素值相同，相同则出队。2、每次来while循环，若是队尾元素<即将入队的元素，那么进行pollLast()） for (int i = size; i < num.length; i++) { //①由于是移动新的一位，那么就要看是否需要出队 if (queue.peek() == num[i - size]) { queue.pollFirst(); } //2、尝试过滤掉在当前队列中<当前元素的 while (!queue.isEmpty() && num[i] > queue.peekLast()) { queue.pollLast(); } queue.addLast(num[i]); res.add(queue.peek()); } return res; } }
