当前位置: 首页 > news >正文

面试算法37:小行星碰撞

题目

输入一个表示小行星的数组,数组中每个数字的绝对值表示小行星的大小,数字的正负号表示小行星运动的方向,正号表示向右飞行,负号表示向左飞行。如果两颗小行星相撞,那么体积较小的小行星将会爆炸最终消失,体积较大的小行星不受影响。如果相撞的两颗小行星大小相同,那么它们都会爆炸消失。飞行方向相同的小行星永远不会相撞。求最终剩下的小行星。例如,有6颗小行星[4,5,-6,4,8,-5],如图6.2所示(箭头表示飞行的方向),它们相撞之后最终剩下3颗小行星[-6,4,8]。
在这里插入图片描述

分析

下面以一个具体的例子来分析小行星碰撞的规律。先假设有6颗小行星[4,5,-6,4,8,-5],然后逐一分析它们的飞行情况。第1颗是向右飞行的大小为4的小行星。此时还不知道它会不会和其他小行星碰撞,可以先将它保存到某个数据容器中。第2颗还是一颗向右飞行的小行星,它的大小为5。它和前面一颗小行星的飞行方向相同,所以不会碰撞。但现在还不知道它会不会和后面的小行星碰撞,因此也将它保存到数据容器中。第3颗是一颗向左飞行的小行星,大小为6。由于它和前面两颗小行星是相向而行的,因此会和前面两颗小行星相撞。由于大小为5的小行星离它更近,因此这两颗小行星将会先相撞。先后向数据容器中保存了大小为4、5的两颗小行星,后保存到数据容器中的小行星先和其他的小行星相撞。

根据题目的碰撞规则,小的小行星将会爆炸消失,因此当大小分别为5和6的两颗小行星相撞时,大小为5的小行星会爆炸消失。大小为6的小行星继续向左飞行,它将和大小为4的小行星相撞。大小为4的小行星爆炸消失,留下大小为6的小行星向左飞行。此时左边已经没有更多的小行星和这颗大小为6的小行星相撞,将它入栈。

接下来是两颗向右飞行的小行星,大小分别为4和8,它们和大小为6的小行星背向飞行,肯定不会相撞,因此将它们也先后入栈。最后是一颗大小为5向左飞行的小行星。此时栈中保存了3颗小行星[-6,4,8],大小为8的小行星离它最近而且相向飞行,因此它将与大小为8的小行星相撞,然后爆炸消失。最终剩下3颗小行星[-6,4,8]。

