每日一练:LeeCode-316. 去除重复字母【字符串操作+单调栈+布尔型变量】

本文主要是介绍每日一练:LeeCode-316. 去除重复字母【字符串操作+单调栈+布尔型变量】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本文是力扣LeeCode-316. 去除重复字母 学习与理解过程,本文仅做学习之用,对本题感兴趣的小伙伴可以出门左拐LeeCode。

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

示例 1:
输入:s = “bcabc”
输出:“abc”

示例 2:
输入:s = “cbacdcbc”
输出:“acdb”

提示:
1 <= s.length <= 104
s 由小写英文字母组成

注意:该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters 相同

思路

初做这道题,我一下子就想到了之前有做过 1047. 删除字符串中的所有相邻重复项 题,使用栈方法移除相同项,这道题显然也可以这样做一部分,但是由于这道题要求有三个:

  • 去重
  • 去重字符串中的字符顺序不能打乱 s 中字符出现的相对顺序
  • 字典序最小

笔者这边做完去重和不打乱字符出现的相对顺序后,发现对这道题的要求3束手无策了。于是参考了LeeCode博主labuladong,对这道题的题解,我才发现还可以遇山开山,遇河架桥,666。下面是,我对博主题解的简述和总结:

要求1和2可以直接用如下代码解决

String removeDuplicateLetters(String s) {// 存放去重的结果Stack<Character> stack= new Stack<>();// 布尔数组初始值为 false,记录栈中是否存在某个字符// 输入字符均为 ASCII 字符,所以大小 256 够用了boolean[] inStack = new boolean[256];for (char c : s.toCharArray()) {// 如果字符 c 存在栈中,直接跳过if (inStack[c]) continue;// 若不存在,则插入栈顶并标记为存在stack.push(c);inStack[c] = true;}StringBuilder sb = new StringBuilder();while (!stack.empty()) {sb.append(stack.pop());}// 栈中元素插入顺序是反的,需要 reverse 一下return sb.reverse().toString();
}

bcabc举例,这个算法会返回 “bca”,已经符合要求1和要求2,但是题目希望要的答案是 “abc” 。所以此时需要考虑要求3,如何让字典项最小:以a、b、c、……举例,c的ASCII值大于b,b的ASCII值大于a,如果b比a先进栈,就需要先将b出栈pop,a才可以进栈排前面,如果c比b先进栈,就需要先将c出栈pop,b才可以进栈排前面…… 是否很像单调栈的原理

