算法通关村第5关【白银】| 哈希和栈经典算法题

1.两个栈实现队列 

思路:两个栈,一个输入栈,一个输出栈。

当需要输入的时候就往inStack中插入,需要输出就往outStack中输出,当输出栈是空就倒出输入栈的数据到输出栈中,这样就保证了后插入的数据从栈顶倒入了栈底,输出栈栈顶弹出的一定是原先输入栈栈底的数据,也就是先进来的,即先进先出。 

class MyQueue {Deque<Integer> inStack ;Deque<Integer> outStack;public MyQueue() {inStack = new LinkedList<>();outStack = new LinkedList<>();}public void push(int x) {inStack.push(x);}public int pop() {if(outStack.isEmpty()){while(!inStack.isEmpty()){outStack.push(inStack.pop());}return outStack.pop();}else{return outStack.pop();}}public int peek() {if(outStack.isEmpty()){while(!inStack.isEmpty()){outStack.push(inStack.pop());}return outStack.peek();}else{return outStack.peek();}}public boolean empty() {return inStack.isEmpty() && outStack.isEmpty();}
}

2.两个队列实现栈

思路:确保队列前端是后进数据,用两个队列实现后插入数据在前面效果

(从下方叠罗汉,每次插入,先放好一层,然后将原先所有数据抬起然后放到新的一层上面,这样达到后加入数据始终在前面)。

queue2必定为空,数据压入queue2,这样就确保队列前端是后进的数据

然后将queue1的数据灌入queue2,交换queue1和queue2,queue2仍然为空

需要弹出的时候就弹出queue1的数据就行,因为queue1始终保持后进数据在队列前端。

class MyStack {Deque<Integer> q1;Deque<Integer> q2;public MyStack() {q1 = new LinkedList<>();q2 = new LinkedList<>();}public void push(int x) {q2.offer(x);while(!q1.isEmpty()){q2.offer(q1.remove());}Deque<Integer> t = q1;q1 = q2;q2 = t;}public int pop() {return q1.remove();}public int top() {return q1.peek();}public boolean empty() {return q1.isEmpty();}
}

3.n数之和

两数之和

思路:

一、暴力两层循环 ,不可取

二、使用哈希表。每遍历过一个元素就记录下来,判断有没有包含target-nums[i]的值

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer,Integer> map = new HashMap<>();for(int i = 0;i<nums.length;i++){int tar = target - nums[i];if(map.containsKey(tar)){return new int[]{i,map.get(tar)};}else{map.put(nums[i],i);}}return null;}
}

三数之和

思路:

一、双层循环+两数之和。

排序之后,先确定nums[i]为三数之一,然后从剩下的数中找到两数之和为-nums[i]的数,三数之和就是0.

class Solution {public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();if (nums == null || nums.length < 3) {return result;}Arrays.sort(nums);for (int i = 0; i < nums.length - 2; i++) {if (i > 0 && nums[i] == nums[i - 1]) {continue; // Skip duplicates}int target = -nums[i];Map<Integer, Integer> map = new HashMap<>();for (int j = i + 1; j < nums.length; j++) {int complement = target - nums[j];if (map.containsKey(complement)) {result.add(Arrays.asList(nums[i], complement, nums[j]));while (j + 1 < nums.length && nums[j] == nums[j + 1]) {j++; // Skip duplicates}}map.put(nums[j], j);}}return result;}
}

二、排序+双指针

先从小到大排序,两层循环

外层循环用来确定一个三数之一,然后内层循环双指针确定另外两数

之和大于目标right--

之和小于目标left++

之和等于目标加入答案,同时为了避免重复答案,需要跳过相同的数字

外层循环需要跳过相同的数字避免重复答案,同时必须是nums[i]==nums[i-1]

例如:[-1,-1,0,1,2]

[-1,0,1],[-1,-1,2]都是答案,不能跳过第一个-1

if(i>0&&nums[i] == nums[i-1]){continue;}
class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result = new ArrayList<>();if (nums == null || nums.length < 3) {return result;}Arrays.sort(nums);int i,l,r;for(i=0;i<nums.length;i++){if(nums[i]>0) break;if(i>0&&nums[i]==nums[i-1]){continue;}int tar = -nums[i];for(l = i+1,r = nums.length -1;l<r;){if(nums[l]+nums[r]>tar){r--;}else if(nums[l]+nums[r]<tar){l++;}else{List<Integer> list = new ArrayList<>();list.add(nums[i]);list.add(nums[l]);list.add(nums[r]);result.add(list);while (r > l && nums[r] == nums[r - 1]) r--;while (r > l && nums[l] == nums[l + 1]) l++;l++;r--;}}}return result;}
}

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

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

