欧美网站源码,赣州人才网招聘官网最新招聘,wordpress下雪,建站合作本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服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 100s 由小写英文字母组成s[0] ! i 解法 模拟双端队列
本题可以每次遇到 i 就反转前面的所有字符但假如后一半的字符全部是 i 遍历到后一半时每次都要将前一半的字符反转一遍这样的代价是 O ( n 2 ) O(n^2) O(n2) 的。
我们可以把第一次遇到 i 反转看作是往字符串的头部依次添加后续字符最后从字符串尾部往前读取全部字符这样前面遍历过的字符就反转了后续添加的字符的顺序不变。如果再遇到 i 就将后续字符添加到字符串的尾部最后从字符串头部往后读取全部字符……如此反复反转直到处理完全部字符。根据最后一次遇到 i 决定的方向读取全部字符。
这可以用双端队列实现。
class Solution {
public:string finalString(string s) {dequechar 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());}
};
