去除重复字母(力扣)贪心 + 队列 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 ,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证 返回结果的字典序最小(要求不能打乱其他字符的相对位置)。 示例 1: 输入:s “bcabc” 输出:“abc” 示例 2&am…...
Spring,SpringBoot,Spring MVC的区别是什么
1.Spring是什么 我们通常所说的 Spring 指的是 Spring Framework(Spring 框架),它是⼀个开源框架,有着活跃⽽庞⼤的社区,这就是它之所以能⻓久不衰的原因。Spring ⽀持⼴泛的应⽤场景,它可以让 Java 企业级…...
在CSDN学Golang云原生(Docker镜像)
一,镜像分层机制 在 Docker 中,一个镜像可以由多个分层(Layer)组成。每个分层都表示一些修改或添加到上一个分层的文件系统差异。 Golang 在构建 Docker 镜像时也支持类似的机制,通过 docker build 命令来创建一个包…...
Hive窗口函数大全
Hive窗口函数 一、偏移量函数laglead 二、窗口分析函数first_valuelast_value 三、排序函数rankdense_rankrow_number 一、偏移量函数 lag 语法:lag(col,n,default_val) 返回值:字段类型 说明:往前第n行数据。 lag(column字段,第…...
达闼面试(部分)(未完全解析)
grpc怎么解决负载均衡问题? Answer by newBing : gRPC提供了多种负载均衡策略,包括轮询、随机、最少连接数等。gRPC客户端可以使用这些策略来选择要连接的服务器。 k8s环境下部署grpc的几种方案 : 在k8s环境中,可以选择headless service,或者…...
Makefile常用函数
目录 字符串替换函数:subst 模式字符串替换函数:patsubst 去空格函数 strip 查找字符串函数 findstring 过滤函数 filter 反过滤函数 filter-out 排序函数 sort 取目录函数 dir 取文件函数 notdir 取后缀函数 suffix 取前缀函数 basename 加…...
mysql的一些知识整理
这里整理一些mysql相关的知识点,是自己不太熟悉的内容 varchar(n) 中 n 最大取值为多少 MySQL 规定除了 TEXT、BLOBs 这种大对象类型之外,其他所有的列(不包括隐藏列和记录头信息)占用的字节长度加起来不能超过 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编程案例点击跳转>软考全系列点击跳转>蓝桥系列 👉关于作者 专注于Android/Unity和各种游…...
kubernetes调试利器——kubectl debug工具
通常情况下,业务容器所使用的镜像是非常精简的,而一旦业务容器出现问题,通过kubectl exec进入到容器时,我们会发现自己需要使用的工具都没有,也无法通过apt, apt-get, yum等包管理工具下载需要的工具。 想要解决这个尴…...
浅谈es5如何保证并发请求的返回顺序
最近在公司实习写的是es5,在和回调地狱经过一番拉扯之后写下这篇文章,也算是体验了一把没有promise的时代 假设我们的div有一个日历列表,但是由于大小关系只能每次显示2天的信息,项目限制只能使用es5,不能使用es6的pro…...
深入浅出Pytorch函数——torch.squeeze
分类目录:《深入浅出Pytorch函数》总目录 相关文章: 深入浅出Pytorch函数——torch.squeeze 深入浅出Pytorch函数——torch.unsqueeze 将输入张量形状为1的维度去除并返回。比如输入向量的形状为 A 1 B 1 C 1 D A\times1\times B\times1\times C…...
【LeetCode】121.买卖股票的最佳时机
题目 给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大…...
【力扣】74. 搜索二维矩阵 <二分法>
【力扣】74. 搜索二维矩阵 给你一个满足下述两条属性的 m x n 整数矩阵: 每行中的整数从左到右按非递减顺序排列。每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则&am…...
Spring Task+Cron表达式
不需要导入坐标spring-context(包含在了spring-boot-starter) 在启动类添加EnableScheduleing开启任务调度 单独建个定时任务包task,创建定时任务类MyTask 在定时任务类添加Component 在类的方法上添加Scheduled(cron “cron表达…...
你们公司的【前端项目】是如何做测试的?字节10年测试经验的我这样做的...
前端项目也叫web端项目(通俗讲就是网页上的功能)是我们能够在屏幕上看到并产生交互的体验。 前端项目如何做测试? 要讲清楚这个问题,先需要你对测试流程现有一个全局的了解,先上一张测试流程图: 测试流程…...
华为战略方法论:BLM模型之关键任务与依赖关系
内容简介 在 BLM 模型中,执行部分包括四个模块,分别是: 关键任务与依赖关系;组织与绩效;人才;氛围与文化。 详细内容,大家可以参看下面这张图。 这四个模块其实是可以进一步划分成两个关键点…...
django的ORM模板的fake更新
django存量数据表的migraions记录丢失,若要更新表结构,则需用到fake,否则报错: 解决步骤如下: 1)同步存量表结构,生成伪表 --fake sudo python3 manage.py makemigrations appname sudo pyt…...
239.滑动窗口最大值
leetcode原题链接 题目描述: 给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 示例1: 输入:nums [1,…...
Redis基础原理
1 概念 1.1 关系型数据库与非关系型数据库对比 关系型数据库Mysql、Oralce特点数据之间有关联;数据存储在硬盘上效率操作关系型数据库非常耗时 非关系型数据库redis、hbase存储key:value特点数据之间没有关联关系;数据存储在内存中缓存思想从缓存中获…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...
技术栈RabbitMq的介绍和使用
目录 1. 什么是消息队列?2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...
PostgreSQL——环境搭建
一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在࿰…...
elementUI点击浏览table所选行数据查看文档
项目场景: table按照要求特定的数据变成按钮可以点击 解决方案: <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...
