Leetcode 295.数据流的中位数

295.数据流的中位数

问题描述

中位数是有序整数列表中的中间值。如果列表的大小是偶数,则没有中间值,中位数是两个中间值的平均值。

  • 例如 arr = [2,3,4] 的中位数是 3
  • 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5

实现 MedianFinder 类:

  • MedianFinder() 初始化 MedianFinder 对象。
  • void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
  • double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

示例 1:

输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

提示:

  • -105 <= num <= 105
  • 在调用 findMedian 之前,数据结构中至少有一个元素
  • 最多 5 * 104 次调用 addNumfindMedian

解题思路与代码实现

思路:

设置两个优先队列(相当于堆)queMinqueMax

queMin:记录小于等于中位数的数;

queMax:记录大于中位数的数

添加元素时维持: queMax元素个数 <=queMin的元素个数 <=queMax元素个数 +1

取中位数时:

  • queMax元素个数 ==queMin的元素个数,从queMinqueMax 取出二者队头元素的平均值;
  • queMax元素个数 <queMin的元素个数,从queMin取出队头元素;

代码实现:

class MedianFinder {PriorityQueue<Integer> queMin; // 记录小于等于中位数的数PriorityQueue<Integer> queMax; // 记录大于中位数的数public MedianFinder() {queMin = new PriorityQueue<>(Comparator.reverseOrder()); // 降序排序queMax = new PriorityQueue<>(Comparator.naturalOrder()); // 升序排序}/*** 添加元素时保持:* queMin的元素个数 >= queMax元素个数 && queMin的元素个数 <= queMax元素个数 + 1*/public void addNum(int num) {if (queMin.isEmpty() || queMin.peek() >= num) { // 第一个元素或者num小于等于queMin最大元素queMin.offer(num);// 尽可能保持两者元素数量相等if (queMin.size() > queMax.size() + 1) {queMax.offer(queMin.poll());}} else { // num大于queMax最小元素queMax.offer(num);// 尽可能保持两者元素数量相等if (queMax.size() > queMin.size()) {queMin.offer(queMax.poll());}}}public double findMedian() {if (queMin.size() > queMax.size()) {return queMin.peek();}return (queMin.peek() + queMax.peek()) / 2.0;}
}

155. 最小栈

问题描述

设计一个支持 pushpoptop 操作,并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

示例 1:

输入:
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]输出:
[null,null,null,null,-3,null,0,-2]解释:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示:

  • -231 <= val <= 231 - 1
  • poptopgetMin 操作总是在 非空栈 上调用
  • push, pop, top, and getMin最多被调用 3 * 104

解题思路与代码实现

思路:

设置辅助栈,栈中元素为长度为2的数组,分别存当前插入的val值和它插入后栈中的最小val值。

插入元素时:直接放在栈顶

  • 当前栈为空时,当前插入的val值就是插入后栈中的最小val值;
  • 当前栈为不空时,插入后栈中的最小val值要么是当前插入的val值,要么是插入前栈中的最小val值;

取出最小元素:从栈顶元素获取当前栈中的最小val值;

代码实现:

class MinStack {// 栈中元素为长度为2的数组,分别存当前插入的val值和它插入后栈中的最小val值Stack<int[]> stack = null;public MinStack() {stack = new Stack<>();}public void push(int val) {if (stack.isEmpty()) { // 当前堆栈为空stack.push(new int[] { val, val });} else { // 堆栈不为空int[] item = stack.peek();stack.push(new int[] { val, Math.min(item[1], val) });}}// 栈顶元素出栈public void pop() {stack.pop();}public int top() {int[] item = stack.peek();return item[0];}// 获取堆栈中的最小元素public int getMin() {int[] item = stack.peek();return item[1];}
}

踩坑点

栈顶元素需要记录当前栈中最小的val值

37. 解数独

问题描述

编写一个程序,通过填充空格来解决数独问题。

数独的解法需 遵循如下规则

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)

数独部分空格内已填入了数字,空白格用 '.' 表示。

示例 1:

img