相关文章

Docker修改容器ulimit的全部方案及各方案的详细步骤

要修改Docker容器的ulimit&#xff08;用户资源限制&#xff09;&#xff0c;有以下三种方案&#xff0c;每个方案的详细步骤如下&#xff1a; 方案一&#xff1a;在Dockerfile中设置ulimit 打开您的Dockerfile。在文件中添加以下命令来修改ulimit&#xff1a;RUN ulimit -n …

他们朝我扔泥巴(scratch)

前言 纯~~~属~~~虚~~~构~~~&#xff08;同学看完短视频要我做&#xff0c;蟹蟹你&#xff09; 用scratch做的&#xff0c;幼稚得嘞(&#xffe3;_&#xffe3;|||)呵呵&#xff08;强颜欢笑&#xff09; 完成视频 视频试了好久&#xff0c;就是传不上来&#xff0c;私信我加我…

LabVIEW开发灭火器机器人

LabVIEW开发灭火器机器人 如今&#xff0c;自主机器人在行业中有着巨大的需求。这是因为它们根据不同情况的适应性。由于消防员很难进入高风险区域&#xff0c;自主机器人出现了。该机器人具有自行检测火灾的能力&#xff0c;并通过自己的决定穿越路径。 由于消防安全是主要问…

开源项目-数据可视化分析平台

哈喽,大家好,今天给大家带来一个开源项目-数据可视化分析平台。项目通过SpringBoot实现 数据可视化分析平台主要有数据源管理,项目管理,数据集管理,图表管理,看板管理等功能 登录 数据源管理 数据源管理功能可以添加MySQL,Oracle,PostgreSQL等类型的数据源信息 项目…

24 WEB漏洞-文件上传之WAF绕过及安全修复

目录 WAF绕过上传参数名解析:明确哪些东西能修改?常见绕过方法&#xff1a;符号变异-防匹配( " ;)数据截断-防匹配(%00 ; 换行)重复数据-防匹配(参数多次)搜索引擎搜索fuzz web字典文件上传安全修复方案 WAF绕过 safedog BT(宝塔) XXX云盾 宝塔过滤的比安全狗厉害一些&a…

LeetCode 热题 100(七):105. 从前序与中序遍历序列构造二叉树、14. 二叉树展开为链表

题目一&#xff1a; 105. 从前序与中序遍历序列构造二叉树https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ 思路&#xff1a;依据前序遍历的根左右和中序遍历的左根右&#xff0c; 且根左长度&#xff1d;左根 代码&#xff1a; …

【已解决】pycharm突然双击无法打开,重启电脑也不管用

1.问题&#xff1a; pycharm突然双击无法打开&#xff0c;重启电脑也不管用 2.解决 2.1 方法一&#xff08;修改Roaming&#xff09; 1.找到C盘对应路径下的pycharm版本 2. 用记事本打开文件类型为VMOPTIONS文件 3. 修改或删除最后一行的映射路径 4.保存退出 2.2 方法二…

二级MySQL(二)——编程语言,函数

SQL语言又称为【结构化查询语言】 请使用FLOOR&#xff08;x&#xff09;函数求小于或等于5.6的最大整数 请使用TRUNCATE&#xff08;x&#xff0c;y&#xff09;函数将数字1.98752895保留到小数点后4位 请使用UPPER&#xff08;&#xff09;函数将字符串‘welcome’转化为大写…

Linux重置ROOT密码(CentOS)

解释说明 在CentOS中重置root密码通常需要进入单用户模式&#xff0c;这是一个没有密码限制的特殊模式&#xff0c;允许您以root权限登录系统并更改密码。 重启系统 如果您无法登录到系统&#xff0c;可以通过重启系统来开始这个过程。您可以使用虚拟机控制台、物理服务器控制台…

Leetcode 191.位1的个数

