首页 > 其他分享 >316. 去除重复字母

316. 去除重复字母

时间:2023-10-08 10:14:28浏览次数:40  
标签:弹栈 遍历 remains 字母 316 去除 ord 单调

链接

https://leetcode.cn/problems/remove-duplicate-letters/description/

思路

这个题并不是传统的单调栈,所以硬套单调栈会懵逼。

什么时候用单调栈? 这个题目要求去除重复字母,还要保持字典序。 注意,跟相对顺序相关的题目,如:其后比他大的第一个元素,其后比他小的第一个元素,再比如保持字典序的题目,都适合用单调栈。

应用单调栈我们要想清楚的核心问题是:

1. 什么情况下我们弹栈。

2. 栈内元素是(部分)升序还是(部分)降序

3. 我们应该从前往后遍历,还是从后往前遍历

在这个题目中,我们要的是保持字典序,即我们要的最后的序列是升序序列。所以我们解答了第二个核心问题,即我们要的是升序。

在这个题目中,还有个条件是让我们去除重复字母。我们要的是升序,所以可能要把比较大的字母弹栈。比较大的字母越早被弹栈,我们越能保持字典序。(举个例子,dabd,我们应该让第一个d弹栈),所以我们应该从前往后遍历。

在这个题目中,我们弹栈也有两种情况。 既然我们要保持字典序,那应该栈顶元素大于待入栈元素时弹栈,但并不是每次都这样操作。因为如果栈顶元素没有出现在剩余的未遍历序列中,我们就不能再弹了,再弹我们就漏字母了,所以这里要加一个判断。

代码

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        # visited为True表示该字母已经加入单调栈中了
        visited = [False for i in range(26)]
        # remains代表当前未遍历到的字母的计数(<=0代表未遍历到的序列中没有这个字母了)
        remains = [0 for i in range(26)]
        single_stack = []
        # 初始化remains
        for i in s:
            idx = ord(i) - ord('a')
            remains[idx] += 1
        for i in s:
            if not visited[ord(i)-ord('a')]:
                # 如果这个字符没有加入到单调栈中
                while single_stack and ord(single_stack[-1]) > ord(i):
                    idx = ord(single_stack[-1])-ord('a')
                    if remains[idx] > 0:
                        # 还有剩余的大字符, 影响字典序,弹栈并且重置加入单调栈的状态
                        visited[idx] = False
                        single_stack.pop()
                    # 必须要有else, 否则remains[idx]没有剩余数值时,单调栈不弹栈, 会陷入死循环
                    else:
                        break
                # 别管有没有弹栈, 当前字母都得入栈, 跟其他单调栈的题目没啥区别
                single_stack.append(i)
                # 入单调栈了, 自然是要更新visited记录
                visited[ord(i) - ord('a')] = True
            # remains是剩余序列的计数, 已经遍历过当前字母了, 所以要减1
            remains[ord(i)-ord('a')] -= 1
        return ''.join(single_stack)

 

标签:弹栈,遍历,remains,字母,316,去除,ord,单调
From: https://www.cnblogs.com/bjfu-vth/p/17748211.html

相关文章

  • 背单词 首字母 2023年10月
    2023-10-07tspusmspgotedpttar,slay,pilgrim,utmost,satirical,misapprehension,scorn,paddle,groom,occasion,tuberculosis,exclamation,drum,pager,turnip2023-10-06cscaffhdphsciamcircus,syndrome,claw,administrate,foam,fretful,harry,drugstore,pe......
  • 20211316郭佳昊 《信息安全系统设计与实现(上)》第四周学习笔记
    一、任务要求[1]知识点归纳以及自己最有收获的内容,选择至少2个知识点利用chatgpt等工具进行苏格拉底挑战,并提交过程截图,提示过程参考下面内容(4分)我在学***X知识点,请你以苏格拉底的方式对我进行提问,一次一个问题核心是要求GPT:请你以苏格拉底的方式对我进行提问然后GPT就会......
  • NOJ[1143] 字母转换
    描述:通过栈交换字母顺序。给定两个字符串,要求所有的进栈和出栈序列(i表示进栈,o表示出栈),使得字符串2在求得的进出栈序列的操作下,变成字符串1。输出结果需满足字典序。例如TROT到TORT:[iiiiooooioiiooio]输入:给定两个字符串,第一个字符串是源字符串,第二个字符......
  • 案例6:输入一个小写字母,然后输出一个大写字母
    本题主要是考察大小写字母的转换,大写字母A~Z的ascii码分别是65~90,小写字母a~z的ascii码分别是97~122,它们之间的差值是32。比如小写字母a的ascill码的值97,减去大写字母A的ascii的值65,结果为32。示例代码如下:#define_CRT_SECURE_NO_WARNINGS1#include<stdio.h>voidmain(){......
  • 免费ChatGPT使用,免费一键去除视频水印,有这免费的app就够用了
    ​大家好,我是小凉席,这款APP是我在大学期间试着做着玩的一款工具合集APP本来是想做着玩的,可是越做用户越多,直到现在群里那么多朋友支持,又给了我很大的动力来更新这款app从这款APP诞生到现在已经有两年时间了,一直秉持这  免费,无收费软件内工具有:视频去水印,图集去水印,视频转图片......
  • 随想录Day5|242. 有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和
    随想录Day5|242.有效的字母异位词、349.两个数组的交集、202.快乐数、1.两数之和 242.有效的字母异位词文章&视频讲解给定两个字符串s和t,编写一个函数来判断t是否是s的字母异位词。注意:若s和t中每个字符出现的次数都相同,则称s和t互为字母异位词。1......
  • python去除某列固定数字对应的整行方法
     想去除month列里的1,2,3,4,10,11,12月对应的行留下5,6,7,8,9月#!usr/bin/envpython#-*-coding:utf-8-*-"""@author:Su@file:deletestaion.py@time:2023/09/22@desc:"""importpandasaspddf=pd.read_excel('/lianxi/SPI.xlsx�......
  • 20211316郭佳昊 《信息安全系统设计与实现(上)》第三周学习笔记
    一、任务要求[1]知识点归纳以及自己最有收获的内容,选择至少2个知识点利用chatgpt等工具进行苏格拉底挑战,并提交过程截图,提示过程参考下面内容(4分)我在学***X知识点,请你以苏格拉底的方式对我进行提问,一次一个问题核心是要求GPT:请你以苏格拉底的方式对我进行提问然后GPT就会......
  • .Net Linq语句去除A集合中存在的B集合数据
    这算是一个取巧的场景,在添加数据库的时候,存在一种场景,主数据表的Id和关系表的Id关联,那么在添加子表的时候,为了避免重复,就可以使用到,当然避免重复的方法有很多,这算是一种偷懒的方式,以下是用过C#代码模拟场景,本片随笔为了记录.....usingSystem.Collections.Generic;n......
  • jQuery对输入框进行验证,只允许输入字母和数字
    使用jQuery来对这两个输入框进行验证,确保只允许输入字母和数字,不允许输入中文字符。以下是相应的示例代码:<!DOCTYPEhtml><html> <head> <metacharset="UTF-8"> <title></title> <scriptsrc="https://cdn.staticfile.org/jquery/2.1.1/jquery.min.js&qu......