【C++栈贪心决策包容性】3170. 删除星号以后字典序最小的字符串|1772

本文涉及知道点

C++栈模拟
C++贪心

LeetCode3170. 删除星号以后字典序最小的字符串

给你一个字符串 s 。它可能包含任意数量的 ‘’ 字符。你的任务是删除所有的 '’ 字符。
当字符串还存在至少一个 ‘’ 字符时，你可以执行以下操作：
删除最左边的 '’ 字符，同时删除该星号字符左边一个字典序最小的字符。如果有多个字典序最小的字符，你可以删除它们中的任意一个。
请你返回删除所有 '’ 字符以后，剩余字符连接而成的
字典序最小的字符串。
示例 1：
输入：s = "aaba"
输出：“aab”
解释：
删除 ‘’ 号和它左边的其中一个 ‘a’ 字符。如果我们选择删除 s[3] ，s 字典序最小。
示例 2：
输入：s = “abc”
输出：“abc”
解释：
字符串中没有 '’ 字符。
提示：
1 <= s.length <= 10⁵
s 只含有小写英文字母和 ‘’ 字符。
输入保证操作可以删除所有的 '’ 字符。

栈

贪心（决策包容性）：显然有多个最小序字符时，删除最后一个。
indexs[j]记录 s[0…i-1]中为’a’+j的下标，升序。
如果s[i]是’'，则选择j1最大且indexs[j1]非空， s[indexs[j1]]= '’ indexs[j1].pop()。
否则, indexs[s[j]-‘a’].push(i)。
删除s所有的’*'，并返回s。

代码

核心代码

class Solution {public:string clearStars(string s) {stack<int> indexs[26];auto Del = [&]() {for (int i = 0; i < 26; i++) {if (indexs[i].size()) {s[indexs[i].top()] = '*';indexs[i].pop();return;}}};for (int i = 0; i < s.length(); i++) {if ('*' == s[i]) { Del(); }else {indexs[s[i] - 'a'].emplace(i);}}				auto it = remove(s.begin(), s.end(), '*');s.erase(it, s.end());return s;}};;

单元测试

string s;TEST_METHOD(TestMethod11){s = "aaba*";auto res = Solution().clearStars(s);AssertEx(string("aab"), res);}TEST_METHOD(TestMethod12){s = "abc";auto res = Solution().clearStars(s);AssertEx(string("abc"), res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功