烟台网站开发公司,微信模板怎么制作,百度认证有什么用,品牌网站建设小8a蝌蚪【LetMeFly】2810.故障键盘#xff1a;双端队列模拟
力扣题目链接#xff1a;https://leetcode.cn/problems/faulty-keyboard/
你的笔记本键盘存在故障#xff0c;每当你在上面输入字符 i 时#xff0c;它会反转你所写的字符串。而输入其他字符则可以正常工作。
给你一个…【LetMeFly】2810.故障键盘双端队列模拟
力扣题目链接https://leetcode.cn/problems/faulty-keyboard/
你的笔记本键盘存在故障每当你在上面输入字符 i 时它会反转你所写的字符串。而输入其他字符则可以正常工作。
给你一个下标从 0 开始的字符串 s 请你用故障键盘依次输入每个字符。
返回最终笔记本屏幕上输出的字符串。 示例 1
输入s string
输出rtsng
解释
输入第 1 个字符后屏幕上的文本是s 。
输入第 2 个字符后屏幕上的文本是st 。
输入第 3 个字符后屏幕上的文本是str 。
因为第 4 个字符是 i 屏幕上的文本被反转变成 rts 。
输入第 5 个字符后屏幕上的文本是rtsn 。
输入第 6 个字符后屏幕上的文本是 rtsng 。
因此返回 rtsng 。示例 2
输入s poiinter
输出ponter
解释
输入第 1 个字符后屏幕上的文本是p 。
输入第 2 个字符后屏幕上的文本是po 。
因为第 3 个字符是 i 屏幕上的文本被反转变成 op 。
因为第 4 个字符是 i 屏幕上的文本被反转变成 po 。
输入第 5 个字符后屏幕上的文本是pon 。
输入第 6 个字符后屏幕上的文本是pont 。
输入第 7 个字符后屏幕上的文本是ponte 。
输入第 8 个字符后屏幕上的文本是ponter 。
因此返回 ponter 。 提示
1 s.length 100s 由小写英文字母组成s[0] ! i
解题方法双端队列模拟
使用一个双端队列来存放要输出的字符们默认将字符添加到双端队列的右边后面。
使用一个布尔类型的变量push_front来记录当前字符是否应该添加到双端队列的右边。
遍历字符串
如果当前字符为i则说明需要“翻转字符串”。我们不需要真正翻转字符串只需要标记一下说“原来字符串的头现在你变成尾了”翻转变量push_front的值。否则依据变量push_front的值将字符添加到字符串的头或尾。
最终依据变量push_front的值从头到尾或从尾到头将队列中的字符拼接成字符串。
时空复杂度分析
时间复杂度 O ( l e n ( s ) ) O(len(s)) O(len(s))空间复杂度 O ( l e n ( s ) ) O(len(s)) O(len(s))
虽然这种方法时间复杂度为 O ( n ) O(n) O(n)但是题目的数据返回是 1 0 2 10^2 102级别因此效果可能不如直接的模拟。
AC代码
C
class Solution {
public:string finalString(string s) {dequechar q;bool push_front false;for (char c : s) {if (c i) {push_front !push_front;continue;}if (push_front) {q.push_front(c);}else {q.push_back(c);}}return push_front ? string{q.rbegin(), q.rend()} : string{q.begin(), q.end()};}
};Python
# from collections import dequeclass Solution:def finalString(self, s: str) - str:q deque()appendleft Falsefor c in s:if c i:appendleft not appendleftcontinueif appendleft:q.appendleft(c)else:q.append(c)return .join(q)[::-1] if appendleft else .join(q)愚人节快乐 同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/137242651