编写一个函数&#xff0c;输入是一个无符号整数&#xff08;以二进制串的形式&#xff09;&#xff0c;返回其二进制表达式中数字位数为 1 的个数&#xff08;也被称为汉明重量&#xff09;。 提示&#xff1a; 请注意&#xff0c;在某些语言&#xff08;如 Java&#xff09;中…

java+springboot+mysql农业园区管理系统

项目介绍&#xff1a; 使用javaspringbootmysql开发的农业园区管理系统&#xff0c;系统包含超级管理员、管理员、用户角色&#xff0c;功能如下&#xff1a; 超级管理员&#xff1a;管理员管理&#xff1b;用户管理&#xff1b;土地管理&#xff08;租赁&#xff09;&#x…

语言模型(language model)

文章目录 引言1. 什么是语言模型2. 语言模型的主要用途2.1 言模型-语音识别2.2 语言模型-手写识别2.3 语言模型-输入法 3. 语言模型的分类4. N-gram语言模型4.1 N-gram语言模型-平滑方法4.2 ngram代码4.3 语言模型的评价指标4.4 两类语言模型的对比 5. 神经网络语言模型6. 语言…

RabbitMQ的镜像队列

镜像队列 如果 RabbitMQ 集群中只有一个 Broker 节点&#xff0c;那么该节点的失效将导致整体服务的临时性不可用&#xff0c;并且也可能会导致消息的丢失。可以将所有消息都设置为持久化&#xff0c;并且对应队列的durable 属性也设置为 true &#xff0c;但是这样仍然无法…

基于java swing和mysql实现的汽车租赁管理系统(源码+数据库+文档+运行指导视频)

一、项目简介 本项目是一套基于java swing和mysql实现的汽车租赁管理系统&#xff0c;主要针对计算机相关专业的正在做毕设的学生与需要项目实战练习的Java学习者。 包含&#xff1a;项目源码、项目文档、数据库脚本等&#xff0c;该项目附带全部源码可作为毕设使用。 项目都经…

计算机竞赛 基于YOLO实现的口罩佩戴检测 - python opemcv 深度学习

文章目录 0 前言1 课题介绍2 算法原理2.1 算法简介2.2 网络架构 3 关键代码4 数据集4.1 安装4.2 打开4.3 选择yolo标注格式4.4 打标签4.5 保存 5 训练6 实现效果6.1 pyqt实现简单GUI6.3 视频识别效果6.4 摄像头实时识别 7 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xf…

打架斗殴监测识别算法 yolov8

打架斗殴监测识别算法采用yolov8先进的图像处理和机器学习算法框架模型&#xff0c;打架斗殴监测识别算法能够自动识别和分析出打架斗殴的行为特征。一旦系统检测到打架斗殴行为&#xff0c;将自动触发告警。YOLO的结构非常简单&#xff0c;就是单纯的卷积、池化最后加了两层全…

抢先体验|乐鑫推出 ESP32-S3-BOX-3 新一代开源 AIoT 开发套件

乐鑫科技 (688018.SH) 非常高兴地宣布其开发套件阵容的最新成员 ESP32-S3-BOX-3。这款完全开源的 AIoT 应用开发套件搭载乐鑫高性能 ESP32-S3 AI SoC&#xff0c;旨在突破传统开发板&#xff0c;成为新一代开发工具的引领者。 【乐鑫新品抢先体验】ESP32-S3-BOX-3 新一代开源 A…

文件上传漏洞之条件竞争

这里拿upload-labs的第18关做演示 首先先看代码 $is_upload false; $msg null;if(isset($_POST[submit])){$ext_arr array(jpg,png,gif);$file_name $_FILES[upload_file][name];$temp_file $_FILES[upload_file][tmp_name];$file_ext substr($file_name,strrpos($file_…

AES+base64+远程加载----ConsoleApplication811项目

ConsoleApplication9.cpp // ConsoleApplication9.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 //#include <iostream> #include <Windows.h> #include <wininet.h> #include "base64.h" #include "AES.h" …

【Rust】Rust学习 第十九章高级特征

现在我们已经学习了 Rust 编程语言中最常用的部分。在第二十章开始另一个新项目之前&#xff0c;让我们聊聊一些总有一天你会遇上的部分内容。你可以将本章作为不经意间遇到未知的内容时的参考。本章将要学习的功能在一些非常特定的场景下很有用处。虽然很少会碰到它们&#xf…