本文主要是介绍LeetCode 2810.故障键盘:双端队列模拟,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
【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 <= 100
s
由小写英文字母组成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) {deque<char> 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和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/137242651
这篇关于LeetCode 2810.故障键盘:双端队列模拟的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!