目录链接：

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目：

https://github.com/September26/java-algorithms

原题链接：. - 力扣（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’对集合进行翻转，这样时间复杂度为O(n2)。但是看了官方答案后，还是官方答案更合理。

其实所谓的翻转，并不是一定需要翻转集合，只更改插入的位置也是可以的。比如翻转一个集合，和往一个未翻转的集合头节点插入是一样的效果。

代码：

class Solution2810
{
public:
    string finalString(string s)
    {
        deque<char> q;
        bool head = false;
        for (char ch : s)
        {
            if (ch != 'i')
            {
                if (head)
                {
                    q.push_front(ch);
                }
                else
                {
                    q.push_back(ch);
                }
            }
            else
            {
                head = !head;
            }
        }
        string ans = (head ? string{q.rbegin(), q.rend()} : string{q.begin(), q.end()});
        return ans;
    }
};