刷题日常(数据流中的中位数,逆波兰表达式求值,最长连续序列,字母异位词分组)

数据流中的中位数

描述

如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。我们使用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俩日 


结语: 写博客不仅仅是为了分享学习经历,同时这也有利于我巩固知识点,总结该知识点,由于作者水平有限,对文章有任何问题的还请指出,接受大家的批评,让我改进。同时也希望读者们不吝啬你们的点赞+收藏+关注,你们的鼓励是我创作的最大动力! 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/478815.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

SQL 复杂查询

目录 复杂查询 一、目的和要求 二、实验内容 &#xff08;1&#xff09;查询出所有水果产品的类别及详情。 查询出编号为“00000001”的消费者用户的姓名及其所下订单。&#xff08;分别采用子查询和连接方式实现&#xff09; 查询出每个订单的消费者姓名及联系方式。 在…

uniapp-vue2引用了vue-inset-loader插件编译小程序报错

报错信息 Error: Vue packages version mismatch: - vue3.2.45 (D:\qjy-myApp\admin-app\node_modules\vue\index.js) - vue-template-compiler2.7.16 (D:\qjy-myApp\admin-app\node_modules\vue-template-compiler\package.json) This may cause things to work incorrectly.…

VOLO实战:使用VOLO实现图像分类任务(二)

文章目录 训练部分导入项目使用的库设置随机因子设置全局参数图像预处理与增强读取数据设置Loss设置模型设置优化器和学习率调整策略设置混合精度&#xff0c;DP多卡&#xff0c;EMA定义训练和验证函数训练函数验证函数调用训练和验证方法 运行以及结果查看测试完整的代码 在上…

【Linux】TCP网络编程

目录 V1_Echo_Server V2_Echo_Server多进程版本 V3_Echo_Server多线程版本 V3-1_多线程远程命令执行 V4_Echo_Server线程池版本 V1_Echo_Server TcpServer的上层调用如下&#xff0c;和UdpServer几乎一样&#xff1a; 而在InitServer中&#xff0c;大部分也和UDP那里一样&…

XG(S)-PON原理

前言 近年来&#xff0c;随着全球范围内接入市场的飞快发展以及全业务运营的快速开展&#xff0c;已有的PON技术标准在带宽需求、业务支撑能力以及接入节点设备和配套设备的性能提升等方面都面临新的升级需求XG(S)-PON(10G GPON)是在已有GPON技术标准上演进的增强下一代GPON技…

C语言学习 12(指针学习1)

一.内存和地址 1.内存 在讲内存和地址之前&#xff0c;我们想有个⽣活中的案例&#xff1a; 假设有⼀栋宿舍楼&#xff0c;把你放在楼⾥&#xff0c;楼上有100个房间&#xff0c;但是房间没有编号&#xff0c;你的⼀个朋友来找你玩&#xff0c;如果想找到你&#xff0c;就得挨…

前端---CSS(部分用法)

HTML画页面--》这个页面就是页面上需要的元素罗列起来&#xff0c;但是页面效果很差&#xff0c;不好看&#xff0c;为了让页面好看&#xff0c;为了修饰页面---》CSS CSS的作用&#xff1a;修饰HTML页面 用了CSS之后&#xff0c;样式和元素本身做到了分离的效果。---》降低了代…

H.265流媒体播放器EasyPlayer.js无插件H5播放器关于移动端(H5)切换网络的时候,播放器会触发什么事件

EasyPlayer.js无插件H5播放器作为一款功能全面的H5流媒体播放器&#xff0c;凭借其多种协议支持、多种解码方式、丰富的渲染元素和强大的应用功能&#xff0c;以及出色的跨平台兼容性&#xff0c;为用户提供了高度定制化的选项和优化的播放体验。无论是视频直播还是点播&#x…

零基础学安全--云技术基础

目录 学习连接 前言 云技术历史 云服务 公有云服务商 云分类 基础设施即服务&#xff08;IaaS&#xff09; 平台即服务&#xff08;PaaS&#xff09; 软件即服务&#xff08;SaaS&#xff09; 云架构 虚拟化 容器 云架构设计 组件选择 基础设施即代码 集成部署…

【AI绘画】Midjourney进阶:色调详解(上)

