每日一练: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 中,变量是一种用来存储数据值的标识符。创建变量很简单,

poj2406(连续重复子串)

题意:判断串s是不是str^n,求str的最大长度。 解题思路:kmp可解,后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后,自动跳转到next[i],所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下; #include<iostream>#include<algorithm>#include<stdio.h>#include<math.

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (

pip-tools:打造可重复、可控的 Python 开发环境,解决依赖关系,让代码更稳定

在 Python 开发中,管理依赖关系是一项繁琐且容易出错的任务。手动更新依赖版本、处理冲突、确保一致性等等,都可能让开发者感到头疼。而 pip-tools 为开发者提供了一套稳定可靠的解决方案。 什么是 pip-tools? pip-tools 是一组命令行工具,旨在简化 Python 依赖关系的管理,确保项目环境的稳定性和可重复性。它主要包含两个核心工具:pip-compile 和 pip

POJ1631最长单调递增子序列

最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

动手学深度学习【数据操作+数据预处理】

import osos.makedirs(os.path.join('.', 'data'), exist_ok=True)data_file = os.path.join('.', 'data', 'house_tiny.csv')with open(data_file, 'w') as f:f.write('NumRooms,Alley,Price\n') # 列名f.write('NA

线程的四种操作

所属专栏:Java学习        1. 线程的开启 start和run的区别: run:描述了线程要执行的任务,也可以称为线程的入口 start:调用系统函数,真正的在系统内核中创建线程(创建PCB,加入到链表中),此处的start会根据不同的系统,分别调用不同的api,创建好之后的线程,再单独去执行run(所以说,start的本质是调用系统api,系统的api