LeetCode 2810. Faulty Keyboard【模拟,双端队列,字符串】简单

这篇具有很好参考价值的文章主要介绍了LeetCode 2810. Faulty Keyboard【模拟,双端队列,字符串】简单。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,还会用多种编程语言实现题解,涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件,我还建立了相关的仓库:https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中,你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等,还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解,还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动,欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

你的笔记本键盘存在故障,每当你在上面输入字符 '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'

解法 模拟+双端队列

本题可以每次遇到 i 就反转前面的所有字符,但假如后一半的字符全部是 i ,遍历到后一半时,每次都要将前一半的字符反转一遍,这样的代价是 O ( n 2 ) O(n^2) O(n2) 的。

我们可以把第一次遇到 i 反转,看作是往字符串的头部依次添加后续字符,最后从字符串尾部往前读取全部字符这样前面遍历过的字符就反转了,后续添加的字符的顺序不变。如果再遇到 i ,就将后续字符添加到字符串的尾部,最后从字符串头部往后读取全部字符……如此反复反转,直到处理完全部字符。根据最后一次遇到 i 决定的方向,读取全部字符

这可以用双端队列实现。文章来源地址https://www.toymoban.com/news/detail-645976.html

class Solution {
public:
    string finalString(string s) {
        deque<char> dq;
        bool last = true;
        for (char c : s) {
            if (c == 'i') last = !last;
            else if (last) dq.push_back(c);
            else dq.push_front(c);
        }
        return last ? string(dq.begin(), dq.end()) : string(dq.rbegin(), dq.rend());
    }
};

到了这里,关于LeetCode 2810. Faulty Keyboard【模拟,双端队列,字符串】简单的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode·每日一题·415. 字符串相加·模拟

    作者:小迅 链接:https://leetcode.cn/problems/add-strings/solutions/2347085/mo-ni-zhu-shi-chao-ji-xiang-xi-by-xun-ge-fges/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。   题意 - 给定二个字符串,计算它们的和并同样以字符串形式返回。 直接从

    2024年02月16日
    浏览(40)
  • 【力扣·每日一题】2182.构造限制重复的字符串(模拟 贪心 优先队列 C++ Go)

    题目链接 给你一个字符串 s 和一个整数 repeatLimit ,用 s 中的字符构造一个新字符串 repeatLimitedString ,使任何字母 连续 出现的次数都不超过 repeatLimit 次。你不必使用 s 中的全部字符。 返回 字典序最大的 repeatLimitedString 。 如果在字符串 a 和 b 不同的第一个位置,字符串 a 中

    2024年01月17日
    浏览(53)
  • 【LeetCode】字符串转换整数 (atoi) [M](模拟)

    8. 字符串转换整数 (atoi) - 力扣(LeetCode) 请你来实现一个 myAtoi(string s) 函数,使其能将字符串转换成一个 32 位有符号整数(类似 C/C++ 中的 atoi 函数)。 函数 myAtoi(string s) 的算法如下: 读入字符串并丢弃无用的前导空格 检查下一个字符(假设还未到字符末尾)为正还是负

    2024年02月07日
    浏览(68)
  • LeetCode 2788.按分隔符拆分字符串:模拟(字符串处理)

    力扣题目链接:https://leetcode.cn/problems/split-strings-by-separator/ 给你一个字符串数组 words 和一个字符 separator ,请你按 separator 拆分 words 中的每个字符串。 返回一个由拆分后的新字符串组成的字符串数组, 不包括空字符串 。 注意 separator 用于决定拆分发生的位置,但它不包含在

    2024年01月21日
    浏览(57)
  • 【数据结构-队列】双端队列

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月09日
    浏览(36)
  • (栈和队列) 1047. 删除字符串中的所有相邻重复项 ——【Leetcode每日一题】

    难度:简单 给出由小写字母组成的字符串 S , 重复项删除操作 会选择两个相邻且相同的字母,并删除它们。 在 S 上反复执行重复项删除操作,直到无法继续删除。 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。 示例: 输入 :“abbaca” 输出 :“ca” 解释

    2024年02月08日
    浏览(51)
  • 循环队列、双端队列 C和C++

    目录 概念 实现方式 顺序队列 循环队列 队列的数组实现 用循环链表实现队列 STL 之 queue 实现队列  STL 之 dequeue 实现双端队列  概念 队列是一种特殊的线性表,它只允许在 表的前端 (称为队头,front)进行 删除操作 —— 出队 ,而在 表的后端 (称为队尾,rear)进行 插入

    2023年04月09日
    浏览(33)
  • 数据结构--双端队列

    双端队列(Double-ended Queue,简称Deque)是一种具有队列和栈特性的数据结构,可以在队列的两端进行插入和删除操作。双端队列允许从前端和后端同时进行插入和删除操作,因此可以称为“两端都可以进出的队列”。 双端队列的特点包括: 可以在队列的头部和尾部进行插入和

    2024年02月08日
    浏览(45)
  • 49天精通Java,第27天,队列、双端队列、优先队列

    大家好,我是哪吒。 双端队列是一种特殊的队列,它的两端都可以进行插入和删除操作。这种队列的实现方式是使用两个指针,一个指针指向队列的头部,另一个指针指向队列的尾部。当需要插入或删除元素时,只需要移动指针即可。

    2024年02月03日
    浏览(44)
  • 双端队列deque(C++)

    栗酱有一天在网上冲浪的时候发现了一道很有意思的数据结构题。 该数据结构形如长条形。 一开始该容器为空,有以下七种操作。 1 a从前面插入元素a 2 从前面删除一个元素 3 a从后面插入一个元素 4 从后面删除一个元素 5 将整个容器头尾翻转 6 输出个数和所有元素 7 对所有

    2024年02月11日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包