public class Test {public static void main(String[] args) {int[] tokens = {4, 5, -6, 4, 8, -5};int[] result = asteroidCollision(tokens);for (int res : result) {System.out.println(res);}}public static int[] asteroidCollision(int[] asteroids) {Stack<Integer> stack = new Stack<>();for (int as : asteroids) {while (!stack.empty() && stack.peek() > 0 && stack.peek() < -as) {// 为什么while循环,是因为as没有被撞碎,接着撞stack.pop();}if (!stack.empty() && stack.peek() > 0 && stack.peek() == -as) {// 为什么没有while循环,是因为as被撞碎了stack.pop();}else if (as > 0 || stack.empty() || stack.peek() < 0) {stack.push(as);}// 如果不符合上述情况,则这里表示as被撞碎了,继续分析下一颗行星}return stack.stream().mapToInt(i -> i).toArray();}
}

相关文章:

面试算法37:小行星碰撞

题目 输入一个表示小行星的数组&#xff0c;数组中每个数字的绝对值表示小行星的大小&#xff0c;数字的正负号表示小行星运动的方向&#xff0c;正号表示向右飞行&#xff0c;负号表示向左飞行。如果两颗小行星相撞&#xff0c;那么体积较小的小行星将会爆炸最终消失&#xf…...

ROS学习记录2018.7.10

ROS学习记录2018.7.10 1.ROS基础了解 开源机器人操作系统ROS&#xff08;robot operation system&#xff09; 分级&#xff1a; 1.计算图集&#xff08;一种网络结构&#xff09; 1.节点&#xff1a;执行运算的进程&#xff08;做基础处理的单元&#xff09;2.消息&#x…...

OPC UA:工业领域的“HTML”

OPC UA是工业自动化领域的一项重要的通信协议。它的特点是包括了信息模型构建方法。能够建立工业领域各种事物的信息模型。在工业自动化行业&#xff0c;OPCUA 类似互联网行业的HTTP协议和“HTML”语言。能够准确&#xff0c;可靠地描述复杂系统中各个元素&#xff0c;并且实现…...

【golang】Windows环境下Gin框架安装和配置

Windows环境下Gin框架安装和配置 我终于搞定了Gin框架的安装&#xff0c;花了两三个小时&#xff0c;只能说道阻且长&#xff0c;所以写下这篇记录文章 先需要修改一些变量&#xff0c;这就需要打开终端&#xff0c;为了一次奏效&#xff0c;我们直接设置全局的&#xff1a; …...

多测师肖sir_高级金牌讲师__接口测试之tonken (5.6)

接口测试之tonken 网站&#xff1a;http://shop.duoceshi.com/login?redirect2Fdashboard 第一个接口&#xff1a;uiid接口 uiid接口url&#xff1a;http://manage.duoceshi.com/auth/code test中语句&#xff1a; var jsonData JSON.parse(responseBody); postman.setEnvi…...

C++常见面试问题之内存对齐

一、内存对齐是什么 1.内存对齐是什么 还是用一个例子带出这个问题&#xff0c;看下面的小程序&#xff0c;理论上&#xff0c;32位系统下&#xff0c;int占4byte&#xff0c;char占一个byte&#xff0c;那么将它们放到一个结构体中应该占415byte&#xff1b;但是实际上&…...

网络协议--TCP:传输控制协议

17.1 引言 本章将介绍TCP为应用层提供的服务&#xff0c;以及TCP首部中的各个字段。随后的几章我们在了解TCP的工作过程中将对这些字段作详细介绍。 对TCP的介绍将由本章开始&#xff0c;并一直包括随后的7章。第18章描述如何建立和终止一个TCP连接&#xff0c;第19和第20章将…...

网络协议--BOOTP:引导程序协议

16.1 引言 在第5章我们介绍了一个无盘系统&#xff0c;它在不知道自身IP地址的情况下&#xff0c;在进行系统引导时能够通过RARP来获取它的IP地址。然而使用RARP有两个问题&#xff1a;&#xff08;1&#xff09;IP地址是返回的唯一结果&#xff1b;&#xff08;2&#xff09;…...

33基于MATLAB的对RGB图像实现中值滤波,均值滤波,维纳滤波。程序已通过调试,可直接运行。

基于MATLAB的对RGB图像实现中值滤波&#xff0c;均值滤波&#xff0c;维纳滤波。程序已通过调试&#xff0c;可直接运行。 33 MATLAB、图像处理、维纳滤波 (xiaohongshu.com)...

WPF十六(页面内嵌加载)

在WPF中进行页面内嵌的加载 当存在一定需求时&#xff0c;比如当前页面C左侧是一个A页面&#xff0c;右侧是一个B页面&#xff0c;A页面是一个公用页面时&#xff0c;此时只需要做内嵌A页面&#xff0c;然后B页面进行正常处理&#xff0c;既可以节省时间&#xff0c;又做到了WP…...

JAVA基础(JAVA SE)学习笔记(九)异常处理

前言 1. 学习视频&#xff1a; 尚硅谷Java零基础全套视频教程(宋红康2023版&#xff0c;java入门自学必备)_哔哩哔哩_bilibili 2023最新Java学习路线 - 哔哩哔哩 第三阶段&#xff1a;Java高级应用 9.异常处理 10.多线程 11.常用类和基础API 12.集合框架 13.泛型 14…...

Miniconda、Vscode下载和conda源、pip源设置

1、常用软件下载 1、Miniconda软件下载&#xff1a; windows网址&#xff1a;https://mirrors.tuna.tsinghua.edu.cn/anaconda/miniconda/?CS&OA 2、最新版Miniconda下载网址&#xff1a;https://docs.conda.io/projects/miniconda/en/latest/ 3、常用代码编辑器VsCode下…...

CAN接口的PCB Layout规则要求汇总

随着时代高速发展&#xff0c;控制器局域网&#xff08;CAN&#xff09;接口的应用越来越广泛&#xff0c;尤其是在汽车电子、航空航天等领域中发挥着重要作用&#xff0c;为了确保CAN接口的可靠性和稳定性&#xff0c;工程师必须在其PCB Layout方面下功夫&#xff0c;下面来看…...

IP网络矿用打点紧急广播方案

IP网络矿用打点紧急广播方案 一、概述 目前&#xff0c;随着计算机网络技术的迅速普及&#xff0c;信息化已经走向煤矿。很多煤矿都陆续具有了稳定可靠、覆盖矿井上下的工业以太网。科学技术的不断进步和信息化矿山建设步伐的不断加快&#xff0c;井下工业以太网将逐渐得到推…...

系列六、FactoryBean vs ApplicationContext

一、FactoryBean vs ApplicationContext 1.1、概述 BeanFactory是一个工厂类&#xff0c;负责生产和管理bean&#xff0c;在Spring中BeanFactory是IOC容器的核心接口&#xff0c;它的主要职责就是生产bean及建立各个bean之间的依赖。applicationContext是BeanFactory的一个子接…...

AOP简单使用模版

AOP面向切面编程 切面类的定义之模版 package com.xie.service;import org.aspectj.lang.JoinPoint; import org.aspectj.lang.annotation.*; import org.aspectj.lang.ProceedingJoinPoint; import org.springframework.stereotype.Component; import javax.servlet.http.Http…...

手机注册.

<!DOCTYPE html> <html><head><title>注册</title><meta http-equiv"content-type" content"text/html; charsetutf-8"/><meta name"apple-mobile-web-app-capable" content"yes"/><lin…...

PostgreSQL 17新特性之登录事件触发器

PostgreSQL 9.3 就提供了事件触发器功能&#xff0c;可以基于 DDL 语句触发相应的操作。 正在开发中的 PostgreSQL 17 增加了基于登录事件的触发器&#xff0c;可以在用户登录时执行某些检查或者特定操作。登录事件触发器的使用方法和其他触发器一样&#xff1a;创建一个返回 …...

Docker 搭建 LNMP + Wordpress

[TOC](Docker 搭建 LNMP Wordpress 一、项目介绍1.1、项目环境1.2、 服务器环境1.3、 任务需求 二、部署Nginx2.1、建立工作目录2.2、 编写 Dockerfile 脚本2.3、准备 nginx.conf 配置文件2.4、生成镜像2.5、创建自定义网络 三、部署Mysql3.1、建立工作目录3.2、编写 Dockerfi…...

大数据调度最佳实践 | 从Airflow迁移到Apache DolphinScheduler

迁移背景 有部分用户原来是使用 Airflow 作为调度系统的&#xff0c;但是由于 Airflow 只能通过代码来定义工作流&#xff0c;并且没有对资源、项目的粒度划分&#xff0c;导致在部分需要较强权限控制的场景下不能很好的贴合客户需求&#xff0c;所以部分用户需要将调度系统从…...

电弧现象解析与过零检测灭弧技术

1. 电弧现象的本质与危害解析1.1 电弧的物理本质电弧本质上是一种气体放电现象&#xff0c;当机械触点分离时&#xff0c;触点间的电子或离子在电场作用下游离到空气中形成导电通道。这个过程中&#xff0c;原本绝缘的空气被电离成为等离子体&#xff0c;维持了电流的持续流通。…...

游戏脚本助手,电脑点击器,脚本自动点击识图找图_无限试用版

熊猫精灵脚本助手 分类功能项其他功能管理、插件、生成、中控、进程守护、护盾配置、坐标工具脚本设置窗口设置、绑定设置、运行设置、变量设置、程序设置图色识别Yolo识别、找图识别、点色找色文字识别ocr识别找字、字库识别、验证码识别键鼠操作鼠标操作、键盘操作、录制脚本…...

构筑可信电子签名签章体系,亲笔签助力黔江区公立医院改革与高质量发展

巍巍武陵山&#xff0c;滔滔阿蓬江&#xff0c;在渝东南这片热土上&#xff0c;一个关乎50余万群众健康福祉的数字变革正在发生。2022年&#xff0c;黔江区成为首批入选公立医院改革与高质量发展示范项目全国15个试点地区之一。从“看病难、看病远”的山区困境&#xff0c;到“…...

Qwen3.5-9B-AWQ-4bit Visual Studio开发者的AI伙伴:C#与.NET项目集成

Qwen3.5-9B-AWQ-4bit Visual Studio开发者的AI伙伴&#xff1a;C#与.NET项目集成 1. 当AI大模型遇上.NET开发 想象一下这样的场景&#xff1a;你在Visual Studio中编写一个ASP.NET Core控制器时&#xff0c;突然卡在某个LINQ查询的实现上。这时&#xff0c;你的IDE不仅能提示…...

m3u8视频下载终极指南:轻松获取加密流媒体内容的完整解决方案

m3u8视频下载终极指南&#xff1a;轻松获取加密流媒体内容的完整解决方案 【免费下载链接】m3u8_downloader 项目地址: https://gitcode.com/gh_mirrors/m3/m3u8_downloader 还在为无法保存在线视频而烦恼吗&#xff1f;m3u8_downloader项目为你提供了简单快速的解决方…...

大模型面试必备:模型训练与微调 15 问全解析

导读&#xff1a;2026 年&#xff0c;大模型已从"尝鲜"走向"落地"。无论是求职面试还是项目实战&#xff0c;模型训练与微调都是绕不开的核心话题。本文基于面试辅导资料&#xff0c;结合行业最佳实践&#xff0c;梳理了 15 个关键知识点&#xff0c;助大家…...

MSF(etasploit Framework)工具使用与实战

MSF工具介绍工具简介全称Metasploit Framework&#xff0c;是漏洞研究、渗透测试、漏洞验证的一体化平台&#xff0c;主要有以下五大核心模块&#xff1a; Auxiliary&#xff08;辅助模块&#xff09;&#xff1a;漏洞扫描、信息收集、端口扫描、服务探测&#xff08;无攻击载荷…...

Netbird iOS客户端连接问题分析与解决方案

Netbird iOS客户端连接问题分析与解决方案 Netbird作为一款优秀的P2P网络工具&#xff0c;在跨平台使用中可能会遇到一些兼容性问题。近期iOS客户端出现的连接异常现象引起了开发者社区的关注。本文将深入分析该问题的技术背景&#xff0c;并提供有效的解决方案。 问题现象描述…...

Text-Grab:重新定义本地化OCR工具的高效办公体验

Text-Grab&#xff1a;重新定义本地化OCR工具的高效办公体验 【免费下载链接】Text-Grab Use OCR in Windows quickly and easily with Text Grab. With optional background process and notifications. 项目地址: https://gitcode.com/gh_mirrors/te/Text-Grab 在数字…...

解决数字阅读焦虑:用fanqienovel-downloader构建个人离线图书馆的创新方法

解决数字阅读焦虑&#xff1a;用fanqienovel-downloader构建个人离线图书馆的创新方法 【免费下载链接】fanqienovel-downloader 下载番茄小说 项目地址: https://gitcode.com/gh_mirrors/fa/fanqienovel-downloader 在数字阅读日益普及的今天&#xff0c;你是否曾遭遇过…...