每日一练: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

相关文章

MySQL字符串常用函数详解

《MySQL字符串常用函数详解》本文给大家介绍MySQL字符串常用函数,本文结合实例代码给大家介绍的非常详细,对大家学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql字符串常用函数一、获取二、大小写转换三、拼接四、截取五、比较、反转、替换六、去空白、填充MySQL字符串常用函数一、

Ubuntu 24.04启用root图形登录的操作流程

《Ubuntu24.04启用root图形登录的操作流程》Ubuntu默认禁用root账户的图形与SSH登录,这是为了安全,但在某些场景你可能需要直接用root登录GNOME桌面,本文以Ubuntu2... 目录一、前言二、准备工作三、设置 root 密码四、启用图形界面 root 登录1. 修改 GDM 配

Spring Boot中的路径变量示例详解

《SpringBoot中的路径变量示例详解》SpringBoot中PathVariable通过@PathVariable注解实现URL参数与方法参数绑定,支持多参数接收、类型转换、可选参数、默认值及... 目录一. 基本用法与参数映射1.路径定义2.参数绑定&nhttp://www.chinasem.cnbs

nginx 负载均衡配置及如何解决重复登录问题

《nginx负载均衡配置及如何解决重复登录问题》文章详解Nginx源码安装与Docker部署,介绍四层/七层代理区别及负载均衡策略,通过ip_hash解决重复登录问题,对nginx负载均衡配置及如何... 目录一:源码安装:1.配置编译参数2.编译3.编译安装 二,四层代理和七层代理区别1.二者混合使用举例

JSONArray在Java中的应用操作实例

《JSONArray在Java中的应用操作实例》JSONArray是org.json库用于处理JSON数组的类,可将Java对象(Map/List)转换为JSON格式,提供增删改查等操作,适用于前后端... 目录1. jsONArray定义与功能1.1 JSONArray概念阐释1.1.1 什么是JSONA

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中,如果使用类成员变量时未给定其初始值,那么它将被

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