博客主页&#xff1a; [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: AI绘画 | Midjourney 文章目录 &#x1f4af;前言&#x1f4af;Midjourney中的色彩控制为什么要控制色彩&#xff1f;为什么要在Midjourney中控制色彩&#xff1f; &#x1f4af;色调白色调淡色调明色调 &#x1f4af…

前端适配:常用的几种方案

一、rem和第三方插件 rem与em不同&#xff0c;rem会根据html的根节点字体大小进行变换&#xff0c;例如1rem就是一个字体大小那么大&#xff0c;比如根大小font size为12px&#xff0c;那么1rem即12px&#xff0c;大家可以在网上寻找单位换算工具进行换算&#xff08;从设计稿…

蓝桥杯c++算法秒杀【6】之动态规划【下】(数字三角形、砝码称重(背包问题)、括号序列、异或三角:::非常典型的必刷例题!!!)

别忘了请点个赞收藏关注支持一下博主喵&#xff01;&#xff01;&#xff01;! ! ! ! &#xff01; 关注博主&#xff0c;更多蓝桥杯nice题目静待更新:) 动态规划 三、括号序列 【问题描述】 给定一个括号序列&#xff0c;要求尽可能少地添加若干括号使得括号序列变得合…

AIGC--AIGC与人机协作:新的创作模式

AIGC与人机协作&#xff1a;新的创作模式 引言 人工智能生成内容&#xff08;AIGC&#xff09;正在以惊人的速度渗透到创作的各个领域。从生成文本、音乐、到图像和视频&#xff0c;AIGC使得创作过程变得更加快捷和高效。然而&#xff0c;AIGC并非完全取代了人类的创作角色&am…

Hot100 - 字母异位词分组

Hot100 - 字母异位词分组 最佳思路&#xff1a;排序 时间复杂度&#xff1a; O(nmlogm)&#xff0c;其中 n 为 strs 数组的长度&#xff0c;m 为每个字符串的长度。 代码&#xff1a; class Solution {public List<List<String>> groupAnagrams(String[] strs) …

C++11特性(详解)

目录 1.C11简介 2.列表初始化 3.声明 1.auto 2.decltype 3.nullptr 4.范围for循环 5.智能指针 6.STL的一些变化 7.右值引用和移动语义 1.左值引用和右值引用 2.左值引用和右值引用的比较 3.右值引用的使用场景和意义 4.右值引用引用左值及其一些更深入的使用场景分…

【H2O2|全栈】JS进阶知识(十一)axios入门

目录 前言 开篇语 准备工作 获取 介绍 使用 结束语 前言 开篇语 本系列博客主要分享JavaScript的进阶语法知识&#xff0c;本期主要对axios进行基本的了解。 与基础部分的语法相比&#xff0c;ES6的语法进行了一些更加严谨的约束和优化&#xff0c;因此&#xff0c;在…

【前端】ES6基础

1.开发工具 vscode地址 :https://code.visualstudio.com/download, 下载对应系统的版本windows一般都是64位的 安装可以自选目录&#xff0c;也可以使用默认目录 插件&#xff1a; 输入 Chinese&#xff0c;中文插件 安装&#xff1a; open in browser&#xff0c;直接右键文件…

代码美学:MATLAB制作渐变色

输入颜色个数n&#xff0c;颜色类型&#xff1a; n 2; % 输入颜色个数 colors {[1, 0, 0], [0, 0, 1]}; createGradientHeatmap(n, colors); 调用函数&#xff1a; function createGradientHeatmap(n, colors)% 输入检查if length(colors) ~ nerror(输入的颜色数量与n不一…

【Reinforcement Learning】强化学习下的多级反馈队列(MFQ)算法

&#x1f4e2;本篇文章是博主强化学习&#xff08;RL&#xff09;领域学习时&#xff0c;用于个人学习、研究或者欣赏使用&#xff0c;并基于博主对相关等领域的一些理解而记录的学习摘录和笔记&#xff0c;若有不当和侵权之处&#xff0c;指出后将会立即改正&#xff0c;还望谅…

103.【C语言】数据结构之TopK问题详细分析

目录 1.定义 2.实现 一个容易想到的方法 稍微改进的方法 最优的方法 分析方法的可行性 取出无序数组的取出前K个元素有几种可能 1.取的全是非TopK个元素中的 2.取的前K个既有非TopK个元素也有TopK个元素 3.取的前K个q恰为TopK个元素 代码实现 步骤 TestTopK代码 …