自助做网站傻瓜式自助建站工具,招聘网络推广专员,俄文网站建设 俄文网站设计,北京公司网站制作流程2434. 使用机器人打印字典序最小的字符串 解题报告#xff1a;
首先进行题意转换#xff0c;其实上述两种操作描述的就是一个栈。
为什么要进行题意转换呢#xff1f;因为你看题目说有两种操作#xff0c;但是却不问最少的操作数#xff0c;说明说不定这两种操作可以合并…2434. 使用机器人打印字典序最小的字符串 解题报告
首先进行题意转换其实上述两种操作描述的就是一个栈。
为什么要进行题意转换呢因为你看题目说有两种操作但是却不问最少的操作数说明说不定这两种操作可以合并或者转换与两种操作无关。
既然是字典序考虑贪心。
本来想的是从字符a-z进行遍历先处理a在处理b这样但是好像处理不了bdacb这种情况。
发现最后的输出结果不一定是按照字母顺序来的。即结果不是abdbc而是abcdb
然后发现没这么复杂从栈的角度考虑贪心啥时候入栈啥时候输出就行了。
AC代码
class Solution:def robotWithString(self, s: str) - str:dp [0]*(len(s)1)dp[len(s)] zdp[len(s)-1] s[len(s)-1]for i in range(len(s)-2,-1,-1):dp[i] dp[i1]if s[i] dp[i]:dp[i] s[i]i 0ans sk []while i len(s):sk.append(s[i])while len(sk)0 and sk[-1] dp[i1]:c sk.pop()ans ans ci1while len(sk) 0:ans ans sk.pop()return ans错误思路的代码
假设当前处理的字符是c。
本来想着是先往前看相邻的输出必须是连续的c字符然后往后看只输出c字符一直到后面没有c字符然后再往前看栈内的全都输出一直到输出完c字符
几个地方要注意
1、①那里没必要因为他可以和第二种方法合并没必要先处理当前字符然后再进流程。而且这些流程外的代码越多需要加的特判也越多。比如这里需要判断poss.size()也需要判断不想把当前值压入而是直接处理栈内元素的情况
2、写之前想好是要每次操作完都pos还是下次操作前才pos。
3、想好最外层for是按照a~z的字符来还是按照s这个串来。
4、有那些变量是要捆绑变化和维护的要注意好。
5、vis和mp具体代表的含义到底是什么要定义清楚免得出现歧义。其实vis虽然这么多地方维护但是只使用了一次在流程中的第二步使用到。所以在这之后其实就不需要维护vis了
class Solution {
public:string robotWithString(string s) {string ans ;mapchar, int mp, vis;for(auto c:s) {mp[c] 1;}string sk ;int pos 0;for(char c a; cz; c) {if(mp[c] 0) continue;//1、没必要// if(pos s.size()) {// sk.push_back(s[pos]);// vis[s[pos]];// pos;// }int num 0;//先往前看while(sk.size()0sk.back() c) {ans.push_back(c);sk.pop_back();num;}//再往后看while(vis[c] mp[c]) {sk.push_back(s[pos]);vis[s[pos]];if(s[pos] c) {vis[c];ans.push_back(c);sk.pop_back();num;}pos;}// 再往前看while(num mp[c] sk.size()0) {char tmp sk.back();sk.pop_back();mp[tmp]--;vis[tmp]--;ans.push_back(tmp);}}return ans;}
};
