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

去除重复字母(力扣)贪心 + 队列 JAVA

给你一个字符串 s ,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证 返回结果的字典序最小(要求不能打乱其他字符的相对位置)。

示例 1:

输入:s = “bcabc”
输出:“abc”

示例 2:

输入:s = “cbacdcbc”
输出:“acdb”

提示:

1 <= s.length <= 10^4
s 由小写英文字母组成

解题思路:

1、大于O(n ^ 2)时间复杂度的算法会超时

2、由于要输出字典序最小的排列,所以字典序越小的字符就我设法让其排在前面,这就是贪心思维

3、需要栈辅助,即栈顶元素比添加进来的元素大,那么设法消掉此栈顶元素

4、需要index数组保留字符最后一次出现的位置,以便删掉栈顶元素使用

5、需要boolean类型数组判断新添元素是否在栈内存在

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

代码:

class Solution {public String removeDuplicateLetters(String s) {char a[] = s.toCharArray();int len = a.length;int index[] = new int [26]; for(int i = 0; i < len; i ++) index[a[i] - 'a'] = i;//记录每个字母最后出现的位置;boolean check[] = new boolean [26];Deque<Character> stack = new ArrayDeque<>();for(int i = 0; i < len; i ++) {if(!check[a[i] - 'a']) {//如果栈内没有,就选择添加while(!stack.isEmpty() && stack.peekLast() > a[i] && index[stack.peekLast() - 'a'] > i) {//如果添加的元素比栈顶小char c = stack.removeLast();check[c - 'a'] = false;}stack.add(a[i]);check[a[i] - 'a'] = true;}}StringBuffer s1 = new StringBuffer();for(char d : stack) s1.append(d);return s1.toString();}
}

在这里插入图片描述

相关文章:

去除重复字母(力扣)贪心 + 队列 JAVA

给你一个字符串 s &#xff0c;请你去除字符串中重复的字母&#xff0c;使得每个字母只出现一次。需保证 返回结果的字典序最小&#xff08;要求不能打乱其他字符的相对位置&#xff09;。 示例 1&#xff1a; 输入&#xff1a;s “bcabc” 输出&#xff1a;“abc” 示例 2&am…...

Spring,SpringBoot,Spring MVC的区别是什么

1.Spring是什么 我们通常所说的 Spring 指的是 Spring Framework&#xff08;Spring 框架&#xff09;&#xff0c;它是⼀个开源框架&#xff0c;有着活跃⽽庞⼤的社区&#xff0c;这就是它之所以能⻓久不衰的原因。Spring ⽀持⼴泛的应⽤场景&#xff0c;它可以让 Java 企业级…...

在CSDN学Golang云原生(Docker镜像)

一&#xff0c;镜像分层机制 在 Docker 中&#xff0c;一个镜像可以由多个分层&#xff08;Layer&#xff09;组成。每个分层都表示一些修改或添加到上一个分层的文件系统差异。 Golang 在构建 Docker 镜像时也支持类似的机制&#xff0c;通过 docker build 命令来创建一个包…...

Hive窗口函数大全

Hive窗口函数 一、偏移量函数laglead 二、窗口分析函数first_valuelast_value 三、排序函数rankdense_rankrow_number 一、偏移量函数 lag 语法&#xff1a;lag(col,n,default_val) 返回值&#xff1a;字段类型 说明&#xff1a;往前第n行数据。 lag(column字段&#xff0c;第…...

达闼面试(部分)(未完全解析)

grpc怎么解决负载均衡问题? Answer by newBing : gRPC提供了多种负载均衡策略&#xff0c;包括轮询、随机、最少连接数等。gRPC客户端可以使用这些策略来选择要连接的服务器。 k8s环境下部署grpc的几种方案 : 在k8s环境中&#xff0c;可以选择headless service&#xff0c;或者…...

Makefile常用函数

目录 字符串替换函数&#xff1a;subst 模式字符串替换函数&#xff1a;patsubst 去空格函数 strip 查找字符串函数 findstring 过滤函数 filter 反过滤函数 filter-out 排序函数 sort 取目录函数 dir 取文件函数 notdir 取后缀函数 suffix 取前缀函数 basename 加…...

mysql的一些知识整理

这里整理一些mysql相关的知识点&#xff0c;是自己不太熟悉的内容 varchar(n) 中 n 最大取值为多少 MySQL 规定除了 TEXT、BLOBs 这种大对象类型之外&#xff0c;其他所有的列&#xff08;不包括隐藏列和记录头信息&#xff09;占用的字节长度加起来不能超过 65535 个字节。 …...

修改密码和再次确认密码的js和element-ui的使用

<template><div><!-- plan的插槽 --><plan title"修改密码"><!-- 插槽的名字 --><span slot"header">修改密码</span><el-form:model"ruleForm2"status-icon:rules"rules2"ref"rul…...

蓝桥杯专题-真题版含答案-【垒骰子_动态规划】【抽签】【平方怪圈】【凑算式】

点击跳转专栏>Unity3D特效百例点击跳转专栏>案例项目实战源码点击跳转专栏>游戏脚本-辅助自动化点击跳转专栏>Android控件全解手册点击跳转专栏>Scratch编程案例点击跳转>软考全系列点击跳转>蓝桥系列 &#x1f449;关于作者 专注于Android/Unity和各种游…...

kubernetes调试利器——kubectl debug工具

通常情况下&#xff0c;业务容器所使用的镜像是非常精简的&#xff0c;而一旦业务容器出现问题&#xff0c;通过kubectl exec进入到容器时&#xff0c;我们会发现自己需要使用的工具都没有&#xff0c;也无法通过apt, apt-get, yum等包管理工具下载需要的工具。 想要解决这个尴…...

浅谈es5如何保证并发请求的返回顺序

最近在公司实习写的是es5&#xff0c;在和回调地狱经过一番拉扯之后写下这篇文章&#xff0c;也算是体验了一把没有promise的时代 假设我们的div有一个日历列表&#xff0c;但是由于大小关系只能每次显示2天的信息&#xff0c;项目限制只能使用es5&#xff0c;不能使用es6的pro…...

深入浅出Pytorch函数——torch.squeeze

分类目录&#xff1a;《深入浅出Pytorch函数》总目录 相关文章&#xff1a; 深入浅出Pytorch函数——torch.squeeze 深入浅出Pytorch函数——torch.unsqueeze 将输入张量形状为1的维度去除并返回。比如输入向量的形状为 A 1 B 1 C 1 D A\times1\times B\times1\times C…...

【LeetCode】121.买卖股票的最佳时机

题目 给定一个数组 prices &#xff0c;它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票&#xff0c;并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大…...

【力扣】74. 搜索二维矩阵 <二分法>

【力扣】74. 搜索二维矩阵 给你一个满足下述两条属性的 m x n 整数矩阵&#xff1a; 每行中的整数从左到右按非递减顺序排列。每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target &#xff0c;如果 target 在矩阵中&#xff0c;返回 true &#xff1b;否则&am…...

Spring Task+Cron表达式

不需要导入坐标spring-context&#xff08;包含在了spring-boot-starter&#xff09; 在启动类添加EnableScheduleing开启任务调度 单独建个定时任务包task&#xff0c;创建定时任务类MyTask 在定时任务类添加Component 在类的方法上添加Scheduled&#xff08;cron “cron表达…...

你们公司的【前端项目】是如何做测试的?字节10年测试经验的我这样做的...

前端项目也叫web端项目&#xff08;通俗讲就是网页上的功能&#xff09;是我们能够在屏幕上看到并产生交互的体验。 前端项目如何做测试&#xff1f; 要讲清楚这个问题&#xff0c;先需要你对测试流程现有一个全局的了解&#xff0c;先上一张测试流程图&#xff1a; 测试流程…...

华为战略方法论:BLM模型之关键任务与依赖关系

内容简介 在 BLM 模型中&#xff0c;执行部分包括四个模块&#xff0c;分别是&#xff1a; 关键任务与依赖关系&#xff1b;组织与绩效&#xff1b;人才&#xff1b;氛围与文化。 详细内容&#xff0c;大家可以参看下面这张图。 这四个模块其实是可以进一步划分成两个关键点…...

django的ORM模板的fake更新

django存量数据表的migraions记录丢失&#xff0c;若要更新表结构&#xff0c;则需用到fake&#xff0c;否则报错&#xff1a; 解决步骤如下&#xff1a; 1&#xff09;同步存量表结构&#xff0c;生成伪表 --fake sudo python3 manage.py makemigrations appname sudo pyt…...

239.滑动窗口最大值

leetcode原题链接 题目描述&#xff1a; 给你一个整数数组 nums&#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 示例1: 输入&#xff1a;nums [1,…...

Redis基础原理

1 概念 1.1 关系型数据库与非关系型数据库对比 关系型数据库Mysql、Oralce特点数据之间有关联&#xff1b;数据存储在硬盘上效率操作关系型数据库非常耗时 非关系型数据库redis、hbase存储key:value特点数据之间没有关联关系&#xff1b;数据存储在内存中缓存思想从缓存中获…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...