输入:board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出:[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释:输入的数独如上图所示,唯一有效的解决方案如下所示:

提示:

  • board.length == 9
  • board[i].length == 9
  • board[i][j] 是一位数字或者 '.'
  • 题目数据 保证 输入数独仅有一个解

解题思路与代码实现

思路:

回溯暴力解,给回溯函数设置返回值,当找到一个可行解时,停止计算,返回结果。

代码实现:

class Solution {private final int N = 9;public void solveSudoku(char[][] board) {backtracking(board, 0, 0);}/*** 回溯函数* 设置返回值是为了当找到一个可行解时,停止计算,返回结果** @return flag 是否找到了唯一的解*/private boolean backtracking(char[][] board, int row, int col) {if (row == N) { // 遍历了整个棋盘返回truereturn true;}// 当前位置已有数字,去处理下一位置if (board[row][col] != '.') {int nextRow = col == N - 1 ? row + 1 : row;int nextCol = col == N - 1 ? 0 : col + 1;boolean flag = backtracking(board, nextRow, nextCol);return flag;}for (char k = '1'; k <= '9'; k++) {// 用1-9在当前位置尝试if (isValid(board, row, col, k)) {board[row][col] = k;int nextRow = col == N - 1 ? row + 1 : row;int nextCol = col == N - 1 ? 0 : col + 1;boolean flag = backtracking(board, nextRow, nextCol);if (flag) { // 找到了可行解,停止计算return true;}board[row][col] = '.'; // 回溯}}// 用1-9在当前位置都不满足,返回falsereturn false;}/*** 判断当前位置是否有效*/private boolean isValid(char[][] board, int row, int col, char c) {// 判断同一行或者同一列是否有重复数字for (int i = 0; i < N; i++) {if (c == board[row][i] // 同一行|| c == board[i][col]) { // 同一列return false;}}// 判断3*3区域是否有重复数字int startX = row / 3 * 3;int startY = col / 3 * 3;for (int i = startX; i < startX + 3; i++) {for (int j = startY; j < startY + 3; j++) {if (c == board[i][j]) {return false;}}}return true;}}

踩坑点

判断当前位置试探的数字在所在的3*3棋盘是否重复

71.简化路径

问题描述

给你一个字符串 path ,表示指向某一文件或目录的 Unix 风格 绝对路径 (以 '/' 开头),请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中,一个点(.)表示当前目录本身;此外,两个点 (..) 表示将目录切换到上一级(指向父目录);两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠(即,'//')都被视为单个斜杠 '/' 。 对于此问题,任何其他格式的点(例如,'...')均被视为文件/目录名称。

请注意,返回的 规范路径 必须遵循下述格式:

  • 始终以斜杠 '/' 开头。
  • 两个目录名之间必须只有一个斜杠 '/'
  • 最后一个目录名(如果存在)不能'/' 结尾。
  • 此外,路径仅包含从根目录到目标文件或目录的路径上的目录(即,不含 '.''..')。

返回简化后得到的 规范路径

示例 1:

输入:path = "/home/"
输出:"/home"
解释:注意,最后一个目录名后面没有斜杠。 

示例 2:

输入:path = "/../"
输出:"/"
解释:从根目录向上一级是不可行的,因为根目录是你可以到达的最高级。

示例 3:

输入:path = "/home//foo/"
输出:"/home/foo"
解释:在规范路径中,多个连续斜杠需要用一个斜杠替换。

示例 4:

输入:path = "/a/./b/../../c/"
输出:"/c"

提示:

  • 1 <= path.length <= 3000
  • path 由英文字母,数字,'.''/''_' 组成。
  • path 是一个有效的 Unix 风格绝对路径。

解题思路与代码实现

思路:

使用辅助栈求解,先对字符串先切片,遍历字符串数组判断:

  • 如果不是空串且不是".“且不是”…",加入到栈;
  • 如果是".",跳过,不作任何处理;
  • 如果是"…"且栈不为空,弹出栈顶元素;

最后拼接栈中字符串返回。

代码实现:

class Solution {public String simplifyPath(String path) {String[] strs = path.split("/"); // 字符串切片Stack<String> stack = new Stack<>(); // 辅助栈for (String str : strs) {// 切片后:当前字符串不为空串也不为.和..,加入到栈中if (!str.equals("") && !str.equals(".") && !str.equals("..")) {stack.push(str);} else if (str.equals("..") && !stack.isEmpty()) {// 当前字符串为..且栈中不为空,则弹出栈顶元素stack.pop();}}if (stack.isEmpty()) { // 栈为空,返回根目录return "/";}// 拼接栈中字符串StringBuilder builder = new StringBuilder();while (!stack.isEmpty()) {builder.insert(0, "/" + stack.pop());}return builder.toString();}
}

踩坑点

没想到字符串切片,纯指针实现切片,代码臃肿。

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

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

相关文章

【笔记】太久不用redis忘记怎么后台登陆了

&#xff01;首先启动虚拟机linux的centos7 2.启动finalshell 我的redis启动在根目录用 redis-server redis.conf --启动 systemctl status redis --查看redis状态 是否active redis-cli -h centos的ip地址 -p 你要用的redis端口号&#xff08;默认为6379&#xff09; -a 你…

UDP通讯实现

服务器端&#xff1a; 1.获取套接字 int fd;fdsocket(AF_INET,SOCK_DGRAM,0);if(fd<0){perror("socket");exit(0);} #include <sys/types.h> #include <sys/socket.h> int socket(int domain, int type, int protocol); -domain: 指定通信域&…

LInux安装

目录 1. LInux优点 1.1 安全性高 1.2 稳定性和可靠性高 1.3 开源和免费 1.4 资源利用效率 2. Linux虚拟机下载 2.1 VMware安装 2.2 虚拟机安装 2.3 Centos7下载 2.4 简单设置Centors-7 2.4.1 首次进入 2.4.2 联网设置 2.4.3 自动联网设置 2.4.4 自动锁屏设置 Li…

Hadoop-15-Hive 元数据管理与存储 Metadata 内嵌模式 本地模式 远程模式 集群规划配置 启动服务 3节点云服务器实测

章节内容 上一节我们完成了&#xff1a; Hive中数据导出&#xff1a;HDFSHQL操作上传内容至Hive、增删改查等操作 背景介绍 这里是三台公网云服务器&#xff0c;每台 2C4G&#xff0c;搭建一个Hadoop的学习环境&#xff0c;供我学习。 之前已经在 VM 虚拟机上搭建过一次&am…

C++初学者指南-5.标准库(第一部分)--顺序容器

C初学者指南-5.标准库(第一部分)–顺序容器 文章目录 C初学者指南-5.标准库(第一部分)--顺序容器标准顺序容器常见特点规律性&#xff1a;复制&#xff0c;分配&#xff0c;比较类型推导(C17)常用接口部分 array<T,size>vector\<T>C 的默认容器快速回顾迭代器范围插…

【粉丝福利 | 第8期】值得收藏!推荐10个好用的数据血缘工具

⛳️ 写在前面参与规则&#xff01;&#xff01;&#xff01; ✅参与方式&#xff1a;关注博主、点赞、收藏、评论&#xff0c;任意评论&#xff08;每人最多评论三次&#xff09; ⛳️本次送书1~4本【取决于阅读量&#xff0c;阅读量越多&#xff0c;送的越多】 目前市面上绝…

文档图像处理:大模型的突破与新探索

前言 随着数字化时代的到来&#xff0c;文档图像处理技术在各行各业扮演着越来越重要的角色。在2023第十二届中国智能产业高峰论坛&#xff08;CIIS 2023&#xff09;的专题论坛上&#xff0c;合合信息智能技术平台事业部副总经理、高级工程师丁凯博士分享了当前文档图像处理面…

如何学习和提升SQL

资料来源于腾讯技术直播&#xff0c;只作为学习记录&#xff0c;如有侵权&#xff0c;请联系作者进行删除

4.1 操作系统

大纲 进程管理重点&#xff0c;占本章历年考试一半分数&#xff0c; 前趋图、信号量和PV操作、死锁和银行家算法 出计算题 作业管理历年考试从来没有考过 操作系统概述 进程管理 进程的组成和状态 前趋图 进程资源图 真题 1

实验一 MATLAB \ Python数字图像处理初步

一、实验目的&#xff1a; 1&#xff0e;熟悉及掌握在MATLAB\Python中能够处理哪些格式图像。 2&#xff0e;熟练掌握在MATLAB\Python中如何读取图像。 3&#xff0e;掌握如何利用MATLAB\Python来获取图像的大小、颜色、高度、宽度等等相关信息。 4&#xff0e;掌握如何在M…

java花店管理系统eclipse开发mysql数据库

1 绪论 1.1 系统开发目的 随着人们物质生活水平和经济水平的不断提高&#xff0c;室内绿化布置、家庭园艺装饰、礼仪鲜花等日益受到重视和青睐&#xff0c;以及送鲜花给亲朋好友来表达自己的情谊。传统的花店对于信息的管理的主要方式是基于文本、表格等纸质手工处理&#xf…

SpringCloudAlibaba基础五 Nacos配置中心

一 Nacos配置中心介绍 官方文档&#xff1a;https://github.com/alibaba/spring-cloud-alibaba/wiki/Nacos-config Nacos 提供用于存储配置和其他元数据的 key/value 存储&#xff0c;为分布式系统中的外部化配置提供服务器端和客户端支持。使用 Spring Cloud Alibaba Nacos C…

剪辑抽帧技巧有哪些 剪辑抽帧怎么做视频 剪辑抽帧补帧怎么操作 剪辑抽帧有什么用 视频剪辑哪个软件好用在哪里学

打破视频节奏&#xff0c;让作品告别平庸。抽帧剪辑可以改变视频叙事节奏&#xff0c;人为制造冲突、转折、卡顿的效果。这种剪辑方式&#xff0c;不仅可以推进剧情发展&#xff0c;还能吸引观众的注意力&#xff0c;有效防止观影疲劳。有关剪辑抽帧技巧有哪些&#xff0c;剪辑…

mysql数据库中的视图view的概念和详细说明

目录 一、定义 二、视图view的分类 &#xff08;一&#xff09;按功能和特性分类 1、普通视图&#xff08;Regular View/Standard View&#xff09; 2、索引视图&#xff08;Indexed View&#xff09; 3、分割视图&#xff08;Partitioned View/Distributed Partitioned …

1.认识微服务

认识微服务 1.微服务2.微服务架构 1.微服务 微服务是一种经过良好架构设计的分布式架构设计&#xff0c;微服务架构特征&#xff1a; 单一指职责&#xff1a;微服务拆分粒度更小&#xff0c;每一个服务都对应唯一的业务能力&#xff0c;做到单一职责&#xff0c;避免重复业务…

Python提取视频文案

Python提取视频文案 1、背景描述2、视频转音频3、音频转文字 1、背景描述 在多媒体应用中&#xff0c;视频是一个信息量巨大的载体。然而&#xff0c;有时我们需要从视频中提取语音并转换为文本&#xff0c;以用于文本分析和机器学习训练 其中主要涉及到两个过程&#xff1a;视…

LVS+Nginx高可用集群---Nginx进阶与实战(二)

1.Nginx配置SSL证书提供https访问 大概步骤&#xff1a;云服务器-注册域名-配置SSL证书-下载证书&#xff0c;并且拷贝到nginx的conf目录下。 检查nginx是否含有ssl的模块-安装ssl模块-配置HTTPS模块-配置SSL-主域名可以通过HTTPS访问 配置模版&#xff1a; 添加上开启SSL的代…

python-课程满意度计算(赛氪OJ)

[题目描述] 某个班主任对学生们学习的的课程做了一个满意度调查&#xff0c;一共在班级内抽取了 N 个同学&#xff0c;对本学期的 M 种课程进行满意度调查。他想知道&#xff0c;有多少门课是被所有调查到的同学都喜欢的。输入格式&#xff1a; 第一行输入两个整数 N , M 。 接…

微服务-初级篇

微服务-初级篇 认识微服务1.1 单体架构1.2 分布式架构1.3 微服务 SpringCloud2.1 了解2.2 服务拆分原则2.3 服务拆分效果 Nacos注册中心3.1 认识和安装Nacos3.1.1 Nacos下载3.1.2 Nacos安装 3.2 服务注册到Nacos Feign远程调用4.1 Feign引入4.2 Feign配置 认识微服务 1.1 单体…

LVS-DR负载均衡

LVS-DR负载均衡 LVS—DR工作模式 原理 客户端访问调度器的VIP地址&#xff0c;在路由器上应该设置VIP跟调度器的一对一的映射关系&#xff0c;调度器根据调度算法将该请求“调度“到后端真实服务器&#xff0c;真实服务器处理完毕后直接将处理后的应答报文发送给路由器&#xf…