刷题日常（数据流中的中位数，逆波兰表达式求值，最长连续序列，字母异位词分组）
刷题日常（数据流中的中位数，逆波兰表达式求值，最长连续序列，字母异位词分组）
描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
题目意思就是当遍历到第一个数5的时候 因为此时为一个数为奇数 所有返回中间的一个 遍历到2时候 此时遍历了2个数字 因为是偶数 排序 返回俩个数的中位数 遍历3时候 此时遍历了3 个数字 因为是奇数 排序{2,3,5} 返回中位数 3 遍历4时候 此时遍历了4 个数字 为偶数 排序{2,3,4,5} 返回 (3+4)/2 ..........
题目分析：
思路一：暴力
import java.util.*;
public class Solution {
ArrayList<Integer> list = new ArrayList<>();
int count = 0;
public void Insert(Integer num) {
list.add(num);
count++;
}
public Double GetMedian() {
Collections.sort(list);
return count%2==1 ?(double)list.get(count/2):
(double)(list.get(count/2)+list.get((count/2-1)))/2;
}
}思路二：堆排序
我们来看看中位数的特征，它是数组中间个数字或者两个数字的均值，它是数组较小的一半元素中最大的一个，同时也是数组较大的一半元素中最小的一个。那我们只要每次维护最小的一半元素和最大的一半元素，并能快速得到它们的最大值和最小值，那不就可以了嘛。这时候就可以想到了堆排序的优先队列。
使用一个大根堆min维护较小一半元素 堆顶为较小元素的最大值 使用一个小跟堆max维护较大一半元素 堆顶为较大元素的最小值 如果一个数组为奇数 设置大根堆个数比小根堆多上一个 返回的时候直接返回大根堆的堆顶元素即可 如果为偶数 设置相同数量的大小根堆 返回的时候取平均在大小根堆的堆顶元素 每次输入的数据流先进入大顶堆min排序，然后将大顶堆的堆顶弹入小顶堆max中，完成整个的排序 但是因为大顶堆min的数据不可能会比小顶堆max少一个，因此需要再比较二者的长度，若是小顶堆长度大于大顶堆，需要从小顶堆中弹出堆顶到大顶堆中进行平衡
import java.util.*;
public class Solution {
//大根堆
PriorityQueue<Integer> min = new PriorityQueue<>((o1, o2)->o2 - o1);
//小根堆
PriorityQueue<Integer> max = new PriorityQueue<>((o1, o2)->o1 - o2);
public void Insert(Integer num) {
min.offer(num);
max.offer(min.poll());
if (max.size() > min.size()) {
min.offer(max.poll());
}
}
public Double GetMedian() {
//奇数个
if (min.size() > max.size()) {
return (double)min.peek();
} else {
return (double)(max.peek() + min.peek()) / 2;
}
}
}逆波兰表达式求值
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
我们平时写a+b，这是中缀表达式，写成后缀表达式就是：ab+ (a+b)*c-(a+b)/e的后缀表达式为： (a+b)*c-(a+b)/e →((a+b)*c)((a+b)/e)- →((a+b)c*)((a+b)e/)- →(ab+c*)(ab+e/)- →ab+c*ab+e/-
题目分析
逆波兰表达式严格遵循「从左到右」的运算。计算逆波兰表达式的值时，使用一个栈存储操作数，从左到右遍历逆波兰表达式，进行如下操作： 如果遇到操作数，则将操作数入栈； 如果遇到运算符，则将两个操作数出栈，其中先出栈的是右操作数，后出栈的是左操作数，使用运算符对两个操作数进行运算，将运算得到的新操作数入栈。 整个逆波兰表达式遍历完毕之后，栈内只有一个元素，该元素即为逆波兰表达式的值。
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> s = new Stack<>();
for(int i = 0;i < tokens.length; i++) {
String str = tokens[i];
if(isNumber(str)) {
s.push(Integer.parseInt(str));
} else {
int num1 =s.pop();
int num2 =s.pop();
switch(str) {
case "+" :
s.push(num2+num1);
break;
case "-" :
s.push(num2-num1);
break;
case "*" :
s.push(num2*num1);
break;
case "/" :
s.push(num2/num1);
break;
default :
}
}
}
return s.pop();
}
public boolean isNumber(String str) {
return !(str.equals("+") || str.equals("-")||str.equals("*")||str.equals("/")) ;
}
}最长连续序列
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
题目分析：
细节 ：此题目只需要它连续的个数，即使有重复的数字也没关系，跟我们以前求的最长连续的数组有所差异 所以到了 nums[i+1] 比 nums[i] 大 1 或者 相等的情况下 ，继续判断 只有相差为1的情况下才进行count++，否则就不动 其他情况 就重新重置为1
class Solution {
public int longestConsecutive(int[] nums) {
if(nums.length == 0) {
return 0;
}
Arrays.sort(nums);
int count = 1,ret = 1;
for(int i = 1;i<nums.length;i++) {
if(nums[i] - nums[i-1] == 0 || nums[i] -nums[i-1] == 1) {
if(nums[i] -nums[i-1] == 0) {
count--;
}
count++;
} else {
count = 1;
}
ret = Math.max(ret,count);
}
return ret;
}
}解法二：哈希表
将所有的数字先丢进hash表中 我们只要知道什么时候数字为起点？ 答案就是这个数的前一个数不存在于数组中 我们就要遍历这个连续序列，什么时候是终点呢？ 答案是当前数x的后一个数
x+1不存在于数组中
class Solution {
public int longestConsecutive(int[] nums) {
HashSet<Integer> hash = new HashSet<>();
for(int i : nums) {
hash.add(i);
}
int ret = 0,count;
for(int x : hash) {
if(!hash.contains(x-1)) {
//此时为起点
count = 0;
while(hash.contains(x)) {
x++;
count++;
}
ret = Math.max(count,ret);
}
}
return ret;
}
}字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
题目分析：
创建一个hash表 Key为String ，Value 为String[] 1.进行遍历整个数组 拿到其中的数组元素 先将它排序 可以获取到最原始Key 2.如果发现hash表中存在Key，可以直接在它的Value后面添加 创建一个String[]即可 然后在它的Value后面添加 3.最后返回hash表上的value即可
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String,List<String>> hash = new HashMap<>();
for(String str : strs) {
char[] ch = str.toCharArray();
Arrays.sort(ch);
String s = new String(ch);
if(!hash.containsKey(s)) {
hash.put(s,new ArrayList<>());
}
hash.get(s).add(str);
}
return new ArrayList<>(hash.values());
}
}1122-23俩日
结语： 写博客不仅仅是为了分享学习经历，同时这也有利于我巩固知识点，总结该知识点，由于作者水平有限，对文章有任何问题的还请指出，接受大家的批评，让我改进。同时也希望读者们不吝啬你们的点赞+收藏+关注，你们的鼓励是我创作的最大动力！
腾讯云开发者
