当前位置: 首页 > 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;数据存储在内存中缓存思想从缓存中获…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...