当前位置: 首页 > 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;所以部分用户需要将调度系统从…...

lvgl_v8之设置label背景颜色一种方式

void lv_label_demo() {static lv_style_t style;lv_style_init(&style);lv_style_set_radius...

Alexa Plus 拓展食品配送领域,语音订餐体验升级

Alexa Plus 开启食品配送新功能从本周起&#xff0c;Alexa Plus 拓展至食品配送领域&#xff0c;用户可通过它从优步外卖&#xff08;Uber Eats&#xff09;和 Grubhub 订餐。只需将优步或 Grubhub 应用与 Alexa Plus 设备关联&#xff0c;就能询问食品配送情况&#xff0c;并通…...

Qwen3.5-9B-AWQ-4bit Java开发环境快速配置:从安装到第一个AI程序

Qwen3.5-9B-AWQ-4bit Java开发环境快速配置&#xff1a;从安装到第一个AI程序 1. 准备工作&#xff1a;你需要什么 在开始之前&#xff0c;确保你的电脑满足以下基本要求&#xff1a; 操作系统&#xff1a;Windows 10/11、macOS 10.15 或主流Linux发行版内存&#xff1a;至少…...

Phi-3-mini-4k-instruct-gguf效果实测:单卡3090上并发3路问答的延迟与显存占用

Phi-3-mini-4k-instruct-gguf效果实测&#xff1a;单卡3090上并发3路问答的延迟与显存占用 1. 测试背景与模型介绍 Phi-3-mini-4k-instruct-gguf是微软Phi-3系列中的轻量级文本生成模型GGUF版本&#xff0c;专为问答、文本改写、摘要整理和简短创作等场景优化。作为一款开箱即…...

GLM-4.1V-9B-Base惊艳输出:支持追问式对话的图片理解连续推理演示

GLM-4.1V-9B-Base惊艳输出&#xff1a;支持追问式对话的图片理解连续推理演示 1. 视觉多模态模型新标杆 GLM-4.1V-9B-Base是智谱最新开源的视觉多模态理解模型&#xff0c;它重新定义了图片理解与交互的方式。不同于传统视觉模型只能做简单识别&#xff0c;这个9B参数的模型支…...

智能水印引擎:重新定义摄影后期效率标准

智能水印引擎&#xff1a;重新定义摄影后期效率标准 【免费下载链接】semi-utils 一个批量添加相机机型和拍摄参数的工具&#xff0c;后续「可能」添加其他功能。 项目地址: https://gitcode.com/gh_mirrors/se/semi-utils 问题发现&#xff1a;数字摄影时代的效率困境 …...

CasRel关系抽取完整流程:从原始文本清洗、NER预处理到SPO抽取

CasRel关系抽取完整流程&#xff1a;从原始文本清洗、NER预处理到SPO抽取 1. 什么是CasRel关系抽取&#xff1f; CasRel&#xff08;Cascade Binary Tagging Framework&#xff09;是一个专门从文本中自动提取"谁-做了什么-对谁"这种关系信息的AI模型。想象一下&am…...

设备独立滚动控制:让macOS输入设备各得其所的开源解决方案

设备独立滚动控制&#xff1a;让macOS输入设备各得其所的开源解决方案 【免费下载链接】Scroll-Reverser Per-device scrolling prefs on macOS. 项目地址: https://gitcode.com/gh_mirrors/sc/Scroll-Reverser 问题溯源&#xff1a;当滚动方向成为效率隐形杀手 在数字…...

忍者像素绘卷入门必看:Z-Image-Turbo与Stable Diffusion 16-Bit插件对比

忍者像素绘卷入门必看&#xff1a;Z-Image-Turbo与Stable Diffusion 16-Bit插件对比 1. 像素艺术创作新选择 在数字艺术创作领域&#xff0c;像素风格始终占据着独特地位。对于想要创作16-Bit复古游戏风格作品的艺术家来说&#xff0c;选择合适的工具至关重要。本文将对比分析…...

SDMatte模型推理加速:利用OpenCV和CUDA进行预处理优化

SDMatte模型推理加速&#xff1a;利用OpenCV和CUDA进行预处理优化 1. 为什么需要预处理加速 在图像处理的实际应用中&#xff0c;我们常常忽视一个关键环节&#xff1a;预处理。当把一张原始图片送入SDMatte这样的深度学习模型前&#xff0c;通常需要经过一系列转换操作——调…...