String removeDuplicateLetters(String s) {Stack<Character> stack= new Stack<>();boolean[] inStack = new boolean[256];for (char c : s.toCharArray()) {if (inStack[c]) continue;// 插入之前,和之前的元素比较一下大小// 如果字典序比前面的小,pop 前面的元素while (!stack.isEmpty() && stack.peek() > c) {// 弹出栈顶元素,并把该元素标记为不在栈中inStack[stack.pop()] = false;}stack.push(c);inStack[c] = true;}StringBuilder sb = new StringBuilder();while (!stack.empty()) {sb.append(stack.pop());}return sb.reverse().toString();
}

对于以上代码,我们输入 s = "bcabc",我们可以得出正确结果 "abc" 了,但是对于s="bcac",结果是ac,结果是不对的。究其根本,在于我们一杆子打死了所有stack.peek() > c 的情况。以 s = "bcac"为例,我们没有考虑到,将b出栈后,后续字符串中有没有b了,c是没问题的,它后面还有,所以,我们需要分情况讨论

  • 如果 stk.peek() 这个字符之后还会出现,那么可以把它 pop 出去,后面再 push 到栈里即可
  • 如果 stk.peek() 这个字符之后不会出现了,那么就不能把它 pop 出去,否则无法在后面找它了

该怎么实现这个效果呢? 计数器统计

最终代码实现

class Solution {public String removeDuplicateLetters(String s) {Stack<Character> stack = new Stack<>();boolean[] inStack = new boolean[256];// 维护一个计数器记录字符串中字符的数量// 因为输入为 ASCII 字符,大小 256 够int[] count = new int[256];for(char a : s.toCharArray()){count[a]++;}for(char c : s.toCharArray()){count[c]--;	// 每遍历过一个字符,都将对应的计数减一if(inStack[c])continue;while(!stack.isEmpty()&&stack.peek()>c){// 如果之后不存在栈顶元素了,则停止 popif(count[stack.peek()]==0)break;// 如果之后还有,则可以大胆 popinStack[stack.pop()] = false;}stack.push(c);inStack[c] = true;}StringBuilder sb = new StringBuilder();while(!stack.isEmpty()){sb.append(stack.pop());}return sb.reverse().toString();                }
}

时间复杂度: O(N)
空间复杂度: O(N)

大佬们有更好的方法,请不吝赐教,谢谢。

这篇关于每日一练:LeeCode-316. 去除重复字母【字符串操作+单调栈+布尔型变量】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/572176

相关文章

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函

Java操作Word文档的全面指南

《Java操作Word文档的全面指南》在Java开发中,操作Word文档是常见的业务需求,广泛应用于合同生成、报表输出、通知发布、法律文书生成、病历模板填写等场景,本文将全面介绍Java操作Word文... 目录简介段落页头与页脚页码表格图片批注文本框目录图表简介Word编程最重要的类是org.apach

MySQL中查找重复值的实现

《MySQL中查找重复值的实现》查找重复值是一项常见需求,比如在数据清理、数据分析、数据质量检查等场景下,我们常常需要找出表中某列或多列的重复值,具有一定的参考价值,感兴趣的可以了解一下... 目录技术背景实现步骤方法一:使用GROUP BY和HAVING子句方法二:仅返回重复值方法三:返回完整记录方法四:

Python实现对阿里云OSS对象存储的操作详解

《Python实现对阿里云OSS对象存储的操作详解》这篇文章主要为大家详细介绍了Python实现对阿里云OSS对象存储的操作相关知识,包括连接,上传,下载,列举等功能,感兴趣的小伙伴可以了解下... 目录一、直接使用代码二、详细使用1. 环境准备2. 初始化配置3. bucket配置创建4. 文件上传到os

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

mysql表操作与查询功能详解

《mysql表操作与查询功能详解》本文系统讲解MySQL表操作与查询,涵盖创建、修改、复制表语法,基本查询结构及WHERE、GROUPBY等子句,本文结合实例代码给大家介绍的非常详细,感兴趣的朋友跟随... 目录01.表的操作1.1表操作概览1.2创建表1.3修改表1.4复制表02.基本查询操作2.1 SE

MySQL 获取字符串长度及注意事项

《MySQL获取字符串长度及注意事项》本文通过实例代码给大家介绍MySQL获取字符串长度及注意事项,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 获取字符串长度详解 核心长度函数对比⚠️ 六大关键注意事项1. 字符编码决定字节长度2

c++中的set容器介绍及操作大全

《c++中的set容器介绍及操作大全》:本文主要介绍c++中的set容器介绍及操作大全,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录​​一、核心特性​​️ ​​二、基本操作​​​​1. 初始化与赋值​​​​2. 增删查操作​​​​3. 遍历方

MySQL追踪数据库表更新操作来源的全面指南

《MySQL追踪数据库表更新操作来源的全面指南》本文将以一个具体问题为例,如何监测哪个IP来源对数据库表statistics_test进行了UPDATE操作,文内探讨了多种方法,并提供了详细的代码... 目录引言1. 为什么需要监控数据库更新操作2. 方法1:启用数据库审计日志(1)mysql/mariad

springboot如何通过http动态操作xxl-job任务

《springboot如何通过http动态操作xxl-job任务》:本文主要介绍springboot如何通过http动态操作xxl-job任务的问题,具有很好的参考价值,希望对大家有所帮助,如有错... 目录springboot通过http动态操作xxl-job任务一、maven依赖二、配置文件三、xxl-